轉載請注明出處 http://blog.csdn.net/pony_maggie/article/details/36706131 作者:小馬 一希爾排序 上一篇講到的直接插入排序，時間復雜度O(n^2). 請在腦海里想一下它的過程。如果一個序列本來就是有序的，對它排序的時間復雜度是O(n)。所以當序列基本有序時，插入排序排序的效率大大提高，因為減少了移動的動作。 另外，直接插入排序還有一個特點，當n比較小時，它的效率比較高。 希爾排序正是基于上面兩個思想做的一種改進算法。它先將整個序列分成若干個小序列，對每個小序列做直接插入排序，這樣整個序列變得“基本有序”，然后對整個序列做一次直接插入排序，得到最終結果。不過希爾排序并不是簡單地逐段分割，而用相隔某個增量的記錄組成一個序列。如下圖所示:  一開始增量為3, 有三組，{9，8，4}， {1， 3， 6}，{5，7，2}，分別直接插入排序得到2圖,然后增加變為2，繼續上面的過程，最后當增量為1時，數組就有序了。三趟排序用的增量構造一個增量序列{3,2,1}。這個不是固定的，但是一個好的增量序列，應該沒有除1以外的公因子，并且最后一個增量必須等于1。思路很清晰了，上代碼吧。 ~~~ //一趟插入排序, dk是單次的增量 static void shellInsert(int nArray[], int nLength, int dk) { int i = 0; int j = 0; int nSerity = 0; for (i = dk; i < nLength; i++) { if (nArray[i] < nArray[i-dk]) { nSerity = nArray[i]; for (j = i-dk; (j >= 0)&&(nSerity < nArray[j]); j-=dk) { nArray[j+dk] = nArray[j]; } nArray[j+dk] = nSerity; } } } int shellSort(int nArray[], int nLength) { int k = 0; int dkArray[] = {3, 2, 1}; //默認使用的增量序列 int dkLength = 3; for (k = 0; k < dkLength; k++) { shellInsert(nArray, nLength, dkArray[k]); } return 0; } ~~~ 它的復雜度計算涉及到一些數學難題，你只要知道它的效率比較直接插入排序要高一些就行了。 二快速排序 有些地方會提到快速排序是對冒泡排序的一種改進，我倒是覺得不要這么聯想，會誤導你學習快速排序。 快速排序思想先選取一個“樞紐元素”，一般就是序列的第一個元素。把比這個樞紐小的數據放一邊，比它大的放另一邊。這樣一趟之后序列變為, 一部分中的所有元素都比另一部分中的所有元素小，但是部分之間的記錄可能是無序的。然后對每一部分再用樣的思想繼續分，最后就變為有序序列。如下圖所示:  通過上面的步驟，自然想到用遞歸來實現快速排序，沒錯，上代碼。 ~~~ static int partition(int nArray[], int nLow, int nHigh) { int nPivot = nArray[nLow]; while (nLow < nHigh) { while ((nLow < nHigh) && (nArray[nHigh] >= nPivot)) nHigh--; nArray[nLow] = nArray[nHigh]; while ((nLow < nHigh) && (nArray[nLow] <= nPivot)) nLow++; nArray[nHigh] = nArray[nLow]; } nArray[nLow] = nPivot; return nLow; } static void sortProcess(int nArray[], int nLow, int nHigh) { int nPartition = 0; if (nLow < nHigh) { nPartition = partition(nArray, nLow, nHigh); sortProcess(nArray, nLow, nPartition-1); sortProcess(nArray, nPartition+1, nHigh); } } int quickSort(int nArray[], int nLength) { sortProcess(nArray, 0, nLength-1); return 0; } ~~~ 快速排序時間復雜度是O(nlogn),是目前公認的效率比較高的排序算法。 三歸并排序 歸并排序算是一種比較特殊的排序算法，它將兩個有序表(長度分別是m,n)合并成另一個有序表，這個動作可在O(m+n)的時間復雜度實現。對于個有n個元素的無序序列，可以看成n個有序的子序列，然后兩兩歸并，得到一個n/2長度為2或1(想想為什么有1)的有序子序列，繼續兩兩歸并，直接得到一個長度為n的有序序列為止。如下圖所示:  這里我們用遞歸的方法來實現，好理解一些，非遞歸的方法稍復雜一些。代碼如下: ~~~ //將有序的srcArray[i..m]和srcArray[m+1..n],歸并到destArray[i..n] static void Merge(int srcArray[], int destArray[], int i, int m, int n) { int j = 0; int k = 0; for (j = m+1,k=i; (i<=m)&&(j<=n); ++k) { if (srcArray[i] < srcArray[j]) { destArray[k] = srcArray[i++]; } else { destArray[k] = srcArray[j++]; } } //剩下的直接拷過來 while (i <= m) { destArray[k++] = srcArray[i++]; } while (j <= n) { destArray[k++] = srcArray[j++]; } } static void MSort(int srcArray[], int destArray[], int s,int t) { int m = 0; int destArray2[256] = {0}; //輔助數組,空間根據實際情況分配. if (s == t) { destArray[s] = srcArray[s]; } else { m = (s + t)/2; MSort(srcArray, destArray2, s, m); MSort(srcArray, destArray2, m+1, t); Merge(destArray2, destArray, s, m, t); } } //遞歸方法實現歸并排序 int MergeSort(int nArray[], int nLength) { int nDestArray[256] = {0}; int i = 0; MSort(nArray, nDestArray, 0, nLength-1); while (i<nLength)nArray[i] = nDestArray[i++]; return 0; } ~~~ 它的時間復雜度是O(nlog2n)。 代碼下載地址: http://download.csdn.net/detail/pony_maggie/7568971 或 https://github.com/pony-maggie/SortDemo