所謂排序，就是要整理文件中的記錄，使之按關鍵字遞增(或遞減)次序排列起來。其確切定義如下：
輸入：n個記錄R1，R2，…，Rn，其相應的關鍵字分別為K1，K2，…，Kn。
輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。
排序的時間開銷可用算法執行中的數據比較次數與數據移動次數來衡量。基本的排序算法有如下幾種：交換排序（冒泡排序、快速排序）、選擇排序（直接選擇排序、堆排序）、插入排序（直接插入排序、希爾排序）、歸并排序、分配排序（基數排序、箱排序、計數排序）。下面依次列出各種算法的代碼，并進行簡要分析。分配排序算法的代碼沒有列出。
（1）快速排序：快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的策略，通常稱其為分治法(Divide-and-ConquerMethod)。最好、平均復雜度都為O(nlogn)，最壞為O(n^2)。
void quick_sort1(int a[],int l,int r) { if(l >= r) return; int i, j, p; i = l-1, j = l,p = a[r]; while(j < r) { if(a[j] < p) swap(a[++i], a[j]); j++; } swap(a[++i], a[r]); quick_sort1(a, l, i-1); quick_sort1(a, i+1, r); } 《算法導論》一書中，給出了這個程序的偽代碼。當數組元素相等、逆序、順序排列時，調用這個程序會導致棧溢出。因為每次劃分都是最壞壞分。可以改進一下。上述程序每次選的劃分基準元素都是固定的，如果是隨機產生的，那么可以大大降低出現最壞劃分的概率。
void quick_sort2(int a[],int l,int r) { if(l >= r) return; int i,j,p; i = l-1,j = l; p=l + rand()%(r-l); //隨機產生[l,r)之間的數 swap(a[p], a[r]); p = a[r]; while(j < r) { if(a[j] < p) swap(a[++i], a[j]); j++; } swap(a[++i], a[r]); quick_sort2(a, l, i-1); quick_sort2(a, i+1, r); } 但是，當數組元素相等時，還是出現了棧溢出。可以做如下調整。
void quick_sort3(int a[],int l,int r) { if(l >= r) return; int i,j,p; i = l-1, j = r, p = a[r]; while(1) { do { i++; } while(a[i] < p && i < r); do { j--; } while(a[j] > p && j > l); if(i >= j) break; swap(a[i], a[j]); } swap(a[i],a[r]); quick_sort3(a, l, i-1); quick_sort3(a, i+1, r); } 但是，當數組元素順序，逆序時，同樣出現了棧溢出。若將兩者結合起來，就可以盡量避免棧溢出。
void quick_sort4(int a[],int l,int r) { if(l >= r) return; int i,j,p; i = l-1, j = r; p = l + rand()%(r-l); swap(a[p],a[r]); p = a[r]; while(1) { do { i++; } while(a[i] < p && i < r); do { j--; } while(a[j] > p && j > l); if(i >= j) break; swap(a[i], a[j]); } swap(a[i], a[r]); quick_sort4(a, l, i-1); quick_sort4(a, i+1, r); } （2）冒泡排序：兩兩比較待排序記錄的關鍵字，發現兩個記錄的次序相反時即進行交換，直到沒有反序的記錄為止。
void bubble_sort1(int a[],int n) { int i,j; for(i = 0; i < n-1; i++) { for(j = i+1; j < n; j++) { if(a[i] > a[j]) swap(a[i], a[j]); } } } 可以稍作改進，當數組數元素順序時，時間復雜度為O(n)。加入一個變量，如果在一遍掃描中，沒有出現交換，那么結束排序，因為數組已排好序了。
void bubble_sort2(int a[],int n) { int i,j; for(i = 0; i < n-1; i++) { bool exchange = false; for(j = i+1; j < n; j++) { if(a[i] > a[j]) { exchange = true; swap(a[i], a[j]); } } if(exchange == false) break; } } 經網友指出，上面這個冒泡排序有問題，無法得到正確結果。下面引自網友的正確寫法：
void bubble_sort2(int a[],int n) { int i,j; for(i = 0;i < n-1; i++) { bool exchange = false; for(j = n-1;j > i; j--) { if(a[j-1] > a[j]) { exchange = true; swap(a[j-1], a[j]); } } if(exchange == false) break; } } （3）直接選擇排序：每一趟從待排序的記錄中選出關鍵字最小的記錄，順序放在已排好序的子文件的最后，直到全部記錄排序完畢。
void select_sort1(int a[],int n) { int i,j; for(i = 0; i < n-1; i++) { int min = i; for(j = i+1; j < n; j++) { if(a[j] < a[min]) min = j; } if(min != i) swap(a[i], a[min]); } } （4）堆排序：根據輸入數據，利用堆的調整算法形成初始堆，然后交換根元素與尾元素，總的元素個數減1，然后從根往下調整。堆排序的最好、最壞、平均時間復雜度都為O(nlogn)
void heap_siftdown(int a[],int n,int p) //調整算法 { int i = p,j = i*2+1; int tmp = a[i]; while(j < n) { if(j+1 < n && a[j] < a[j+1]) j++; if(a[j] <= tmp) break; else { a[i] = a[j]; i = j;j = j*2+1; } } a[i] = tmp; } void heap_sort1(int a[],int n) { int i; for(i = (n-1)/2; i >= 0;i--) heap_siftdown(a, n, i); for(i = n-1;i >= 0; i--) { swap(a[i], a[0]); heap_siftdown(a, i, 0); } } （5）直接插入排序：每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子文件中的適當位置，直到全部記錄插入完成為止。當數組已經排好序，直接插入排序的時間復雜度為O(n)
void insert_sort1(int a[],int n) { int i,j; for(i = 1; i < n; i++) { for(j = i; j > 0 && a[j]<a[j-1]; j--) swap(a[j-1], a[j]); } }
如果將交換函數展開，可以加快排序的速度。
void insert_sort2(int a[],int n) { int i,j; for(i = 1; i < n; i++) { for(j = i; j > 0 && a[j] < a[j-1]; j--) { int t = a[j-1]; a[j-1] = a[j]; a[j] = t; } } } 可以進一步改進，insert_sort2的算法不斷給t賦值，可以將賦值語句移到循環外面。
void insert_sort3(int a[],int n) { int i,j; for(i = 1;i < n; i++) { int t = a[i]; for(j = i; j > 0 && a[j-1] > t; j--) a[j] = a[j-1]; a[j] = t; } } （6）希爾排序：先取一個小于n的整數d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為dl的倍數的記錄放在同一個組中。先在各組內進行直接插人排序；然后，取第二個增量d2<d1重復上述的分組和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止。
最后一遍的增量必須是1，其實是就是調用直接插入排序算法。
void shell_sort1(int a[],int n) { int i = n; do{ i = i/3 + 1; shell_pass1(a, n, i); }while(i > 1); } void shell_pass1(int a[],int n,int inc) //inc為1時，其實就是直接插入排序 { int i,j; for(i = inc; i < n; i++) { int t=a[i]; for(j = i;j >= inc && a[j-inc] > t; j-= inc) a[j] = a[j-inc]; a[j] = t; } } （7）歸并排序：利用"歸并"技術來進行排序。歸并是指將若干個已排序的子文件合并成一個有序的文件。可以用于外排序。
void merge_sort1(int a[],int b[],int l,int r) { if(l >= r) return; int m = (l+r)/2; merge_sort1(a, b, l, m); merge_sort1(a, b, m+1, r); merge1(a, b, l, m, r); } void merge1(int a[],int b[],int l,int m,int r) { int i,j,k; for(i = l; i <= r; i++) b[i] = a[i]; i = l; j = m+1; k = l; while(i <= m && j <= r) { if(b[i] <= b[j]) a[k++] = b[i++]; else a[k++] = b[j++]; } while(i <= m) a[k++] = b[i++]; while(j <= r) a[k++] = b[j++]; } 給出上述算法的程序的測試驅動程序及兩個輔助程序。要測試某種排序算法，只需將注釋去掉即可。
#include <iostream> #include <ctime> using namespace std; const int N = 100; int a[N]; int b[N]; int main() { int i; srand(time(0)); //for(i=0;i<N;i++) // a[i]= N-i; for(i = 0;i < N; i++) a[i]=rand()%N; long start,end; start = clock(); //quick_sort1(a,0,N-1); //quick_sort2(a,0,N-1); //quick_sort3(a,0,N-1); //quick_sort4(a,0,N-1); //bubble_sort1(a,N); //bubble_sort2(a,N); //merge_sort1(a,b,0,N-1); //heap_sort1(a,N); //shell_sort1(a,N); //select_sort1(a,N); //insert_sort1(a,N); //insert_sort2(a,N); //insert_sort3(a,N); end = clock(); print_array(a, N); cout<<"total time is : "<<(end-start)/1000.0<<'s'<<endl; return 0; } void swap(int a[],int i,int j) //交換元素 { int t = a[i]; a[i] = a[j]; a[j] = t; } void print_array(int a[],int n) //打印元素值 { for(int i = 0; i < n; i++) { cout<<a[i]<<' '; if(i%10==0 && i!=0) cout<<endl; } cout<<endl; }
新聞熱點
疑難解答
圖片精選
