新的一年到了，很多園友都辭職要去追求更好的工作環境，我也是其中一個，呵呵！ 最近閒暇的時候我開始重溫一些常用的算法。老早就買了《算法導論》，一直都沒啃下去。 這本書確實很好，只是太難讀了，總是讀了幾章就又讀不下去了！工作上也幾乎用不到。 我這段時間發現看這些排序算法比以前容易了很多，就借此機會將它們整理總結起來。 一是方便以後重溫，二是可以應對筆試面試。同時也希望這篇博文可以幫助各位剛辭職和正在學習排序算法的園友。 PS：有可能實現的代碼並不是最優的，如果有什麼錯誤或者值得改進的地方，還請大家幫忙指出。 簡介 排序算法是我們編程中遇到的最多的算法。目前主流的算法有8種。 平均時間復雜度從高到低依次是： 冒泡排序（o(n2)），選擇排序（o(n2)），插入排序（o(n2)），堆排序（o(nlogn)）， 歸並排序（o(nlogn)），快速排序（o(nlogn)）， 希爾排序（o(n1.25)），基數排序（o(n)） 這些平均時間復雜度是參照維基百科排序算法羅列的。 是計算的理論平均值，並不意味著你的代碼實現能達到這樣的程度。 例如希爾排序，時間復雜度是由選擇的步長決定的。基數排序時間復雜度最小， 但我實現的基數排序的速度並不是最快的，後面的結果測試圖可以看到。 本文代碼實現使用的數據源類型為IList<int>，這樣可以兼容int[]和List<int>(雖然int[]有ToList()， List<int>有ToArray()，哈哈！)。 選擇排序 選擇排序是我覺得最簡單暴力的排序方式了。 以前剛接觸排序算法的時候，感覺算法太多搞不清，唯獨記得選擇排序的做法及實現。 原理：找出參與排序的數組最大值，放到末尾（或找到最小值放到開頭） 維基入口 實現如下： 復制代碼 1 public static void SelectSort(IList<int> data) 2 { 3 for (int i = 0; i < data.Count - 1; i++) 4 { 5 int min = i; 6 int temp = data[i]; 7 for (int j = i + 1; j < data.Count; j++) 8 { 9 if (data[j] < temp) 10 { 11 min = j; 12 temp = data[j]; 13 } 14 } 15 if (min != i) 16 Swap(data, min, i); 17 } 18 } 復制代碼 過程解析：將剩余數組的最小數交換到開頭。 冒泡排序 冒泡排序是筆試面試經常考的內容，雖然它是這些算法裡排序速度最慢的（汗），後面有測試為證。 原理：從頭開始，每一個元素和它的下一個元素比較，如果它大，就將它與比較的元素交換，否則不動。 這意味著，大的元素總是在向後慢慢移動直到遇到比它更大的元素。所以每一輪交換完成都能將最大值 冒到最後。 維基入口 實現如下： 復制代碼 1 public static void BubbleSort(IList<int> data) 2 { 3 for (int i = data.Count - 1; i > 0; i--) 4 { 5 for (int j = 0; j < i; j++) 6 { 7 if (data[j] > data[j + 1]) 8 Swap(data, j, j + 1); 9 } 10 } 11 } 復制代碼 過程解析：中需要注意的是j<i，每輪冒完泡必然會將最大值排到數組末尾，所以需要排序的數應該是在減少的。 很多網上版本每輪冒完泡後依然還是將所有的數進行第二輪冒泡即j<data.Count-1，這樣會增加比較次數。 通過標識提升冒泡排序 在維基上看到，可以通過添加標識來分辨剩余的數是否已經有序來減少比較次數。感覺很有意思，可以試試。 實現如下： 復制代碼 1 public static void BubbleSortImprovedWithFlag(IList<int> data) 2 { 3 bool flag; 4 for (int i = data.Count - 1; i > 0; i--) 5 { 6 flag = true; 7 for (int j = 0; j < i; j++) 8 { 9 if (data[j] > data[j + 1]) 10 { 11 Swap(data, j, j + 1); 12 flag = false; 13 } 14 } 15 if (flag) break; 16 } 17 } 復制代碼 過程解析：發現某輪冒泡沒有任何數進行交換（即已經有序），就跳出排序。 我起初也以為這個方法是應該有不錯效果的，可是實際測試結果並不如想的那樣。和未優化耗費時間一樣（對於隨機數列）。 由果推因，那麼應該是冒泡排序對於隨機數列，當剩余數列有序的時候，也沒幾個數要排列了！？ 不過如果已經是有序數列或者部分有序的話，這個冒泡方法將會提升很大速度。 雞尾酒排序（來回排序） 對冒泡排序進行更大的優化 冒泡排序只是單向冒泡，而雞尾酒來回反復雙向冒泡。 原理：自左向右將大數冒到末尾，然後將剩余數列再自右向左將小數冒到開頭，如此循環往復。維基入口 實現如下： 復制代碼 1 public static void BubbleCocktailSort(IList<int> data) 2 { 3 bool flag; 4 int m = 0, n = 0; 5 for (int i = data.Count - 1; i > 0; i--) 6 { 7 flag = true; 8 if (i % 2 == 0) 9 { 10 for (int j = n; j < data.Count - 1 - m; j++) 11 { 12 if (data[j] > data[j + 1]) 13 { 14 Swap(data, j, j + 1); 15 flag = false; 16 } 17 } 18 if (flag) break; 19 m++; 20 } 21 else 22 { 23 for (int k = data.Count - 1 - m; k > n; k--) 24 { 25 if (data[k] < data[k - 1]) 26 { 27 Swap(data, k, k - 1); 28 flag = false; 29 } 30 } 31 if (flag) break; 32 n++; 33 } 34 } 35 } 復制代碼 過程解析：分析第i輪冒泡，i是偶數則將剩余數列最大值向右冒泡至末尾，是奇數則將剩余數列最小值 向左冒泡至開頭。對於剩余數列，n為始，data.Count-1-m為末。 來回冒泡比單向冒泡：對於隨機數列，更容易得到有序的剩余數列。因此這裡使用標識將會提升的更加明顯。 插入排序 插入排序是一種對於有序數列高效的排序。非常聰明的排序。只是對於隨機數列，效率一般，交換的頻率高。 原理：通過構建有序數列，將未排序的數從後向前比較，找到合適位置並插入。維基入口 第一個數當作有序數列。 實現如下： 復制代碼 1 public static void InsertSort(IList<int> data) 2 { 3 int temp; 4 for (int i = 1; i < data.Count; i++) 5 { 6 temp = data[i]; 7 for (int j = i - 1; j >= 0; j--) 8 { 9 if (data[j] > temp) 10 { 11 data[j + 1] = data[j]; 12 if (j == 0) 13 { 14 data[0] = temp; 15 break; 16 } 17 } 18 else 19 { 20 data[j + 1] = temp; 21 break; 22 } 23 } 24 } 25 } 復制代碼 過程解析：將要排序的數（索引為i）存儲起來，向前查找合適位置j+1，將i-1到j+1的元素依次向後 移動一位，空出j+1，然後將之前存儲的值放在這個位置。 這個方法寫的不如維基上的簡潔清晰，由於合適位置是j+1所以多出了對j==0的判斷，但實際效率影響無差別。 建議比照維基和我寫的排序，自行選擇。 二分查找法優化插入排序 插入排序主要工作是在有序的數列中對要排序的數查找合適的位置，而查找裡面經典的二分查找法正可以適用。 原理：通過二分查找法的方式找到一個位置索引。當要排序的數插入這個位置時，大於前一個數，小於後一個數。 實現如下： 復制代碼 1 public static void InsertSortImprovedWithBinarySearch(IList<int> data) 2 { 3 int temp; 4 int tempIndex; 5 for (int i = 1; i < data.Count; i++) 6 { 7 temp = data[i]; 8 tempIndex = BinarySearchForInsertSort(data, 0, i, i); 9 for (int j = i - 1; j >= tempIndex; j--) 10 { 11 data[j + 1] = data[j]; 12 } 13 data[tempIndex] = temp; 14 } 15 } 16 17 public static int BinarySearchForInsertSort(IList<int> data, int low, int high, int key) 18 { 19 if (low >= data.Count - 1) 20 return data.Count - 1; 21 if (high <= 0) 22 return 0; 23 int mid = (low + high) / 2; 24 if (mid == key) return mid; 25 if (data[key] > data[mid]) 26 { 27 if (data[key] < data[mid + 1]) 28 return mid + 1; 29 return BinarySearchForInsertSort(data, mid + 1, high, key); 30 } 31 else // data[key] <= data[mid] 32 { 33 if (mid - 1 < 0) return 0; 34 if (data[key] > data[mid - 1]) 35 return mid; 36 return BinarySearchForInsertSort(data, low, mid - 1, key); 37 } 38 } 復制代碼 過程解析：需要注意的是二分查找方法實現中high-low==1的時候mid==low，所以需要33行 mid-1<0即mid==0的判斷，否則下行會索引越界。 快速排序 快速排序是一種有效比較較多的高效排序。它包含了“分而治之”以及“哨兵”的思想。 原理：從數列中挑選一個數作為“哨兵”，使比它小的放在它的左側，比它大的放在它的右側。將要排序是數列遞歸地分割到 最小數列，每次都讓分割出的數列符合“哨兵”的規則，自然就將數列變得有序。 維基入口 實現如下： 復制代碼 1 public static void QuickSortStrict(IList<int> data) 2 { 3 QuickSortStrict(data, 0, data.Count - 1); 4 } 5 6 public static void QuickSortStrict(IList<int> data, int low, int high) 7 { 8 if (low >= high) return; 9 int temp = data[low]; 10 int i = low + 1, j = high; 11 while (true) 12 { 13 while (data[j] > temp) j--; 14 while (data[i] < temp && i < j) i++; 15 if (i >= j) break; 16 Swap(data, i, j); 17 i++; j--; 18 } 19 if (j != low) 20 Swap(data, low, j); 21 QuickSortStrict(data, j + 1, high); 22 QuickSortStrict(data, low, j - 1); 23 } 復制代碼 過程解析：取的哨兵是數列的第一個值，然後從第二個和末尾同時查找，左側要顯示的是小於哨兵的值， 所以要找到不小於的i，右側要顯示的是大於哨兵的值，所以要找到不大於的j。將找到的i和j的數交換， 這樣可以減少交換次數。i>=j時，數列全部查找了一遍，而不符合條件j必然是在小的那一邊，而哨兵 是第一個數，位置本應是小於自己的數。所以將哨兵與j交換，使符合“哨兵”的規則。 這個版本的缺點在於如果是有序數列排序的話，遞歸次數會很可怕的。 另一個版本 這是維基上的一個C#版本，我覺得很有意思。這個版本並沒有嚴格符合“哨兵”的規則。但卻將“分而治之” 以及“哨兵”思想融入其中，代碼簡潔。 實現如下： 復制代碼 1 public static void QuickSortRelax(IList<int> data) 2 { 3 QuickSortRelax(data, 0, data.Count - 1); 4 } 5 6 public static void QuickSortRelax(IList<int> data, int low, int high) 7 { 8 if (low >= high) return; 9 int temp = data[(low + high) / 2]; 10 int i = low - 1, j = high + 1; 11 while (true) 12 { 13 while (data[++i] < temp) ; 14 while (data[--j] > temp) ; 15 if (i >= j) break; 16 Swap(data, i, j); 17 } 18 QuickSortRelax(data, j + 1, high); 19 QuickSortRelax(data, low, i - 1); 20 } 復制代碼 過程解析：取的哨兵是數列中間的數。將數列分成兩波，左側小於等於哨兵，右側大於等於哨兵。 也就是說，哨兵不一定處於兩波數的中間。雖然哨兵不在中間，但不妨礙“哨兵”的思想的實現。所以 這個實現也可以達到快速排序的效果。但卻造成了每次遞歸完成，要排序的數列數總和沒有減少（除非i==j）。 針對這個版本的缺點，我進行了優化 實現如下： 復制代碼 1 public static void QuickSortRelaxImproved(IList<int> data) 2 { 3 QuickSortRelaxImproved(data, 0, data.Count - 1); 4 } 5 6 public static void QuickSortRelaxImproved(IList<int> data, int low, int high) 7 { 8 if (low >= high) return; 9 int temp = data[(low + high) / 2]; 10 int i = low - 1, j = high + 1; 11 int index = (low + high) / 2; 12 while (true) 13 { 14 while (data[++i] < temp) ; 15 while (data[--j] > temp) ; 16 if (i >= j) break; 17 Swap(data, i, j); 18 if (i == index) index = j; 19 else if (j == index) index = i; 20 } 21 if (j == i) 22 { 23 QuickSortRelaxImproved(data, j + 1, high); 24 QuickSortRelaxImproved(data, low, i - 1); 25 } 26 else //i-j==1 27 { 28 if (index >= i) 29 { 30 if (index != i) 31 Swap(data, index, i); 32 QuickSortRelaxImproved(data, i + 1, high); 33 QuickSortRelaxImproved(data, low, i - 1); 34 } 35 else //index < i 36 { 37 if (index != j) 38 Swap(data, index, j); 39 QuickSortRelaxImproved(data, j + 1, high); 40 QuickSortRelaxImproved(data, low, j - 1); 41 } 42 } 43 } 復制代碼 過程解析：定義了一個變量Index，來跟蹤哨兵的位置。發現哨兵最後在小於自己的那堆， 那就與j交換，否則與i交換。達到每次遞歸都能減少要排序的數列數總和的目的。 歸並排序 歸並排序也是采用“分而治之”的方式。剛發現分治法是一種算法范式，我還一直以為是一種需要意會的思想呢。 不好意思了，孤陋寡聞了，哈哈！ 原理：將兩個有序的數列，通過比較，合並為一個有序數列。 維基入口 為方便理解，此處實現用了List<int>的一些方法，隨後有IList<int>版本。 實現如下： 復制代碼 1 public static List<int> MergeSortOnlyList(List<int> data, int low, int high) 2 { 3 if (low == high) 4 return new List<int> { data[low] }; 5 List<int> mergeData = new List<int>(); 6 int mid = (low + high) / 2; 7 List<int> leftData = MergeSortOnlyList(data, low, mid); 8 List<int> rightData = MergeSortOnlyList(data, mid + 1, high); 9 int i = 0, j = 0; 10 while (true) 11 { 12 if (leftData[i] < rightData[j]) 13 { 14 mergeData.Add(leftData[i]); 15 if (++i == leftData.Count) 16 { 17 mergeData.AddRange(rightData.GetRange(j, rightData.Count - j)); 18 break; 19 } 20 } 21 else 22 { 23 mergeData.Add(rightData[j]); 24 if (++j == rightData.Count) 25 { 26 mergeData.AddRange(leftData.GetRange(i, leftData.Count - i)); 27 break; 28 } 29 } 30 } 31 return mergeData; 32 } 33 34 public static List<int> MergeSortOnlyList(List<int> data) 35 { 36 data = MergeSortOnlyList(data, 0, data.Count - 1); //不會改變外部引用 參照C#參數傳遞 37 return data; 38 } 復制代碼 過程解析：將數列分為兩部分，分別得到兩部分數列的有序版本，然後逐個比較，將比較出的小數逐個放進 新的空數列中。當一個數列放完後，將另一個數列剩余數全部放進去。 IList<int>版本 實現如下： 復制代碼 1 public static IList<int> MergeSort(IList<int> data) 2 { 3 data = MergeSort(data, 0, data.Count - 1); 4 return data; 5 } 6 7 public static IList<int> MergeSort(IList<int> data, int low, int high) 8 { 9 int length = high - low + 1; 10 IList<int> mergeData = NewInstance(data, length); 11 if (low == high) 12 { 13 mergeData[0] = data[low]; 14 return mergeData; 15 } 16 int mid = (low + high) / 2; 17 IList<int> leftData = MergeSort(data, low, mid); 18 IList<int> rightData = MergeSort(data, mid + 1, high); 19 int i = 0, j = 0; 20 while (true) 21 { 22 if (leftData[i] < rightData[j]) 23 { 24 mergeData[i + j] = leftData[i++]; //不能使用Add,Array Length不可變 25 if (i == leftData.Count) 26 { 27 int rightLeft = rightData.Count - j; 28 for (int m = 0; m < rightLeft; m++) 29 { 30 mergeData[i + j] = rightData[j++]; 31 } 32 break; 33 } 34 } 35 else 36 { 37 mergeData[i + j] = rightData[j++]; 38 if (j == rightData.Count) 39 { 40 int leftleft = leftData.Count - i; 41 for (int n = 0; n < leftleft; n++) 42 { 43 mergeData[i + j] = leftData[i++]; 44 } 45 break; 46 } 47 } 48 } 49 return mergeData; 50 51 } 復制代碼 過程原理與上個一樣，此處就不贅述了。 堆排序 堆排序是根據堆這種數據結構設計的一種算法。堆的特性：父節點的值總是小於（或大於）它的子節點。近似二叉樹。 原理：將數列構建為最大堆數列（即父節點總是最大值），將最大值（即根節點）交換到數列末尾。這樣要排序的數列數總和減少， 同時根節點不再是最大值，調整最大堆數列。如此重復，最後得到有序數列。 維基入口 有趣的演示 實現准備：如何將數列構造為堆——父節點i的左子節點為2i+1，右子節點為2i+2。節點i的父節點為floor((i-1)/2)。 實現如下（這個實現判斷和臨時變量使用太多，導致效率低，評論中@小城故事提出了更好的實現）： 復制代碼 1 public static void HeapSort(IList<int> data) 2 { 3 BuildMaxHeapify(data); 4 int j = data.Count; 5 for (int i = 0; i < j; ) 6 { 7 Swap(data, i, --j); 8 if (j - 2 < 0) //只剩下1個數 j代表余下要排列的數的個數 9 break; 10 int k = 0; 11 while (true) 12 { 13 if (k > (j - 2) / 2) break; //即：k > ((j-1)-1)/2 超出最後一個父節點的位置 14 else 15 { 16 int temp = k; 17 k = ReSortMaxBranch(data, k, 2 * k + 1, 2 * k + 2, j - 1); 18 if (temp == k) break; 19 } 20 } 21 } 22 } 23 24 public static void BuildMaxHeapify(IList<int> data) 25 { 26 for (int i = data.Count / 2 - 1; i >= 0; i--) //(data.Count-1)-1)/2為數列最大父節點索引 27 { 28 int temp = i; 29 temp = ReSortMaxBranch(data, i, 2 * i + 1, 2 * i + 2, data.Count - 1); 30 if (temp != i) 31 { 32 int k = i; 33 while (k != temp && temp <= data.Count / 2 - 1) 34 { 35 k = temp; 36 temp = ReSortMaxBranch(data, temp, 2 * temp + 1, 2 * temp + 2, data.Count - 1); 37 } 38 } 39 } 40 } 41 42 public static int ReSortMaxBranch(IList<int> data, int maxIndex, int left, int right, int lastIndex) 43 { 44 int temp; 45 if (right > lastIndex) //父節點只有一個子節點 46 temp = left; 47 else 48 { 49 if (data[left] > data[right]) 50 temp = left; 51 else temp = right; 52 } 53 54 if (data[maxIndex] < data[temp]) 55 Swap(data, maxIndex, temp); 56 else temp = maxIndex; 57 return temp; 58 } 復制代碼 過程解析：BuildMaxHeapify為排序前構建的最大堆數列方法，主要內容為從最後一個父節點開始往前將每個三角組合 （即父節點與它的兩個子節點）符合父節點值最大的規則。ReSortMaxBranch為將三角調整為父節點值最大， 並返回該值之前的索引，用來判斷是否進行了交換，以及原來的父節點值交換到了什麼位置。在HeapSort裡首先 構建了最大堆數列，然後將根節點交換到末尾，根節點不是最大值了，在while語句中對最大堆數列進行調整。 插曲：自從看了Martin Fowler大師《重構》第三版，我發現我更不喜歡寫注釋了。每次都想著盡量讓方法的名字更貼切， 即使會造成方法的名字很長很丑。這算不算曲解了大師的意思啊！？上面的代碼注釋都是寫博客的時候現加的（源代碼很干淨的。汗!）。 希爾排序 希爾排序是插入排序的一種更高效的改進版本。 在前面介紹的插入排序，我們知道1.它對有序數列排序的效率是非常高的 2.要排序的數向前移動是一步步進行的導致插入排序效率低。 希爾排序正是利用第一點，改善第二點，達到更理想的效果。 原理：通過奇妙的步長，插入排序間隔步長的元素，隨後逐漸縮短步長至1，實現數列的插入排序。 維基入口 疑問：可以想象到排序間隔步長的數，會逐漸讓數列變得有序，提升最後步長為1時標准插入排序的效率。在維基上看到這麼 一句話“可能希爾排序最重要的地方在於當用較小步長排序後，以前用的較大步長仍然是有序的”注意用詞是‘可能’。我的疑問是 這是個正確的命題嗎？如何證明呢？看維基上也是由果推因，說是如果不是這樣，就不會排序那麼快了。可這我感覺還是太牽強了， 哪位大哥發現相關資料，希望能分享出來，不勝感激。 實現如下： 復制代碼 1 public static void ShellSort(IList<int> data) 2 { 3 int temp; 4 for (int gap = data.Count / 2; gap > 0; gap /= 2) 5 { 6 for (int i = gap; i < data.Count; i += gap) 7 { 8 temp = data[i]; 9 for (int j = i - gap; j >= 0; j -= gap) 10 { 11 if (data[j] > temp) 12 { 13 data[j + gap] = data[j]; 14 if (j == 0) 15 { 16 data[j] = temp; 17 break; 18 } 19 } 20 else 21 { 22 data[j + gap] = temp; 23 break; 24 } 25 } 26 } 27 } 28 } 復制代碼 過程解析：采用的步長是N/2，每次取半，直至1。循環內部就是標准的插入排序。 這裡實現的貌似是最差的希爾排序。主要源於步長的選擇。維基上有各種牛叉的“凌波微步”，極限在哪裡， 喜歡挑戰的同學可以去學習學習。看維基排序算法裡六種排序的測試，希爾最快，比快速排序還快！！我沒實現啊！ 只是對於神奇的步長更充滿了敬畏。 基數排序 基數排序是一種非比較型整數排序。 “非比較型”是什麼意思呢？因為它內部使用的是桶排序，而桶排序是非比較型排序。 這裡就要說說桶排序了。一個非常有意思的排序。 桶排序 原理：取一定數量（數列中的最大值）的編好序號的桶，將數列每個數放進編號為它的桶裡，然後將不是空的桶依次倒出來， 就組成有序數列了。 維基入口 好吧！聰明的人一眼就看出桶排序的破綻了。假設只有兩個數1,10000，豈不是要一萬個桶！？這確實是個問題啊！我也 沒想出解決辦法。我起初也以為桶排序就是一個通過犧牲空間來換取時間的排序算法，它不需要比較，所以是非比較型算法。 但看了有趣的演示的桶排序後，發現世界之大，你沒有解決，不代表別人沒解決，睿智的人總是很多。 1，9999的桶排序實現：new Int[2];總共有兩個數，得出最大數9999的位數4，取10的4次冪即10000作為分母， 要排序的數（1或9999）作為分子，並乘以數列總數2，即1*2/10000,9999*2/10000得到各自的位置0,1，完成排序。 如果是1,10000進行排序的話，上面的做法就需要稍微加一些處理——發現最大數是10的n次冪，就將它作為分母，並 放在數列末尾就好了。 如果是9999,10000進行排序的話，那就需要二維數組了，兩個都在位置1，位置0沒數。這個時候就需要在放 入每個位置時采用其它排序（比如插入排序）辦法對這個位置的多個數排序了。 為基數排序做個過渡，我這裡實現了一個個位數桶排序 涉及到了當重復的數出現的處理。 實現如下： 復制代碼 1 public static void BucketSortOnlyUnitDigit(IList<int> data) 2 { 3 int[] indexCounter = new int[10]; 4 for (int i = 0; i < data.Count; i++) 5 { 6 indexCounter[data[i]]++; 7 } 8 int[] indexBegin = new int[10]; 9 for (int i = 1; i < 10; i++) 10 { 11 indexBegin[i] = indexBegin[i-1]+ indexCounter[i-1]; 15 } 16 IList<int> tempList = NewInstance(data, data.Count); 17 for (int i = 0; i < data.Count; i++) 18 { 19 int number = data[i]; 20 tempList[indexBegin[number]++] = data[i]; 21 } 22 data = tempList; 23 } 復制代碼 過程解析：indexCounter進行對每個數出現的頻率的統計。indexBegin存儲每個數的起始索引。 比如 1 1 2，indexCounter統計到0個0,2個1,1個2。indexBegin計算出0,1,2的起始索引分別為 0,0,2。當1個1已取出排序，那索引將+1,變為0,1,2。這樣就通過提前給重復的數空出位置，解決了 重復的數出現的問題。當然，你也可以考慮用二維數組來解決重復。 下面繼續基數排序。 基數排序原理：將整數按位數切割成不同的數字，然後按每個位數分別比較。 取得最大數的位數，從低位開始，每個位上進行桶排序。 實現如下： 復制代碼 1 public static IList<int> RadixSort(IList<int> data) 2 { 3 int max = data[0]; 4 for (int i = 1; i < data.Count; i++) 5 { 6 if (data[i] > max) 7 max = data[i]; 8 } 9 int digit = 1; 10 while (max / 10 != 0) 11 { 12 digit++; 13 max /= 10; 14 } 15 for (int i = 0; i < digit; i++) 16 { 17 int[] indexCounter = new int[10]; 18 IList<int> tempList = NewInstance(data, data.Count); 19 for (int j = 0; j < data.Count; j++) 20 { 21 int number = (data[j] % Convert.ToInt32(Math.Pow(10, i + 1))) / Convert.ToInt32(Math.Pow(10, i)); //得出i+1位上的數 22 indexCounter[number]++; 23 } 24 int[] indexBegin = new int[10]; 25 for (int k = 1; k < 10; k++) 26 { 27 indexBegin[k] = indexBegin[k - 1] + indexCounter[k - 1]; 28 } 29 for (int k = 0; k < data.Count; k++) 30 { 31 int number = (data[k] % Convert.ToInt32(Math.Pow(10, i + 1))) / Convert.ToInt32(Math.Pow(10, i)); 32 tempList[indexBegin[number]++] = data[k]; 33 } 34 data = tempList; 35 } 36 return data; 37 } 復制代碼 過程解析：得出最大數的位數，從低位開始桶排序。我寫的這個實現代碼並不簡潔，但邏輯更清晰。 後面測試的時候我們就會發現，按理來說這個實現也還行吧！ 但並不如想象的那麼快！ 循環的次數太多？（統計頻率n次+9次計算+n次放到新的數組）*位數。 創建的新實例太多？(new int[10]兩次+NewInstance is反射判斷創建實例+new int[n])*位數 測試比較 添加隨機數組，數組有序校驗，微軟Linq排序 代碼如下： 復制代碼 1 public static int[] RandomSet(int length, int max) 2 { 3 int[] result = new int[length]; 4 Random rand = new Random(); 5 for (int i = 0; i < result.Length; i++) 6 { 7 result[i] = rand.Next(max); 8 } 9 return result; 10 } 11 12 public static bool IsAscOrdered(IList<int> data) 13 { 14 bool flag = true; 15 for (int i = 0; i < data.Count - 1; i++) 16 { 17 if (data[i] > data[i + 1]) 18 flag = false; 19 } 20 return flag; 21 } 22 23 public static void TestMicrosoft(IList<int> data) 24 { 25 Stopwatch stopwatch = new Stopwatch(); 26 stopwatch.Start(); 27 List<int> result = data.OrderBy(a => a).ToList(); 28 stopwatch.Stop(); 29 string methodName = "TestMicrosoft"; 30 int length = methodName.Length; 31 for (int i = 0; i < 40 - length; i++) 32 { 33 methodName += " "; 34 } 35 Console.WriteLine(methodName + 36 " IsAscOrdered:" + IsAscOrdered(result) + " Time:" + stopwatch.Elapsed.TotalSeconds); 37 38 } 復制代碼 測試主體如下： 復制代碼 1 static void Main(string[] args) 2 { 3 int[] aa = RandomSet(50000, 99999); 4 //int[] aa = OrderedSet(5000); 5 Console.WriteLine("Array Length:" + aa.Length); 6 RunTheMethod((Action<IList<int>>)SelectSort, aa.Clone() as int[]); 7 RunTheMethod((Action<IList<int>>)BubbleSort, aa.Clone() as int[]); 8 RunTheMethod((Action<IList<int>>)BubbleSortImprovedWithFlag, aa.Clone() as int[]); 9 RunTheMethod((Action<IList<int>>)BubbleCocktailSort, aa.Clone() as int[]); 10 RunTheMethod((Action<IList<int>>)InsertSort, aa.Clone() as int[]); 11 RunTheMethod((Action<IList<int>>)InsertSortImprovedWithBinarySearch, aa.Clone() as int[]); 12 RunTheMethod((Action<IList<int>>)QuickSortStrict, aa.Clone() as int[]); 13 RunTheMethod((Action<IList<int>>)QuickSortRelax, aa.Clone() as int[]); 14 RunTheMethod((Action<IList<int>>)QuickSortRelaxImproved, aa.Clone() as int[]); 15 RunTheMethod((Func<IList<int>, IList<int>>)MergeSort, aa.Clone() as int[]); 16 RunTheMethod((Action<IList<int>>)ShellSort, aa.Clone() as int[]); 17 RunTheMethod((Func<IList<int>, IList<int>>)RadixSort, aa.Clone() as int[]); 18 RunTheMethod((Action<IList<int>>)HeapSort, aa.Clone() as int[]); 19 TestMicrosoft(aa.Clone() as int[]); 20 Console.Read(); 21 } 22 23 public static void RunTheMethod(Func<IList<int>, IList<int>> method, IList<int> data) 24 { 25 Stopwatch stopwatch = new Stopwatch(); 26 stopwatch.Start(); 27 IList<int> result = method(data); 28 stopwatch.Stop(); 29 string methodName = method.Method.Name; 30 int length = methodName.Length; 31 for (int i = 0; i < 40 - length; i++) 32 { 33 methodName += " "; 34 } 35 Console.WriteLine(methodName + 36 " IsAscOrdered:" + IsAscOrdered(result) + " Time:" + stopwatch.Elapsed.TotalSeconds); 37 } 38 39 public static void RunTheMethod(Action<IList<int>> method, IList<int> data) 40 { 41 Stopwatch stopwatch = new Stopwatch(); 42 stopwatch.Start(); 43 method(data); 44 stopwatch.Stop(); 45 string methodName = method.Method.Name; 46 int length = methodName.Length; 47 for (int i = 0; i < 40 - length; i++) 48 { 49 methodName += " "; 50 } 51 Console.WriteLine(methodName + 52 " IsAscOrdered:" + IsAscOrdered(data) + " Time:" + stopwatch.Elapsed.TotalSeconds); 53 } 復制代碼
