首先來看一下排序算法的一些相關概念：
1、穩定排序和非穩定排序
簡單地說就是所有相等的數經過某種排序方法后，仍能保持它們在排序之前的相對次序，我們就說這種排序方法是穩定的。反之，就是非穩定的。
比如：一組數排序前是a1,a2,a3,a4,a5，其中a2=a4，經過某種排序后為a1,a2,a4,a3,a5，則我們說這種排序是穩定的，因為a2排序前在a4的前面，排序后它還是在a4的前面。假如變成a1,a4,a2,a3,a5就不是穩定的了。
2、內排序和外排序
在排序過程中，所有需要排序的數都在內存，并在內存中調整它們的存儲順序，稱為內排序；
在排序過程中，只有部分數被調入內存，并借助內存調整數在外存中的存放順序排序方法稱為外排序。
3、算法的時間復雜度和空間復雜度
所謂算法的時間復雜度，是指執行算法所需要的計算工作量。
一個算法的空間復雜度，一般是指執行這個算法所需要的內存空間。
接下來我們實際來看幾大排序算法的具體C語言實現：
冒泡排序 (Bubble Sort)
如果序列是從小到大排列好的，那么任意兩個相鄰元素，都應該滿足a[i-1] <= a[i]的關系。在冒泡排序時，我們從右向左遍歷數組，比較相鄰的兩個元素。如果兩個元素的順序是錯的，那么就交換這兩個元素。如果兩個元素的順序是正確的，則不做交換。經過一次遍歷，我們可以保證最小的元素(泡泡)處于最左邊的位置。
經過一次遍歷，冒泡排序并不能保證所有的元素已經按照從小到大的排列好。因此，我們需要重新從右向左遍歷數組元素，并進行冒泡排序。這一次遍歷，我們不用考慮最左端的元素。然后繼續進行最多為n-1次的遍歷。
如果某次遍歷過程中，元素都沒有發生交換，那么說明數組已經排序好，可以中止停止排序。最壞的情況是在起始數組中，最大的元素位于最左邊，那么冒泡算法必須經過n-1次遍歷才能將數組排列好，而不能提前完成排序。
/*By Vamei*//*swap the neighbors if out of order*/void bubble_sort(int a[], int ac){ /*use swap*/ int i,j; int sign; for (j = 0; j < ac-1; j++) { sign = 0; for(i = ac-1; i > j; i--) { if(a[i-1] > a[i]) { sign = 1; swap(a+i, a+i-1); } } if (sign == 0) break; }}插入排序 (Insertion Sort)
假設在新生報到的時候，我們將新生按照身高排好隊(也就是排序)。如果這時有一名學生加入，我們將該名學生加入到隊尾。如果這名學生比前面的學生低，那么就讓該學生和前面的學生交換位置。這名學生最終會換到應在的位置。這就是插入排序的基本原理。
對于起始數組來說，我們認為最初，有一名學生，也就是最左邊的元素(i=0)，構成一個有序的隊伍。
隨后有第二個學生(i=1)加入隊伍，第二名學生交換到應在的位置；隨后第三個學生加入隊伍，第三名學生交換到應在的位置…… 當n個學生都加入隊伍時，我們的排序就完成了。
/*By Vamei*//*insert the next element into the sorted part*/void insert_sort(int a[], int ac){ /*use swap*/ int i,j; for (j=1; j < ac; j++) { i = j-1; while((i>=0) && (a[i+1] < a[i])) { swap(a+i+1, a+i); i--; } }}選擇排序 (Selection Sort)
排序的最終結果：任何一個元素都不大于位于它右邊的元素 (a[i] <= a[j], if i <= j)。所以，在有序序列中，最小的元素排在最左的位置，第二小的元素排在i=1的位置…… 最大的元素排在最后。
選擇排序是先找到起始數組中最小的元素，將它交換到i=0；然后尋找剩下元素中最小的元素，將它交換到i=1的位置…… 直到找到第二大的元素，將它交換到n-2的位置。這時，整個數組的排序完成。
/*By Vamei*//*find the smallest of the rest, then append to the sorted part*/void select_sort(int a[], int ac) { /*use swap*/ int i,j; int min_idx; for (j = 0; j < ac-1; j++) { min_idx = j; for (i = j+1; i < ac; i++) { if (a[i] < a[min_idx]) { min_idx = i; } } swap(a+j, a+min_idx); } }希爾排序 （Shell Sort）
我們在冒泡排序中提到，最壞的情況發生在大的元素位于數組的起始。這些位于數組起始的大元素需要多次遍歷，才能交換到隊尾。這樣的元素被稱為烏龜(turtle)。
烏龜元素的原因在于，冒泡排序總是相鄰的兩個元素比較并交換。所以每次從右向左遍歷，大元素只能向右移動一位。(小的元素位于隊尾，被稱為兔子(rabbit)元素，它們可以很快的交換到隊首。)
希爾排序是以更大的間隔來比較和交換元素，這樣，大的元素在交換的時候，可以向右移動不止一個位置，從而更快的移動烏龜元素。比如，可以將數組分為4個子數組（i=4k, i=4k+1, i=4k+2, i=4k+3），對每個子數組進行冒泡排序。比如子數組i=0，4，8，12...。此時，每次交換的間隔為4。
完成對四個子數組的排序后，數組的順序并不一定能排列好。希爾排序會不斷減小間隔，重新形成子數組，并對子數組冒泡排序…… 當間隔減小為1時，就相當于對整個數組進行了一次冒泡排序。隨后，數組的順序就排列好了。
希爾排序不止可以配合冒泡排序，還可以配合其他的排序方法完成。
/*By Vamei*//*quickly sort the turtles at the tail of the array*/void shell_sort(int a[], int ac){ int step; int i,j; int nsub; int *sub; /* initialize step */ step = 1; while(step < ac) step = 3*step + 1; /* when step becomes 1, it's equivalent to the bubble sort*/ while(step > 1) { /* step will go down to 1 at most */ step = step/3 + 1; for(i=0; i<step; i++) { /* pick an element every step, and combine into a sub-array */ nsub = (ac - i - 1)/step + 1; sub = (int *) malloc(sizeof(int)*nsub); for(j=0; j<nsub; j++) { sub[j] = a[i+j*step]; } /* sort the sub-array by bubble sorting. It could be other sorting methods */ bubble_sort(sub, nsub); /* put back the sub-array*/ for(j=0; j<nsub; j++) { a[i+j*step] = sub[j]; } /* free sub-array */ free(sub); } }}Shell Sorting依賴于間隔(step)的選取。一個常見的選擇是將本次間隔設置為上次間隔的1/1.3。見參考書籍。
歸并排序 (Merge Sort)
如果我們要將一副撲克按照數字大小排序。此前已經有兩個人分別將其中的一半排好順序。那么我們可以將這兩堆撲克向上放好，假設小的牌在上面。此時，我們將看到牌堆中最上的兩張牌。
我們取兩張牌中小的那張取出放在手中。兩個牌堆中又是兩張牌暴露在最上面，繼續取小的那張放在手中…… 直到所有的牌都放入手中，那么整副牌就排好順序了。這就是歸并排序。
下面的實現中，使用遞歸：
/*By Vamei*//*recursively merge two sorted arrays*/void merge_sort(int *a, int ac){ int i, j, k; int ac1, ac2; int *ah1, *ah2; int *container; /*base case*/ if (ac <= 1) return; /*split the array into two*/ ac1 = ac/2; ac2 = ac - ac1; ah1 = a + 0; ah2 = a + ac1; /*recursion*/ merge_sort(ah1, ac1); merge_sort(ah2, ac2); /*merge*/ i = 0; j = 0; k = 0; container = (int *) malloc(sizeof(int)*ac); while(i<ac1 && j<ac2) { if (ah1[i] <= ah2[j]) { container[k++] = ah1[i++]; } else { container[k++] = ah2[j++]; } } while (i < ac1) { container[k++] = ah1[i++]; } while (j < ac2) { container[k++] = ah2[j++]; } /*copy back the sorted array*/ for(i=0; i<ac; i++) { a[i] = container[i]; } /*free space*/ free(container);}快速排序 (Quick Sort)
我們依然考慮按照身高給學生排序。在快速排序中，我們隨便挑出一個學生，以該學生的身高為參考(pivot)。然后讓比該學生低的站在該學生的右邊，剩下的站在該學生的左邊。
很明顯，所有的學生被分成了兩組。該學生右邊的學生的身高都大于該學生左邊的學生的身高。
我們繼續，在低身高學生組隨便挑出一個學生，將低身高組的學生分為兩組(很低和不那么低)。同樣，將高學生組也分為兩組(不那么高和很高)。
如此繼續細分，直到分組中只有一個學生。當所有的分組中都只有一個學生時，則排序完成。
在下面的實現中，使用遞歸:
/*By Vamei*//*select pivot, put elements (<= pivot) to the left*/void quick_sort(int a[], int ac){ /*use swap*/ /* pivot is a position, all the elements before pivot is smaller or equal to pvalue */ int pivot; /* the position of the element to be tested against pivot */ int sample; /* select a pvalue. Median is supposed to be a good choice, but that will itself take time. here, the pvalue is selected in a very simple wayi: a[ac/2] */ /* store pvalue at a[0] */ swap(a+0, a+ac/2); pivot = 1; /* test each element */ for (sample=1; sample<ac; sample++) { if (a[sample] < a[0]) { swap(a+pivot, a+sample); pivot++; } } /* swap an element (which <= pvalue) with a[0] */ swap(a+0,a+pivot-1); /* base case, if only two elements are in the array, the above pass has already sorted the array */ if (ac<=2) return; else { /* recursion */ quick_sort(a, pivot); quick_sort(a+pivot, ac-pivot); }}理想的pivot是采用分組元素中的中位數。然而尋找中位數的算法需要另行實現。也可以隨機選取元素作為pivot，隨機選取也需要另行實現。為了簡便，我每次都采用中間位置的元素作為pivot。
堆排序 (Heap Sort)
堆(heap)是常見的數據結構。它是一個有優先級的隊列。最常見的堆的實現是一個有限定操作的Complete Binary Tree。這個Complete Binary Tree保持堆的特性，也就是父節點(parent)大于子節點(children)。因此，堆的根節點是所有堆元素中最小的。堆定義有插入節點和刪除根節點操作，這兩個操作都保持堆的特性。
我們可以將無序數組構成一個堆，然后不斷取出根節點，最終構成一個有序數組。
堆的更詳細描述請閱讀參考書目。
下面是堆的數據結構，以及插入節點和刪除根節點操作。你可以很方便的構建堆，并取出根節點，構成有序數組。
/* By Vamei Use an big array to implement heap DECLARE: int heap[MAXSIZE] in calling function heap[0] : total nodes in the heap for a node i, its children are i*2 and i*2+1 (if exists) its parent is i/2 */void insert(int new, int heap[]) { int childIdx, parentIdx; heap[0] = heap[0] + 1; heap[heap[0]] = new; /* recover heap property */ percolate_up(heap);}static void percolate_up(int heap[]) { int lightIdx, parentIdx; lightIdx = heap[0]; parentIdx = lightIdx/2; /* lightIdx is root? && swap? */ while((parentIdx > 0) && (heap[lightIdx] < heap[parentIdx])) { /* swap */ swap(heap + lightIdx, heap + parentIdx); lightIdx = parentIdx; parentIdx = lightIdx/2; }}int delete_min(int heap[]) { int min; if (heap[0] < 1) { /* delete element from an empty heap */ printf("Error: delete_min from an empty heap."); exit(1); } /* delete root move the last leaf to the root */ min = heap[1]; swap(heap + 1, heap + heap[0]); heap[0] -= 1; /* recover heap property */ percolate_down(heap); return min;}static void percolate_down(int heap[]) { int heavyIdx; int childIdx1, childIdx2, minIdx; int sign; /* state variable, 1: swap; 0: no swap */ heavyIdx = 1; do { sign = 0; childIdx1 = heavyIdx*2; childIdx2 = childIdx1 + 1; if (childIdx1 > heap[0]) { /* both children are null */ break; } else if (childIdx2 > heap[0]) { /* right children is null */ minIdx = childIdx1; } else { minIdx = (heap[childIdx1] < heap[childIdx2]) ? childIdx1 : childIdx2; } if (heap[heavyIdx] > heap[minIdx]) { /* swap with child */ swap(heap + heavyIdx, heap + minIdx); heavyIdx = minIdx; sign = 1; } } while(sign == 1);}總結
除了上面的算法，還有諸如Bucket Sorting, Radix Sorting涉及。我會在未來實現了相關算法之后，補充到這篇文章中。相關算法的時間復雜度分析可以參考書目中找到。我自己也做了粗糙的分析。如果博客 園能支持數學公式的顯示，我就把自己的分析過程貼出來，用于引玉。
上面的各個代碼是我自己寫的，只進行了很簡單的測試。如果有錯漏，先謝謝你的指正。
最后，上文中用到的交換函數為：
/* By Vamei *//* exchange the values pointed by pa and pb*/void swap(int *pa, int *pb){ int tmp; tmp = *pa; *pa = *pb; *pb = tmp;}幾種排序算法的比較和選擇
1. 選取排序方法需要考慮的因素：
(1) 待排序的元素數目n；
(2) 元素本身信息量的大小；
(3) 關鍵字的結構及其分布情況；
(4) 語言工具的條件，輔助空間的大小等。
2. 一些建議：
(1) 若n較小(n <= 50)，則可以采用直接插入排序或直接選擇排序。由于直接插入排序所需的記錄移動操作較直接選擇排序多，因而當記錄本身信息量較大時，用直接選擇排序較好。
(2) 若文件的初始狀態已按關鍵字基本有序，則選用直接插入或冒泡排序為宜。
(3) 若n較大，則應采用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸并排序。快速排序是目前基于比較的內部排序法中被認為是最好的方法。
(4) 在基于比較排序方法中，每次比較兩個關鍵字的大小之后，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程，由此可以證明：當文件的n個關鍵字隨機分布時，任何借助于"比較"的排序算法，至少需要O(nlog2n)的時間。
(5) 當記錄本身信息量較大時，為避免耗費大量時間移動記錄，可以用鏈表作為存儲結構。
新聞熱點
疑難解答
圖片精選
