c語言各種排序法詳解

1、c語言各樣排序法詳解c語言各樣排序法詳解21/21c語言各樣排序法詳解適用文檔一插入排序1.1直接插入排序基本思想：每次將一個待排序額記錄按其重點(diǎn)碼的大小插入到一個已經(jīng)排好序的有序序列中，直到所有記錄排好序。圖解：代碼實(shí)現(xiàn)：cppviewplaincopy/直接次序排序2.voidInsertSort(intr,intn)4.for(inti=2;in;i+)適用文檔5.6.r0=ri;/設(shè)置哨兵7.for(intj=i-1;r0rj;j-)/找尋插入地點(diǎn)8.rj+1=rj;/記錄后移9.rj+1=r0;10.11.for(intk=1;kn;k+)12.coutrk;13.coutn;14.

2、1.2希爾排序基本思想是：先將整個待排序記錄序列切割成若干個子序列，在在序列內(nèi)分別進(jìn)行直接插入排序，待整個序列基本有序時，再對全體記錄進(jìn)行一次直接插入排序。圖解：代碼實(shí)現(xiàn)：cppviewplaincopy/希爾排序2.voidShellSort(intr,intn)適用文檔4.inti;5.intd;6.intj;7.for(d=n/2;d=1;d=d/2)/以增量為d進(jìn)行直接插入排序8.9.for(i=d+1;i0&r0rj;j=j-d)13.rj+d=rj;/記錄后移d個地點(diǎn)14.rj+d=r0;15.16.for(i=1;in;i+)18.coutri;coutn;互換排序2.1起泡排序

3、起泡排序是互換排序中最簡單的排序方法，其基本思想是：兩兩比較相鄰記錄的重點(diǎn)碼，假如反序則互換，直到?jīng)]有反序的記錄為止。圖解：適用文檔代碼實(shí)現(xiàn)：cppviewplaincopy/起泡排序2.voidBubbleSort(intr,intn)4.inttemp;5.intexchange;6.intbound;7.exchange=n-1;/第一趟起泡排序的范圍是r0到rn-18.while(exchange)/僅當(dāng)上一趟排序有記錄互換才進(jìn)行本趟排序9.10.bound=exchange;11.exchange=0;12.for(intj=0;jrj+1)14.適用文檔15.temp=rj;16.

4、rj=rj+1;17.rj+1=temp;18.exchange=j;/記錄每一次發(fā)生記錄互換的地點(diǎn)19.20.21.for(inti=0;in;i+)22.coutri;23.coutn;24.2.2迅速排序基本思想:經(jīng)過一趟排序?qū)⒁判虻臄?shù)據(jù)切割成獨(dú)立的兩部分，此中一部分的所有數(shù)據(jù)都比其他一部分的所有數(shù)據(jù)都要小，此后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行迅速排序，整個排序過程能夠遞歸進(jìn)行，以此達(dá)到整個數(shù)據(jù)變?yōu)橛行蛐蛄小D解：適用文檔代碼實(shí)現(xiàn)：cppviewplaincopy/迅速排序一次區(qū)分2.intPartition(intr,intfirst,intend)4.inti=first;/初始化

5、適用文檔5.intj=end;6.inttemp;7.8.while(ij)9.10.while(ij&ri=rj)11.j-;/右側(cè)掃描12.if(ij)13.14.temp=ri;/將較小記錄互換到前面15.ri=rj;16.rj=temp;17.i+;18.19.while(ij&ri=rj)20.i+;/左側(cè)掃描21.if(ij)22.23.temp=rj;24.rj=ri;25.ri=temp;/將較大記錄互換到后邊26.j-;27.28.29.returni;/i為軸值記錄的最后地點(diǎn)30.31./迅速排序33.voidQuickSort(intr,intfirst,intend)3

6、4.35.if(firstend)36./遞歸納束37.intpivot=Partition(r,first,end);/一次區(qū)分38.QuickSort(r,first,pivot-1);/遞歸地對左邊子序列進(jìn)行快速排序39.QuickSort(r,pivot+1,end);/遞歸地對右邊子序列進(jìn)行迅速排序40.適用文檔41.42.三選擇排序3.1簡單項(xiàng)選擇擇排序基本思想：設(shè)所排序序列的記錄個數(shù)為n。i取1,2,（Ri,Ri+1,Rn）中找出排序碼最小的記錄，與第,n-1,從所有n-i+1i個記錄互換。履行個記錄n-1趟后就達(dá)成了記錄序列的排序。圖解：適用文檔代碼實(shí)現(xiàn)：cppviewplai

7、ncopy/簡單項(xiàng)選擇擇排序2.voidSelectSort(intr,intn)4.inti;5.intj;6.intindex;7.inttemp;8.for(i=0;in-1;i+)/對n個記錄進(jìn)行n-1趟簡單項(xiàng)選擇擇排序9.10.index=i;11.for(j=i+1;jn;j+)/在無序區(qū)中采納最小記錄12.if(rjrindex)13.index=j;14.if(index!=i)15.16.temp=ri;17.ri=rindex;18.rindex=temp;19.20.21.for(i=0;in;i+)22.coutri;23.coutn;24.3.2堆排序堆的定義堆是擁有

8、以下性質(zhì)的完滿二叉樹：每個結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（小根堆）；或許每個結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（大根堆）。大根堆和小根堆：根結(jié)點(diǎn)（亦稱為堆頂）的重點(diǎn)字是堆里所有結(jié)點(diǎn)重點(diǎn)字中最小者的堆稱為小根堆，又稱最小堆。根結(jié)點(diǎn)（亦稱為堆頂）的重點(diǎn)字是堆里所有結(jié)點(diǎn)重點(diǎn)字中最大者，稱為大根堆，又稱最大堆。注意：堆中任一子樹亦是堆。以上討論的堆其實(shí)是二叉堆Binary適用文檔Heap），近似地可定義k叉堆。假定目前要優(yōu)選結(jié)點(diǎn)的編號為k，堆中最后一個結(jié)點(diǎn)的編號為m，而且結(jié)點(diǎn)k的左右子樹均是堆（即rk+1rm知足堆的條件），則優(yōu)選算法用偽代碼可描繪為：適用文檔詳細(xì)的優(yōu)選代碼以下：cppvi

9、ewplaincopy/優(yōu)選法調(diào)整堆2.voidSift(intr,intk,intm)5.inti;6.intj;7.inttemp;8.i=k;9.j=2*i+1;/置i為要篩的結(jié)點(diǎn)，j為i的左孩子10.while(j=m)/優(yōu)選還沒有進(jìn)行到葉子12.if(jm&rjrj)break;/根結(jié)點(diǎn)已經(jīng)大于左右孩子中的較大者15.else16.17.temp=ri;18.ri=rj;19.rj=temp;/將根結(jié)點(diǎn)與結(jié)點(diǎn)j互換20.i=j;21.j=2*i+1;/被篩結(jié)點(diǎn)位于本來結(jié)點(diǎn)j的地點(diǎn)22.堆排序堆排序的基本思想是：第一將待排序的記錄序列結(jié)構(gòu)成一個堆，此時，選出了堆中所有記錄的最大者即堆頂

10、記錄，此后將它從堆中移走（平常將堆頂記錄和堆中最后一個記錄互換），并將節(jié)余的記錄再調(diào)整成堆，這樣又找出了次大的記錄，以此類推，直到堆中只有一個記錄為止。適用文檔（1）用大根堆排序的基本思想先將初始文件R1.n建成一個大根堆，此堆為初始的無序區(qū)再將重點(diǎn)字最大的記錄R1（即堆頂）和無序區(qū)的最后一個記錄Rn互換，由此獲得新的無序區(qū)R1.n-1和有序區(qū)Rn，且知足R1.n-1.keysRn.key因?yàn)榛Q后新的根R1可能違犯堆性質(zhì)，故應(yīng)將目前無序區(qū)R1.n-1調(diào)整為堆。此后再次將R1.n-1中重點(diǎn)字最大的記錄R1和該區(qū)間的最后一個記錄Rn-1互換，由此獲得新的無序區(qū)R1.n-2和有序區(qū)Rn-1.n，且

11、仍知足關(guān)系R1.n-2.keysRn-1.n.keys，相同要將R1.n-2調(diào)整為堆。直到無序區(qū)只有一個元素為止。（2）大根堆排序算法的基本操作：初始化操作：將R1.n結(jié)構(gòu)為初始堆；每一趟排序的基本操作：將目前無序區(qū)的堆頂記錄R1和該區(qū)間的最后一個記錄互換，此后將新的無序區(qū)調(diào)整為堆（亦稱重修堆）。注意：只要做n-1趟排序，選出較大的n-1個重點(diǎn)字即能夠使得文件遞加有序。用小根堆排序與利用大根堆近似，只可是其排序結(jié)果是遞減有序的。堆排序和直接選擇排序相反：在任何時辰堆排序中無序區(qū)老是在有序區(qū)以前，且有序區(qū)是在原向量的尾部由后往前逐漸擴(kuò)大至整個向量為止適用文檔適用文檔代碼實(shí)現(xiàn)：cppviewpla

12、incopy適用文檔/堆排序2.voidHeapSort(intr,intn)4.5.inti;6.inttemp;7.for(i=n/2;i=0;i-)/初始建堆，從最后一個非終端結(jié)點(diǎn)至根結(jié)點(diǎn)8.Sift(r,i,n);9.for(i=n-1;i0;i-)/重復(fù)履行移走堆頂及重修堆的操作11.temp=ri;12.ri=r0;13.r0=temp;14.Sift(r,0,i-1);for(i=0;in;i+)17.coutri;coutn;合并排序二路合并排序基本思想：將若干個有序序列進(jìn)行兩兩合并，直至所有待排序記錄都在一個有序序列為止。適用文檔一路合并算法實(shí)現(xiàn)：cppviewplainco

13、py/一次合并2.voidMerge(intr,intr1,ints,intm,intt)5.inti=s;6.intj=m+1;7.intk=s;8.9.while(i=m&j=t)10.11.if(ri=rj)12.r1k+=ri+;/取ri和rj中較小者放入r1k13.else14.r1k+=rj+;15.16.if(i=m)17.while(i=m)/若第一個子序列沒辦理完，則進(jìn)行掃尾辦理18.r1k+=ri+;19.else20.while(j=t)/若第二個子序列沒辦理完，則進(jìn)行掃尾辦理適用文檔21.r1k+=rj+;22.cppviewplaincopy/一趟合并2.voidMe

14、rgePass(intr,intr1,intn,inth)4.inti=0;5.intk;6.7.while(i=n-2*h)/待合并記錄至罕有兩個長度為h的子序列9.Merge(r,r1,i,i+h-1,i+2*h-1);10.i+=2*h;適用文檔12.if(in-h)13.Merge(r,r1,i,i+h-1,n);/待合并序列中有一個長度小于h14.elsefor(k=i;k=n;k+)/待合并序列中只剩一個子序列15.r1k=rk;/合并排序的非遞歸算法19.voidMergeSort1(intr,intr1,intn)inth=1;inti;24.while(hn)26.MergePass(r,r1,n-1,h);/合并27.h=2*h;28.MergePass(r1,r,n-1,h);29.h=2*h;for(i=0;in;i+)32.coutri;coutn;下邊看看二路合并排序的遞歸實(shí)現(xiàn)適用文檔cppviewplaincopy/合并排序的遞歸算法2.voidMergeSort