排序算法之计数排序、基数排序和桶排序
轉自: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是所有元素中最大的一個)。算法偽代碼:
算法的步驟如下:
算法實現:
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之間的數。桶排序步驟如下:
???? 具體過程可以參考動畫演示。
算法偽代碼為:
具體代碼:
?
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) | 穩定排序 |
???? 從整體上來說,計數排序,桶排序都是非基于比較的排序算法,而其時間復雜度依賴于數據的范圍,桶排序還依賴于空間的開銷和數據的分布。而基數排序是一種對多元組排序的有效方法,具體實現要用到計數排序或桶排序。
???? 相對于快速排序、堆排序等基于比較的排序算法,計數排序、桶排序和基數排序限制較多,不如快速排序、堆排序等算法靈活性好。但反過來講,這三種線性排序算法之所以能夠達到線性時間,是因為充分利用了待排序數據的特性,如果生硬得使用快速排序、堆排序等算法,就相當于浪費了這些特性,因而達不到更高的效率。
總結
以上是生活随笔為你收集整理的排序算法之计数排序、基数排序和桶排序的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: centos 推荐使用epel源
- 下一篇: 映射二分堆