幾種常見的排序算法

總結(jié)一些C語(yǔ)言中常見的排序算法，都已經(jīng)實(shí)現(xiàn)。1、冒泡排序算法思想簡(jiǎn)單描述：在要排序的一組數(shù)中，對(duì)當(dāng)前還未排好序的范圍內(nèi)的全部數(shù)，自上而下對(duì)相鄰的兩個(gè)數(shù)依次進(jìn)行比較和調(diào)整，讓較大的數(shù)往下沉，較小的往上冒。即：每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時(shí)，就將它們互換。冒泡排序是穩(wěn)定的。算法時(shí)間復(fù)雜度O(n2)--[n的平方]main(){inta[10],i,j,k;printf(〃Thisisamaopaosort\n〃)；printf(〃Pleaseinput10numbersforsort:");for(i=0;i<10;i++)scanf(〃％d〃，&a[i]);for(i=0;i<9;i++)for(j=0;j<10-i;j++)if(a[j]>a[j+1]){k=a[j];a[j]=a[j+1];a[j+1]=k;}printf("Thecorretsortofthosenumbersis:");for(i=0;i<10;i++)printf("%d",a[i]);printf("\n");}2、選擇排序算法思想簡(jiǎn)單描述：在要排序的一組數(shù)中，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止。選擇排序是不穩(wěn)定的。算法復(fù)雜度O(n2)--[n的平方]main(){intt,k,i,j,a[10];printf("Thisisaselectsort\n");printf("Pleaseinputsomenumberthatyouwanttosort:");for(i=0;i<10;i++)scanf("%d",&a[i]);for(i=0;i<9;i++)(k=i;for(j=i+1;j<10;j++)if(a[k]>a[j])k=j;t=a[i];a[i]=a[k];a[k]=t;}printf(〃Thecorrectsortofthosenumberis:");for(i=0;i<10;i++)printf(〃％d",a[i]);printf("\n");}3、插入排序算法思想簡(jiǎn)單描述：在要排序的一組數(shù)中，假設(shè)前面(n-1)[n>=2]個(gè)數(shù)已經(jīng)是排好順序的，現(xiàn)在要把第n個(gè)數(shù)插到前面的有序數(shù)中，使得這n個(gè)數(shù)也是排好順序的。如此反復(fù)循環(huán)，直到全部排好順序。直接插入排序是穩(wěn)定的。算法時(shí)間復(fù)雜度O(n2)--[n的平方]main()(inta[10],j,i,m;printf("thisisainsertsort\n");printf("Pleaseinputthe10numberyouwanttosort:");for(i=0;i<10;i++)scanf(〃％d〃，&a[i]);for(j=1;j<10;j++)(m=a[j];for(i=j-1;i>=0;i--)(if(a[i]<m)break;elsea[i+1]=a[i];}a[i+1]=m;}printf("Thecorrectorderofthosenumbersis:");for(i=0;i<10;i++)printf("%d",a[i]);printf("\n");}4、快速排序算法思想簡(jiǎn)單描述：快速排序是對(duì)冒泡排序的一種本質(zhì)改進(jìn)。它的基本思想是通過(guò)一趟掃描后，使得排序序列的長(zhǎng)度能大幅度地減少。在冒泡排序中，一次掃描只能確保最大數(shù)值的數(shù)移到正確位置，而待排序序列的長(zhǎng)度可能只減少1?？焖倥判蛲ㄟ^(guò)一趟掃描，就能確保以某個(gè)數(shù)為基準(zhǔn)點(diǎn)的左邊各數(shù)都比它小，右邊各數(shù)都比它大。然后又用同樣的方法處理它左右兩邊的數(shù)，直到基準(zhǔn)點(diǎn)的左右只有一個(gè)元素為止。顯然快速排序可以用遞歸實(shí)現(xiàn)，當(dāng)然也可以用棧化解遞歸實(shí)現(xiàn)。快速排序是不穩(wěn)定的。最理想情況算法時(shí)間復(fù)雜度O(nlog2n)，最壞O(n2)quick(intfirst,intend,intL[]){intleft二first,right二end,key;key=L[first];while(left<right){while((left<right)&&(L[right]>=key))right--;if(left<right)L[left++]=L[right];while((left<right)&&(L[left]<=key))left++;if(left<right)L[right--]=L[left];}L[left]=key;returnleft;}quick_sort(intL[],intfirst,intend){intsplit;if(end>first){split二quick(first,end,L);quick_sort(L,first,split-1);quick_sort(L,split+1,end);}}main(){inta[10],i;printf("Thisisaquicksort\n〃)；printf("Pleaseinput10numbersforsort:");for(i=0;i<10;i++)scanf(〃％d〃，&a[i]);quick_sort(a,0,9);printf("Thecorrectsortofthosenumbersis:");for(i=0;i<10;i++)printf("%d",a[i]);printf("\n");}5、希爾排序算法思想簡(jiǎn)單描述：D.L.shell于1959年在以他名字命名的排序算法中實(shí)現(xiàn)了這一思想。算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組，每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行排序，然后再用一個(gè)較小的增量對(duì)它進(jìn)行，在每組中再進(jìn)行排序。當(dāng)增量減到1時(shí)，整個(gè)要排序的數(shù)被分成一組，排序完成。下面的函數(shù)是一個(gè)希爾排序算法的一個(gè)實(shí)現(xiàn)，初次取序列的一半為增量，以后每次減半，直到增量為1。希爾排序是不穩(wěn)定的。voidshell_sort(int*x,intn)(inth,j,k,t;for(h=n/2;h>0;h=h/2)/*控制增量*/(for(j=h;j<n;j++)/*這個(gè)實(shí)際上就是上面的直接插入排序*/(t=*(x+j);for(k=j-h;(k>=0&&t<*(x+k));k-=h)(*(x+k+h)=*(x+k);}*(x+k+h)=t;}}}6、堆排序算法思想簡(jiǎn)單描述：堆排序是一種樹形選擇排序，是對(duì)直接選擇排序的有效改進(jìn)。堆的定義如下：具有n個(gè)元素的序列(h1,h2,...,hn),當(dāng)且僅當(dāng)滿足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)時(shí)稱之為堆。在這里只討論滿足前者條件的堆。由堆的定義可以看出，堆頂元素(即第一個(gè)元素)必為最大項(xiàng)。完全二叉樹可以很直觀地表示堆的結(jié)構(gòu)。堆頂為根，其它為左子樹、右子樹。初始時(shí)把要排序的數(shù)的序列看作是一棵順序存儲(chǔ)的二叉樹，調(diào)整它們的存儲(chǔ)順序，使之成為一個(gè)堆，這時(shí)堆的根節(jié)點(diǎn)的數(shù)最大。然后將根節(jié)點(diǎn)與堆的最后一個(gè)節(jié)點(diǎn)交換。然后對(duì)前面(n-1)個(gè)數(shù)重新調(diào)整使之成為堆。依此類推，直到只有兩個(gè)節(jié)點(diǎn)的堆，并對(duì)它們作交換，最后得到有n個(gè)節(jié)點(diǎn)的有序序列。從算法描述來(lái)看，堆排序需要兩個(gè)過(guò)程，一是建立堆，二是堆頂與堆的最后一個(gè)元素交換位置。所以堆排序有兩個(gè)函數(shù)組成。一是建堆的滲透函數(shù)，二是反復(fù)調(diào)用滲透函數(shù)實(shí)現(xiàn)排序的函數(shù)。有最大堆和最少堆之分堆排序是不穩(wěn)定的。算法時(shí)間復(fù)雜度O(nlog2n)。功能：滲透建堆voidsift(int*x,intn,ints)(intt,k,j;t=*(x+s);/*暫存開始元素*/k=s;/*開始元素下標(biāo)*/j=2*k+1;/*右子樹元素下標(biāo)*/while(j<n)(if(j<n-1&&*(x+j)<*(x+j+1))/判斷是否滿足堆的條件：滿足就繼續(xù)下一輪比較，否則調(diào)整。*/(j++;}if(t<*(x+j))/*調(diào)整*/(*(x+k)=*(x+j);k=j;/*調(diào)整后，開始元素也隨之調(diào)整*/j=2*k+1;}else/*沒有需要調(diào)整了，已經(jīng)是個(gè)堆了，退出循環(huán)。*/(break;}}*(x+k)=t;/*開始元素放到它正確位置*/}