數據結構與演算法：計數排序和基數排序

來自專欄 數據結構與演算法

兩個都是基於桶排序的這樣一個思想。

什麼是桶排序？它不是一個基於比較的排序，而是最快最簡單的排序。時間複雜度接近於O(n).缺點就是可能佔用大量空間。

我們下面用具體的例子來解釋：

計數排序：

我們要將員工的升高從大到小進行輸出。

一個人的身高一般是100cm---300cm之間，那麼我們建立100至300的桶。

然後依次將員工身高放入對應的桶中。

最後將100至300桶中的數據依次倒出即為從小到大的排序。

王五：168 張三：175 李四：185

Java代碼實現：

public static void countingSort(int[] a){ int min=a[0]; int max=a[0]; //找出最大最小值 for(int i=1;i<a.length;i++){ min=Math.min(min, a[i]); max=Math.max(max, a[i]); } int[] countArr=new int[max-min+1]; for(int i=0;i<a.length;i++){ //將放入元素的桶的容量加一,注意循環的次數是a.length countArr[a[i]-min]++; } //將桶中元素取出來 int index=0; for(int i=0;i<countArr.length;i++){ //用while不用if的原因是，可能存在一樣的多個值 while(countArr[i]-->0){ a[index++]=i+min; } } }

基數排序：

使用數組鏈接數組的哈希表結構來存放數據，通過二維數組來實現哈希表

什麼是基數排序。大概的思路是。

根據個位的數選擇桶，依次放入桶中

再按照順序倒出所有數。（先放進去的先倒出來）

然後重複直至百位，最後一次輸出即可實現排序。

下面介紹具體Java代碼實現：

代碼中循環設置為4表示A數組中的數值應該都在0-9999之間。若要通用。可以求出數組中的最大值max，然後進行

int d=0;

int temp=1;

while((max/temp)%10>0){

d++;

temp*=10;

}

求出d，即最大的位數

public int[] radixSort(int[] A, int n){ //特殊輸入 if (A == null || A.length< 2) return A; // 創建一個二維數組存放數據,10是桶的數目，n是每個桶中元素的最多數目,其大小最大是n,可以不放滿 int number[][] = new int[10][n]; //定義遍歷k，用來求不同位置的餘數 int k = 1; // 第一層循環，用於對每個位置求餘數,已知元素的數據<=2000，因此需要遍歷的位數是固定的,p=1,10,100,1000;如果不給定<2000這個條件，則要通過value=(A[i]/k)%10<=0來進行判斷是否結束 int p = 1; while (p <= 4) {/*定義一個數組count[]用來存放每個桶value中的元素,value的範圍是0~9所以數組的大小是10；千萬注意;count[]數組用來記錄當前位上每個元素的數目,只對當前位有效,當對下一位進行處理時要將count[]數組全部元素置空或者將count[]定義在while()循環之內於是每次更換位數時都會重置count[]數組*/ int[] count = new int[10]; //遍歷原始數組A，將元素散列到二維數組構建的哈希表中 for (int i = 0; i< n; i++) { // 求出當前位上每個元素的餘數(如何求一個數中的某一個位的數組：先除以k=10^m,再%10取餘數)//並且count[value]++ 桶元素的個數++ int value =(A[i] / k) % 10; number[value][count[value]++]= A[i]; } // 定義一個指針index來遍歷新的數組，用於將從哈希表中取出的元素逐個覆蓋到原始數組中 int index = 0; // 原始數組遍歷完成，元素已經全部放入到哈希表（二維數組）中，將其取出覆蓋原數組 for (int i = 0; i< 10; i++) {// 該餘數值的位置可能有多個值（count[value]個），要循環取出裡面的各個值,從0開始取出 for (int j= 0; j < count[i]; j++) { A[index++]= number[i][j]; } } //本次遍歷結束，調整除數，對前面一位進行取余等處理 k *= 10; p++; } //千萬注意：排序結束後要返回結果數組 return A; }

推薦閱讀：