八大排序算法 轉

概述

排序有內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。

我們這里說說八大排序就是內部排序。

當n較大，則應采用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序序。

快速排序：是目前基于比較的內部排序中被認為是最好的方法，當待排序的關鍵字是隨機分布時，快速排序的平均時間最短；

1.插入排序—直接插入排序(Straight Insertion Sort)

基本思想:

將一個記錄插入到已排序好的有序表中，從而得到一個新，記錄數增1的有序表。即：先將序列的第1個記錄看成是一個有序的子序列，然后從第2個記錄逐個進行插入，直至整個序列有序為止。

要點：設立哨兵，作為臨時存儲和判斷數組邊界之用。

直接插入排序示例：

如果碰見一個和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩定的。

算法的實現：

1. void
2. for(intj=0;j<8;j++){
3. cout<<a[j]<<"";
4. }
5. cout<<endl;
6. }
9. voidInsertSort(inta[],intn)
10. {
11. for(inti=1;i<n;i++){
12. if(a[i]<a[i-1]){//若第i個元素大于i-1元素，直接插入。小于的話，移動有序表后插入
13. intj=i-1;
14. intx=a[i];//復制為哨兵，即存儲待排序元素
15. a[i]=a[i-1];//先后移一個元素
16. while(x<a[j]){//查找在有序表的插入位置
17. a[j+1]=a[j];
18. j--;//元素后移
19. }
20. a[j+1]=x;//插入到正確位置
21. }
22. print(a,n,i);//打印每趟排序的結果
23. }
25. }
27. intmain(){
28. inta[8]={3,1,5,7,2,4,9,6};
29. InsertSort(a,8);
30. print(a,8,8);
31. }

效率：

時間復雜度：O（n^2）.

其他的插入排序有二分插入排序，2-路插入排序。

2. 插入排序—希爾排序（Shell`s Sort）

希爾排序是1959 年由D.L.Shell 提出來的，相對直接排序有較大的改進。希爾排序又叫縮小增量排序

基本思想：

先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。

操作方法：

1. 選擇一個增量序列t1，t2，&hellip;，tk，其中ti>tj，tk=1；
2. 按增量序列個數k，對序列進行k 趟排序；
3. 每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序。僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度。

希爾排序的示例：

算法實現：

我們簡單處理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1}n為要排序數的個數

即：先將要排序的一組記錄按某個增量d（n/2,n為要排序數的個數）分成若干組子序列，每組中記錄的下標相差d.對每組中全部元素進行直接插入排序，然后再用一個較小的增量（d/2）對它進行分組，在每組中再進行直接插入排序。繼續不斷縮小增量直至為1，最后使用直接插入排序完成排序。

1. voidprint(inta[],intn,inti){
2. cout<<i<<":";
3. for(intj=0;j<8;j++){
4. cout<<a[j]<<"";
5. }
6. cout<<endl;
7. }
8. /**
9. *直接插入排序的一般形式
10. *
11. *@paramintdk縮小增量，如果是直接插入排序，dk=1
12. *
13. */
15. voidShellInsertSort(inta[],intn,intdk)
16. {
17. for(inti=dk;i<n;++i){
18. if(a[i]<a[i-dk]){//若第i個元素大于i-1元素，直接插入。小于的話，移動有序表后插入
19. intj=i-dk;
20. intx=a[i];//復制為哨兵，即存儲待排序元素
21. a[i]=a[i-dk];//首先后移一個元素
22. while(x<a[j]){//查找在有序表的插入位置
23. a[j+dk]=a[j];
24. j-=dk;//元素后移
25. }
26. a[j+dk]=x;//插入到正確位置
27. }
28. print(a,n,i);
29. }
31. }
33. /**
34. *先按增量d（n/2,n為要排序數的個數進行希爾排序
35. *
36. */
37. voidshellSort(inta[],intn){
39. intdk=n/2;
40. while(dk>=1){
41. ShellInsertSort(a,n,dk);
42. dk=dk/2;
43. }
44. }
45. intmain(){
46. inta[8]={3,1,5,7,2,4,9,6};
47. //ShellInsertSort(a,8,1);//直接插入排序
48. shellSort(a,8);//希爾插入排序
49. print(a,8,8);
50. }

3. 選擇排序—簡單選擇排序（Simple Selection Sort）

基本思想：

在要排序的一組數中，選出最小（或者最大）的一個數與第1個位置的數交換；然后在剩下的數當中再找最小（或者最大）的與第2個位置的數交換，依次類推，直到第n-1個元素（倒數第二個數）和第n個元素（最后一個數）比較為止。

簡單選擇排序的示例：

操作方法：

第一趟，從n 個記錄中找出關鍵碼最小的記錄與第一個記錄交換；

第二趟，從第二個記錄開始的n-1 個記錄中再選出關鍵碼最小的記錄與第二個記錄交換；

以此類推.....

第i 趟，則從第i 個記錄開始的n-i+1 個記錄中選出關鍵碼最小的記錄與第i 個記錄交換，

直到整個序列按關鍵碼有序。

算法實現：

1. voidprint(inta[],intn,inti){
2. cout<<"第"<<i+1<<"趟:";
3. for(intj=0;j<8;j++){
4. cout<<a[j]<<"";
5. }
6. cout<<endl;
7. }
8. /**
9. *數組的最小值
10. *
11. *@returnint數組的鍵值
12. */
13. intSelectMinKey(inta[],intn,inti)
14. {
15. intk=i;
16. for(intj=i+1;j<n;++j){
17. if(a[k]>a[j])k=j;
18. }
19. returnk;
20. }
22. /**
23. *選擇排序
24. *
25. */
26. voidselectSort(inta[],intn){
27. intkey,tmp;
28. for(inti=0;i<n;++i){
29. key=SelectMinKey(a,n,i);//選擇最小的元素
30. if(key!=i){
31. tmp=a[i];a[i]=a[key];a[key]=tmp;//最小元素與第i位置元素互換
32. }
33. print(a,n,i);
34. }
35. }
36. intmain(){
37. inta[8]={3,1,5,7,2,4,9,6};
38. cout<<"初始值：";
39. for(intj=0;j<8;j++){
40. cout<<a[j]<<"";
41. }
42. cout<<endl<<endl;
43. selectSort(a,8);
44. print(a,8,8);
45. }

簡單選擇排序的改進——二元選擇排序

簡單選擇排序，每趟循環只能確定一個元素排序后的定位。我們可以考慮改進為每趟循環確定兩個元素（當前趟最大和最小記錄）的位置,從而減少排序所需的循環次數。改進后對n個數據進行排序，最多只需進行[n/2]趟循環即可。具體實現如下：

1. voidSelectSort(intr[],intn){
2. inti,j,min,max,tmp;
3. for(i=1;i<=n/2;i++){
4. //做不超過n/2趟選擇排序
5. min=i;max=i;//分別記錄最大和最小關鍵字記錄位置
6. for(j=i+1;j<=n-i;j++){
7. if(r[j]>r[max]){
8. max=j;continue;
9. }
10. if(r[j]<r[min]){
11. min=j;
12. }
13. }
14. //該交換操作還可分情況討論以提高效率
15. tmp=r[i-1];r[i-1]=r[min];r[min]=tmp;
16. tmp=r[n-i];r[n-i]=r[max];r[max]=tmp;
18. }
19. }

4. 選擇排序—堆排序（Heap Sort）

堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。

基本思想：

堆的定義如下：具有n個元素的序列（k1,k2,...,kn),當且僅當滿足

時稱之為堆。由堆的定義可以看出，堆頂元素（即第一個元素）必為最小項（小頂堆）。若以一維數組存儲一個堆，則堆對應一棵完全二叉樹，且所有非葉結點的值均不大于(或不小于)其子女的值，根結點（堆頂元素）的值是最小(或最大)的。如：

（a）大頂堆序列：（96, 83,27,38,11,09)

(b) 小頂堆序列：（12，36，24，85，47，30，53，91）

初始時把要排序的n個數的序列看作是一棵順序存儲的二叉樹（一維數組存儲二叉樹），調整它們的存儲序，使之成為一個堆，將堆頂元素輸出，得到n 個元素中最小(或最大)的元素，這時堆的根節點的數最小（或者最大）。然后對前面(n-1)個元素重新調整使之成為堆，輸出堆頂元素，得到n 個元素中次小(或次大)的元素。依此類推，直到只有兩個節點的堆，并對它們作交換，最后得到有n個節點的有序序列。稱這個過程為堆排序。

因此，實現堆排序需解決兩個問題：1. 如何將n 個待排序的數建成堆；2. 輸出堆頂元素后，怎樣調整剩余n-1 個元素，使其成為一個新堆。

首先討論第二個問題：輸出堆頂元素后，對剩余n-1元素重新建成堆的調整過程。調整小頂堆的方法：

1）設有m 個元素的堆，輸出堆頂元素后，剩下m-1 個元素。將堆底元素送入堆頂（（最后一個元素與堆頂進行交換）