c語言各種排序法詳解

1、一 插入排序1.1 直接插入排序基本思想：每次將一個待排序額記錄按其關鍵碼的大小插入到一個已經(jīng)排好序的有序序列中，直到全部記錄排好序。圖解：代碼實現(xiàn)：cppview plaincopy1. / 直接順序排序2.void InsertSort(intr,int n)3. 4. for ( int i=2;i<n;i+)5. 6.r0=ri;/ 設置哨兵7.for ( intj=i-1;r0<rj;j-)/ 尋找插入位置8.rj+1=rj;/ 記錄后移9. rj+1=r0;10. 11. for ( int k=1;k<n;k+)12.cout<<rk<<

2、"" ;13. cout<< "n" ;14. 1.2 希爾排序基本思想是： 先將整個待排序記錄序列分割成若干個子序列，在在序列內(nèi)分別進行直接插入排序，待整個序列基本有序時，再對全體記錄進行一次直接插入排序。圖解：代碼實現(xiàn)：cppview plaincopy1.<spanstyle= "font-size:14px;">/ 希爾排序2.void ShellSort(int r, intn)3. 4. int i;5. int d;6. int j;7.for (d=n/2;d>=1;d=d/2)/ 以增量

3、為d 進行直接插入排序8. 9. for (i=d+1;i<n;i+)10. 11.r0=ri;/ 暫存被插入記錄12.for (j=i-d;j>0&&r0<rj;j=j-d)13.rj+d=rj;/ 記錄后移d 個位置14. rj+d=r0;15. 16. 17. for (i=1;i<n;i+)18.cout<<ri<<"" ;19. cout<< "n" ;20. </span>二 交換排序2.1 起泡排序起泡排序是交換排序中最簡單的排序方法，其基本思想是：兩兩

4、比較相鄰記錄的關鍵碼，如果反序則交換，直到?jīng)]有反序的記錄為止。圖解：代碼實現(xiàn)：cppview plaincopy1.<spanstyle= "font-size:14px;">/ 起泡排序2.void BubbleSort(int r, intn)3. 4. int temp;5. int exchange;6. int bound;7.exchange=n-1;/ 第一趟起泡排序的范圍是r0到 rn-18. while (exchange) / 僅當上一趟排序有記錄交換才進行本趟排序9. 10. bound=exchange;11. exchange=0;12

5、.for ( intj=0;j<bound;j+)/ 一趟起泡排序13. if (rj>rj+1)14. 15. temp=rj;16. rj=rj+1;17. rj+1=temp;18. exchange=j; / 記錄每一次發(fā)生記錄交換的位置19. 20. 21. for ( int i=0;i<n;i+)22.cout<<ri<<"" ;23. cout<< "n" ;24. </span>2.2 快速排序基本思想 :通過一趟 排序?qū)⒁判虻?數(shù)據(jù)分割 成獨立的兩部分， 其中一部分的

6、所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以 遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。圖解：代碼實現(xiàn)：cppview plaincopy1. / 快速排序一次劃分2.int Partition(int r,int first,int end)3. 4.int i=first;/ 初始化5. int j=end;6. int temp;7. while (i<j)8. 9. while (i<j&&ri<=rj)10. j-; / 右側(cè)掃描11. if (i<j)12. 13. temp=ri;/

7、將較小記錄交換到前面14. ri=rj;15. rj=temp;16. i+;17. 18. while (i<j&&ri<=rj)19. i+; / 左側(cè)掃描20. if (i<j)21. 22. temp=rj;23. rj=ri;24. ri=temp;/ 將較大記錄交換到后面25. j-;26. 27. 28. return i; /i 為軸值記錄的最終位置29. 30. / 快速排序31.void QuickSort(intr,intfirst,intend)32. 33. if (first<end)34. / 遞歸結(jié)束35.int pivo

8、t=Partition(r,first,end);/ 一次劃分36.QuickSort(r,first,pivot-1);/ 遞歸地對左側(cè)子序列進行快速排序37.QuickSort(r,pivot+1,end);/ 遞歸地對右側(cè)子序列進行快速排序38. 39. 三 選擇排序3.1 簡單選擇排序基本思想：設所排序序列的記錄個數(shù)為 n。i取 1,2, ,n-1, 從所有中找出排序碼最小的記錄，與第 i 個記錄交換。執(zhí)行 n-1 趟n-i+1 個記錄（Ri,Ri+1,Rn）后就完成了記錄序列的排序。圖解：代碼實現(xiàn)：cppview plaincopy1. / 簡單選擇排序2.void SelectSo

9、rt(intr,int n)3. 4. int i;5. int j;6. int index;7. int temp;8.for (i=0;i<n-1;i+)/ 對 n 個記錄進行n-1 趟簡單選擇排序9. 10. index=i;11.for (j=i+1;j<n;j+)/ 在無序區(qū)中選取最小記錄12. if (rj<rindex)13. index=j;14. if (index!=i)15. 16. temp=ri;17. ri=rindex;18. rindex=temp;19. 20. 21. for (i=0;i<n;i+)22.cout<<r

10、i<<"" ;23. cout<< "n" ;24. 3.2 堆排序堆的定義堆是具有下列性質(zhì)的完全二叉樹：每個結(jié)點的值都小于或等于其左右孩子結(jié)點的值（ 小根堆）；或者每個結(jié)點的值都大于或等于其左右孩子結(jié)點的值（ 大根堆）。大根堆和小根堆：根結(jié)點（亦稱為堆頂）的 關鍵字是堆里所有結(jié)點關鍵字中最小者的堆稱為小根堆，又稱最小堆 。根結(jié)點（亦稱為堆頂） 的關鍵字是堆里所有結(jié)點關鍵字中最大者，稱為大根堆，又稱最大堆。注意：堆中任一子樹亦是堆。以上討論的堆實際上是 二叉堆（BinaryHeap ），類似地可定義k 叉堆。假設當前要篩選結(jié)點的編

11、號為k，堆中最后一個結(jié)點的編號為m，并且結(jié)點 k 的左右子樹均是堆（即 rk+1 rm 滿足堆的條件），則篩選算法用偽代碼可描述為：具體的篩選代碼如下：cppview plaincopy1. / 篩選法調(diào)整堆2.void Sift(intr,intk, intm)3. 4. int i;5. int j;6. int temp;7. i=k;8.j=2*i+1;/ 置 i 為要篩的結(jié)點，j 為 i 的左孩子9. while (j<=m) / 篩選還沒有進行到葉子10. 11. if (j<m&&rj<rj+1)12. j+; / 比較 i 的左右孩子， j 為

12、較大者13.if (ri>rj)break ; / 根結(jié)點已經(jīng)大于左右孩子中的較大者14. else15. 16. temp=ri;17. ri=rj;18.rj=temp;/ 將根結(jié)點與結(jié)點j 交換19. i=j;20. j=2*i+1; / 被篩結(jié)點位于原來結(jié)點 j 的位置21. 22. 23. 堆排序堆排序的基本思想是：首先將待排序的記錄序列構(gòu)造成一個堆，此時，選出了堆中所有記錄的最大者即堆頂記錄， 然后將它從堆中移走 （通常將堆頂記錄和堆中最后一個記錄交換），并將剩余的記錄再調(diào)整成堆，這樣又找出了次大的記錄，以此類推，直到堆中只有一個記錄為止。（ 1）用大根堆排序的基本思想 先將

13、初始文件 R1.n 建成一個大根堆，此堆為初始的無序區(qū) 再將關鍵字最大的記錄R1 （即堆頂）和無序區(qū)的最后一個記錄Rn 交換，由此得到新的無序區(qū) R1.n-1 和有序區(qū) Rn ，且滿足 R1.n- 1.keys Rn.key由于交換后新的根R1 可能違反堆性質(zhì)，故應將當前無序區(qū)R1.n-1 調(diào)整為堆。然后再次將 R1.n-1 中關鍵字最大的記錄R1 和該區(qū)間的最后一個記錄Rn-1 交換，由此得到新的無序區(qū) R1.n-2 和有序區(qū) Rn-1.n ，且仍滿足關系 R1.n- 2.keys Rn-1.n.keys ，同樣要將 R1.n-2 調(diào)整為堆。直到無序區(qū)只有一個元素為止。（ 2）大根堆排序算法

14、的基本操作： 初始化操作：將R1.n 構(gòu)造為初始堆； 每一趟排序的基本操作： 將當前無序區(qū)的堆頂記錄 R1 和該區(qū)間的最后一個記錄交換，然后將新的無序區(qū)調(diào)整為堆（亦稱重建堆）。注意：只需做 n-1 趟排序，選出較大的n-1 個關鍵字即可以使得文件遞增有序。用小根堆排序與利用大根堆類似，只不過其排序結(jié)果是遞減有序的。堆排序和直接 選擇排序相反：在任何時刻堆排序中無序區(qū)總是在有序區(qū)之前，且有序區(qū)是在原向量的尾部由后往前逐步擴大至整個向量為止代碼實現(xiàn)：cppview plaincopy1. / 堆排序2.void HeapSort(int r,int n)3. 4. int i;5. int tem

15、p;6.for (i=n/2;i>=0;i-)/ 初始建堆，從最后一個非終端結(jié)點至根結(jié)點7. Sift(r,i,n);8.for (i=n-1;i>0;i-)/ 重復執(zhí)行移走堆頂及重建堆的操作9. 10. temp=ri;11. ri=r0;12. r0=temp;13. Sift(r,0,i-1);14. 15. for (i=0;i<n;i+)16.cout<<ri<<"" ;17. cout<< "n" ;18. 四 歸并排序二路歸并排序基本思想：將若干個有序序列進行兩兩歸并，直至所有待排序記錄

16、都在一個有序序列為止。一路歸并算法實現(xiàn)：cppview plaincopy1. / 一次歸并2.void Merge( intr,intr1,ints, intm,intt)3. 4. int i=s;5. int j=m+1;6. int k=s;7. while (i<=m&&j<=t)8. 9. if (ri<=rj)10.r1k+=ri+;/ 取 ri和 rj中較小者放入r1k11. else12. r1k+=rj+;13. 14. if (i<=m)15. while (i<=m) / 若第一個子序列沒處理完，則進行收尾處理16. r1k

17、+=ri+;17. else18. while (j<=t) / 若第二個子序列沒處理完，則進行收尾處理19. r1k+=rj+;20. cppview plaincopy1. / 一趟歸并2.void MergePass( intr,intr1,int n, inth)3. 4. int i=0;5. int k;6.while(i<=n-2*h)/ 待歸并記錄至少有兩個長度為h 的子序列7. 8. Merge(r,r1,i,i+h-1,i+2*h-1);9. i+=2*h;10. 11. if (i<n-h)12.Merge(r,r1,i,i+h-1,n);/ 待歸并序列

18、中有一個長度小于h13. elsefor (k=i;k<=n;k+)/ 待歸并序列中只剩一個子序列14. r1k=rk;15. 16. / 歸并排序的非遞歸算法17.void MergeSort1(intr,int r1,intn)18. 19. int h=1;20. int i;21. while (h<n)22. 23.MergePass(r,r1,n-1,h);/ 歸并24. h=2*h;25. MergePass(r1,r,n-1,h);26. h=2*h;27. 28. for (i=0;i<n;i+)29.cout<<ri<<"" ;30. cout<< "n" ;31. 下面看看二路歸并排序的遞