c語(yǔ)言各種排序法詳解

1、最新 料推薦一插入排序1.1直接插入排序基本思想：每次將一個(gè)待排序額記錄按其關(guān)鍵碼的大小插入到一個(gè)已經(jīng)排好序的有序序列中，直到全部記錄排好序。圖解：代碼實(shí)現(xiàn)：cppview plaincopy1. / 直接順序排序2.voidInsertSort(intr,intn)3. 4. for ( int i=2; in; i+)1最新 料推薦5. 6.r0=ri;/設(shè)置哨兵7.for ( int j=i-1; r0rj; j-)/尋找插入位置8.rj+1=rj;/記錄后移9. rj+1=r0;10. 11. for ( int k=1;kn;k+)12.coutrk ;13.coutn;14.1.2

2、 希爾排序基本思想是： 先將整個(gè)待排序記錄序列分割成若干個(gè)子序列，在在序列內(nèi)分別進(jìn)行直接插入排序，待整個(gè)序列基本有序時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。圖解：代碼實(shí)現(xiàn)：cppview plaincopy1./ 希爾排序2.void ShellSort(int r,int n)3. 4. int i;2最新 料推薦5. int d;6. int j;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 個(gè)位置14.rj+d=r0;15. 16. 17. for (

3、i=1;in;i+)18.coutri ;19.coutn;20. 二 交換排序2.1 起泡排序起泡排序是交換排序中最簡(jiǎn)單的排序方法，其基本思想是：兩兩比較相鄰記錄的關(guān)鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。圖解：3最新 料推薦代碼實(shí)現(xiàn)：cppview plaincopy1./ 起泡排序2.void BubbleSort(int r,int n)3. 4. int temp;5. int exchange;6. int bound;7.exchange=n-1;/第一趟起泡排序的范圍是r0 到rn-18.while (exchange)/僅當(dāng)上一趟排序有記錄交換才進(jìn)行本趟排序9. 10.

4、 bound=exchange;11. exchange=0;12.for( int j=0; jrj+1)14. 4最新 料推薦15. temp=rj;16. rj=rj+1;17. rj+1=temp;18.exchange=j;/ 記錄每一次發(fā)生記錄交換的位置19. 20. 21. for ( int i=0;in;i+)22.coutri ;23.coutn;24.2.2 快速排序基本思想 :通過一趟 排序 將要排序的 數(shù)據(jù)分割 成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以 遞歸 進(jìn)行，以此達(dá)到整個(gè)數(shù)

5、據(jù)變成有序序列。圖解：5最新 料推薦代碼實(shí)現(xiàn)：cppview plaincopy1. / 快速排序一次劃分2.intPartition(intr,intfirst,intend)3. 4.inti=first;/ 初始化5.intj=end;6最新 料推薦6. int temp;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

6、(ij)22. 23. temp=rj;24. rj=ri;25.ri=temp;/ 將較大記錄交換到后面26.j-;27. 28. 29.returni;/i為軸值記錄的最終位置30. 31.32. / 快速排序33.voidQuickSort(intr,intfirst,intend)34. 35. if (firstend)36./遞歸結(jié)束37.int pivot=Partition(r, first, end);/ 一次劃分38.QuickSort(r, first, pivot-1);/遞歸地對(duì)左側(cè)子序列進(jìn)行快速排序39.QuickSort(r, pivot+1, end);/遞歸地

7、對(duì)右側(cè)子序列進(jìn)行快速排序40. 41.42. 三 選擇排序7最新 料推薦3.1 簡(jiǎn)單選擇排序基本思想： 所排序序列的 個(gè)數(shù) n。i取 1,2, ,n-1, 從所有 n-i+1 個(gè) （ Ri,Ri+1, ,Rn）中找出排序 最小的 ，與第i 個(gè) 交 。 行n-1 趟后就完成了 序列的排序。 解：代 ：cppview plaincopy1. / 簡(jiǎn)單選擇排序2.voidSelectSort(intr ,intn)3. 4. int i;5. int j;6. int index;7. int temp;8最新 料推薦8.for(i=0; in-1; i+)/ 對(duì) n 個(gè)記錄進(jìn)行 n-1 趟簡(jiǎn)單選擇

8、排序9. 10. index=i;11.for(j=i+1; jn; j+)/ 在無(wú)序區(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 堆排序堆的定義堆是具有下列性質(zhì)的完全二叉樹：每個(gè)結(jié)點(diǎn)的值都小于或等于其左右孩子結(jié)點(diǎn)的值（小根堆 ）；或者每個(gè)結(jié)點(diǎn)的值都大于或等于其左右孩子結(jié)點(diǎn)的值（大根堆 ）。大根堆和小根堆： 根結(jié)點(diǎn) （亦稱為堆頂） 的關(guān)鍵字 是

9、堆里所有結(jié)點(diǎn)關(guān)鍵字中最小者的堆稱為小根堆，又稱 最小堆 。根結(jié)點(diǎn)（亦稱為堆頂）的 關(guān)鍵字 是堆里所有結(jié)點(diǎn)關(guān)鍵字中最大者，稱為大根堆，又稱最大堆。注意：堆中任一子樹亦是堆。以上討論的堆實(shí)際上是二叉堆（ BinaryHeap ），類似地可定義k 叉堆。9最新 料推薦假設(shè)當(dāng)前要篩選結(jié)點(diǎn)的編號(hào)為k，堆中最后一個(gè)結(jié)點(diǎn)的編號(hào)為m，并且結(jié)點(diǎn) k 的左右子樹均是堆（即rk+1 rm 滿足堆的條件），則篩選算法用偽代碼可描述為：具體的篩選代碼如下：cppview plaincopy1. / 篩選法調(diào)整堆2.voidSift(intr,intk,intm)10最新 料推薦3. 4.5. int i;6. int

10、j;7. int temp;8. i=k;9.j=2*i+1;/置 i 為要篩的結(jié)點(diǎn)， j 為 i 的左孩子10.while (j=m)/篩選還沒有進(jìn)行到葉子11. 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)位于原來(lái)結(jié)點(diǎn)j 的位置22. 23. 24. 堆排序堆排序的基本思想是： 首先將待排序的記錄序列構(gòu)造成一個(gè)堆， 此時(shí)，選出了堆中所有記錄的最大者即堆頂記錄，然后將它從堆中移走（通常將堆頂記

11、錄和堆中最后一個(gè)記錄交換），并將剩余的記錄再調(diào)整成堆， 這樣又找出了次大的記錄， 以此類推， 直到堆中只有一個(gè)記錄為止。（1 ）用大根堆排序的基本思想先將初始文件 R1.n 建成一個(gè)大根堆，此堆為初始的無(wú)序區(qū)再將關(guān)鍵字最大的記錄R1 （即堆頂）和無(wú)序區(qū)的最后一個(gè)記錄Rn 交換，由此得到新的無(wú)序區(qū) R1.n-1和有序區(qū) Rn ，且滿足 R1.n-1.keys Rn.key由于交換后新的根R1 可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無(wú)序區(qū)R1.n-1調(diào)整為堆。然后再次將 R1.n-1 中關(guān)鍵字最大的記錄 R1 和該區(qū)間的最后一個(gè)記錄Rn-1交換，由此得到新的無(wú)序區(qū) R1.n-2和有序區(qū) Rn-1.n ，且仍滿

12、足關(guān)系 R1.n- 2.keysRn-1.n.keys ，同樣要將 R1.n-2 調(diào)整為堆。11最新 料推薦直到無(wú)序區(qū)只有一個(gè)元素 止。（2 ）大根堆排序算法的基本操作： 初始化操作：將R1.n 構(gòu)造 初始堆； 每一趟排序的基本操作：將當(dāng)前無(wú)序區(qū)的堆 R1 和 區(qū) 的最后一個(gè) 交 ，然后將新的無(wú)序區(qū) 整 堆（亦稱重建堆）。注意：只需做 n-1 趟排序， 出 大的 n-1 個(gè)關(guān) 字 即可以使得文件 增有序。用小根堆排序與利用大根堆 似， 只不 其排序 果是 減有序的。 堆排序和直接 排序相反：在任何 刻堆排序中無(wú)序區(qū) 是在有序區(qū)之前， 且有序區(qū)是在原向量的尾部由后往前逐步 大至整個(gè)向量 止12最

13、新 料推薦13最新 料推薦代碼實(shí)現(xiàn)：cppview plaincopy14最新 料推薦1. / 堆排序2.voidHeapSort(intr ,intn)3. 4.5. int i;6. int temp;7.for(i=n/2; i=0; i-)/ 初始建堆，從最后一個(gè)非終端結(jié)點(diǎn)至根結(jié)點(diǎn)8. Sift(r, i, n) ;9.for(i=n-1; i0; i-)/ 重復(fù)執(zhí)行移走堆頂及重建堆的操作10. 11. temp=ri;12. ri=r0;13. r0=temp;14. Sift(r, 0, i-1);15. 16. for (i=0;in;i+)17.coutri ;18.coutn

14、;19. 四 歸并排序二路歸并排序基本思想：將若干個(gè)有序序列進(jìn)行兩兩歸并，直至所有待排序記錄都在一個(gè)有序序列為止。15最新 料推薦一路歸并算法實(shí)現(xiàn)：cppview plaincopy1. / 一次歸并2.voidMerge(intr,intr1,ints,intm,intt)3. 4.5. int i=s;6. int j=m+1;7. int k=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)/ 若第

15、一個(gè)子序列沒處理完，則進(jìn)行收尾處理18. r1k+=ri+;19. else20.while(j=t)/ 若第二個(gè)子序列沒處理完，則進(jìn)行收尾處理21. r1k+=rj+;16最新 料推薦22.cppview plaincopy1. / 一趟歸并2.voidMergePass(intr ,intr1 ,intn,inth)3. 4. int i=0;5. int k;6.7.while(i=n-2*h)/ 待歸并記錄至少有兩個(gè)長(zhǎng)度為h 的子序列8. 9. Merge(r, r1, i, i+h-1, i+2*h-1);10. i+=2*h;11. 12. if (in-h)17最新 料推薦13.

16、Merge(r, r1, i, i+h-1, n);/待歸并序列中有一個(gè)長(zhǎng)度小于h14.else for (k=i; k=n; k+)/待歸并序列中只剩一個(gè)子序列15. r1k=rk;16. 17.18. / 歸并排序的非遞歸算法19.voidMergeSort1(intr ,intr1 ,intn )20. 21. int h=1;22. int i;23.24. while (hn)25. 26.MergePass(r, r1, n-1, h);/ 歸并27. h=2*h;28. MergePass(r1, r, n-1, h);29. h=2*h;30. 31. for (i=0;in;i+)32.coutri ;33. cout n ;34. 下面看看二路歸并排序的遞歸實(shí)現(xiàn)18最新 料推薦cppview plaincopy1. / 歸并排序的遞歸算法2.voidMergeSort2(