轉自：http://www.cnblogs.com/ttltry-air/archive/2012/08/04/2623302.html

? ?計數排序，基數排序，桶排序等非比較排序算法，平均時間復雜度都是O(n)。這些排序因為其待排序元素本身就含有了定位特征，因而不需要比較就可以確定其前后位置，從而可以突破比較排序算法時間復雜度O(nlgn)的理論下限。

計數排序(Counting sort)

????計數排序(Counting sort)是一種穩定的排序算法。計數排序是最簡單的特例，由于用來計數的數組C的長度取決于待排序數組中數據的范圍（等于待排序數組的最大值與最小值的差加上1），這使得計數排序對于數據范圍很大的數組，需要大量時間和內存，適用性不高。例如：計數排序是用來排序0到100之間的數字的最好的算法，但是它不適合按字母順序排序人名。但是，計數排序可以用在基數排序中的算法來排序數據范圍很大的數組。當輸入的元素是?n 個 0 到 k 之間的整數時，它的運行時間是?Θ(n?+?k)。

??? 假定輸入是個數組A【1...n】， length【A】=n。 另外還需要一個存放排序結果的數組B【1...n】，以及提供臨時存儲區的C【0...k】(k是所有元素中最大的一個)。算法偽代碼：

算法的步驟如下：

找出待排序的數組中最大和最小的元素

統計數組中每個值為t的元素出現的次數，存入數組C的第t項

對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）

反向填充目標數組：將每個元素t放在新數組的第C(t)項，每放一個元素就將C(t)減去1

算法實現：

1: /* 2: * 算法的步驟如下： 3: 1、找出待排序的數組中最大和最小的元素 4: 2、統計數組中每個值為t的元素出現的次數，存入數組C的第t項 5: 3、對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加） 6: 4、反向填充目標數組：將每個元素t放在新數組的第C(t)項，每放一個元素就將C(t)減去1 7: * */ 8: public class CountingSort { 9: // 類似bitmap排序 10: public static void countSort(int[] a, int[] b, final int k) { 11: // k>=n 12: int[] c = new int[k + 1]; 13: for (int i = 0; i < k; i++) { 14: c[i] = 0; 15: } 16: for (int i = 0; i < a.length; i++) { 17: c[a[i]]++; 18: } 19: System.out.println("\n****************"); 20: System.out.println("計數排序第2步后,臨時數組C變為："); 21: for (int m:c) { 22: System.out.print(m + " "); 23: } 24: 25: for (int i = 1; i <= k; i++) { 26: c[i] += c[i - 1]; 27: } 28: System.out.println("\n計數排序第3步后,臨時數組C變為："); 29: for (int m:c) { 30: System.out.print(m + " "); 31: } 32: 33: for (int i = a.length - 1; i >= 0; i--) { 34: b[c[a[i]] - 1] = a[i];//C[A[i]]-1 就代表小于等于元素A[i]的元素個數，就是A[i]在B的位置 35: c[a[i]]--; 36: } 37: System.out.println("\n計數排序第4步后,臨時數組C變為："); 38: for (int n:c) { 39: System.out.print(n + " "); 40: } 41: System.out.println("\n計數排序第4步后,數組B變為："); 42: for (int t:b) { 43: System.out.print(t + " "); 44: } 45: System.out.println(); 46: System.out.println("****************\n"); 47: } 48:? 49: public static int getMaxNumber(int[] a) { 50: int max = 0; 51: for (int i = 0; i < a.length; i++) { 52: if (max < a[i]) { 53: max = a[i]; 54: } 55: } 56: return max; 57: } 58:? 59: public static void main(String[] args) { 60: int[] a = new int[] { 2, 5, 3, 0, 2, 3, 0, 3 }; 61: int[] b = new int[a.length]; 62: System.out.println("計數排序前為："); 63: for (int i = 0; i < a.length; i++) { 64: System.out.print(a[i] + " "); 65: } 66: System.out.println(); 67: countSort(a, b, getMaxNumber(a)); 68: System.out.println("計數排序后為："); 69: for (int i = 0; i < a.length; i++) { 70: System.out.print(b[i] + " "); 71: } 72: System.out.println(); 73: } 74:? 75: }

?

基數排序(radix sorting)

??????基數排序（radix sorting）將所有待比較數值(正整數)統一為同樣的數位長度，數位較短的數前面補零。 然后 從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后， 數列就變成一個有序序列。具體過程可以參考動畫演示。

???? 假設我們有一些二元組(a,b)，要對它們進行以a為首要關鍵字，b的次要關鍵字的排序。我們可以先把它們先按照首要關鍵字排序，分成首要關鍵字相同的若干堆。然后，在按照次要關鍵值分別對每一堆進行單獨排序。最后再把這些堆串連到一起，使首要關鍵字較小的一堆排在上面。按這種方式的基數排序稱為MSD(Most Significant Dight)排序。第二種方式是從最低有效關鍵字開始排序，稱為LSD(Least Significant Dight)排序。首先對所有的數據按照次要關鍵字排序，然后對所有的數據按照首要關鍵字排序。要注意的是，使用的排序算法必須是穩定的，否則就會取消前一次排序的結果。由于不需要分堆對每堆單獨排序，LSD方法往往比MSD簡單而開銷小。下文介紹的方法全部是基于LSD的。

????? 基數排序的簡單描述就是將數字拆分為個位十位百位，每個位依次排序。因為這對算法穩定要求高，所以我們對數位排序用到上一個排序方法計數排序。因為基數排序要經過d (數據長度)次排序， 每次使用計數排序， 計數排序的復雜度為 On),? d 相當于常量和N無關，所以基數排序也是 O(n)。基數排序雖然是線性復雜度， 即對n個數字處理了n次，但是每一次代價都比較高， 而且使用計數排序的基數排序不能進行原地排序，需要更多的內存， 并且快速排序可能更好地利用硬件的緩存， 所以比較起來，像快速排序這些原地排序算法更可取。對于一個位數有限的十進制數，我們可以把它看作一個多元組，從高位到低位關鍵字重要程度依次遞減。可以使用基數排序對一些位數有限的十進制數排序。

??? 例如我們將一個三位數分成，個位，十位，百位三部分。我們要對七個三位數來進行排序，依次對其個位，十位，百位進行排序，如下圖：

很顯然，每一位的數的大小都在[0，9]中，對于每一位的排序用計數排序再適合不過。

算法實現：

1: // 基數排序：穩定排序 2: public class RadixSorting { 3:? 4: // d為數據長度 5: private static void radixSorting(int[] arr, int d) { 6: //arr = countingSort(arr, 0); 7: for (int i = 0; i < d; i++) { 8: arr = countingSort(arr, i); // 依次對各位數字排序（直接用計數排序的變體） 9: print(arr,i+1,d); 10: } 11: } 12: 13: // 把每次按位排序的結果打印出來 14: static void print(int[] arr,int k,int d) 15: { 16: if(k==d) 17: System.out.println("最終排序結果為："); 18: else 19: System.out.println("按第"+k+"位排序后，結果為："); 20: for (int t : arr) { 21: System.out.print(t + " "); 22: } 23: System.out.println(); 24: } 25: 26: // 利用計數排序對元素的每一位進行排序 27: private static int[] countingSort(int[] arr, int index) { 28: int k = 9; 29: int[] b = new int[arr.length]; 30: int[] c = new int[k + 1]; //這里比較特殊：數的每一位最大數為9 31:? 32: for (int i = 0; i < k; i++) { 33: c[i] = 0; 34: } 35: for (int i = 0; i < arr.length; i++) { 36: int d = getBitData(arr[i], index); 37: c[d]++; 38: } 39: for (int i = 1; i <= k; i++) { 40: c[i] += c[i - 1]; 41: } 42: for (int i = arr.length - 1; i >= 0; i--) { 43: int d = getBitData(arr[i], index); 44: b[c[d] - 1] = arr[i];//C[d]-1 就代表小于等于元素d的元素個數，就是d在B的位置 45: c[d]--; 46: } 47: return b; 48: } 49:? 50: // 獲取data指定位的數 51: private static int getBitData(int data, int index) { 52: while (data != 0 && index > 0) { 53: data /= 10; 54: index--; 55: } 56: return data % 10; 57: } 58:? 59: public static void main(String[] args) { 60: // TODO Auto-generated method stub 61: int[] arr = new int[] {326,453,608,835,751,435,704,690,88,79,79};//{ 333, 956, 175, 345, 212, 542, 99, 87 }; 62: System.out.println("基數排序前為："); 63: for (int t : arr) { 64: System.out.print(t + " "); 65: } 66: System.out.println(); 67: radixSorting(arr, 4); 68: } 69:? 70: }

?

桶排序（Bucket Sort）

??? 首先定義桶，桶為一個數據容器，每個桶存儲一個區間內的數。依然有一個待排序的整數序列A，元素的最小值不小于0，最大值不超過K。假設我們有M個桶，第i個桶Bucket[i]存儲i*K/M至(i+1)*K/M之間的數。桶排序步驟如下：

掃描序列A，根據每個元素的值所屬的區間，放入指定的桶中(順序放置)。

對每個桶中的元素進行排序，什么排序算法都可以，例如插入排序。

依次收集每個桶中的元素，順序放置到輸出序列中。

???? 具體過程可以參考動畫演示。

算法偽代碼為：

具體代碼：

?

1: // 桶排序 2: public class BucketSort { 3:? 4: // 插入排序 5: static void insertSort(int[] a) { 6: int n = a.length; 7: for (int i = 1; i < n; i++) { 8: int p = a[i]; 9: insert(a, i, p); 10: } 11: } 12:? 13: static void insert(int[] a, int index, int x) { 14: // 元素插入數組a[0:index-1] 15: int i; 16: for (i = index - 1; i >= 0 && x < a[i]; i--) { 17: a[i + 1] = a[i]; 18: } 19: a[i + 1] = x; 20: } 21:? 22: private static void bucketSort(int[] a) { 23: int M = 10; // 11個桶 24: int n = a.length; 25: int[] bucketA = new int[M]; // 用于存放每個桶中的元素個數 26: // 構造一個二維數組b，用來存放A中的數據,這里的B相當于很多桶，B[i][]代表第i個桶 27: int[][] b = new int[M][n]; 28: int i, j; 29: for (i = 0; i < M; i++) 30: for (j = 0; j < n; j++) 31: b[i][j] = 0; 32:? 33: int data, bucket; 34: for (i = 0; i < n; i++) { 35: data = a[i]; 36: bucket = data / 10; 37: b[bucket][bucketA[bucket]] = a[i];// B[0][]中存放A中進行A[i]/10運算后高位為0的數據，同理B[1][]存放高位為1的數據 38: bucketA[bucket]++;// 用來計數二維數組中列中數據的個數，也就是桶A[i]中存放數據的個數 39: } 40: System.out.println("每個桶內元素個數："); 41: for (i = 0; i < M; i++) { 42: System.out.print(bucketA[i] + " "); 43: } 44: System.out.println(); 45:? 46: System.out.println("數據插入桶后，桶內未進行排序前的結果為："); 47: for (i = 0; i < M; i++) { 48: for (j = 0; j < n; j++) 49: System.out.print(b[i][j] + " "); 50: System.out.println(); 51: } 52:? 53: System.out.println("對每個桶進行插入排序，結果為："); 54: // 下面使用直接插入排序對這個二維數組進行排序,也就是對每個桶進行排序 55: for (i = 0; i < M; i++) { 56: // 下面是對具有數據的一列進行直接插入排序，也就是對B[i][]這個桶中的數據進行排序 57: if (bucketA[i] != 0) { 58: // 插入排序 59: for (j = 1; j < bucketA[i]; j++) { 60: int p = b[i][j]; 61: int k; 62: for (k = j - 1; k >= 0 && p < b[i][k]; k--) 63: { 64: assert k==-1; 65: b[i][k + 1] = b[i][k]; 66: } 67: b[i][k + 1] = p; 68: } 69: } 70: } 71: 72: // 輸出排序過后的順序 73: for (i = 0; i < 10; i++) { 74: if (bucketA[i] != 0) { 75: for (j = 0; j < bucketA[i]; j++) { 76: System.out.print(b[i][j] + " "); 77: } 78: } 79: } 80: } 81:? 82: /** 83: * @param args 84: */ 85: public static void main(String[] args) { 86: // TODO Auto-generated method stub 87: int[] arr = new int[] {3,5,45,34,2,78,67,34,56,98}; 88: bucketSort(arr); 89: } 90:? 91: }

三種線性排序的比較

排序算法	時間復雜度	空間復雜度	?
計數排序	O(N+K)	O(N+K)	穩定排序
基數排序	O(N)	O(N)	穩定排序
桶排序	O(N+K)	O(N+K)	穩定排序

???? 從整體上來說，計數排序，桶排序都是非基于比較的排序算法，而其時間復雜度依賴于數據的范圍，桶排序還依賴于空間的開銷和數據的分布。而基數排序是一種對多元組排序的有效方法，具體實現要用到計數排序或桶排序。

???? 相對于快速排序、堆排序等基于比較的排序算法，計數排序、桶排序和基數排序限制較多，不如快速排序、堆排序等算法靈活性好。但反過來講，這三種線性排序算法之所以能夠達到線性時間，是因為充分利用了待排序數據的特性，如果生硬得使用快速排序、堆排序等算法，就相當于浪費了這些特性，因而達不到更高的效率。

總結

以上是生活随笔為你收集整理的排序算法之计数排序、基数排序和桶排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。