上一篇總結了常用的比較排序算法，主要有冒泡排序，選擇排序，插入排序，歸并排序，堆排序，快速排序等。
這篇文章中我們來探讨一下常用的非比較排序算法：計數排序，基數排序，桶排序。在一定條件下，它們的時間複雜度可以達到O(n)。
這裡我們用到的唯一資料結構就是數組，當然我們也可以利用連結清單來實作下述算法。
需要三個數組:
待排序數組 int[] arr = new int[]{1,4,3,4,3};
輔助計數數組 int[] help = new int[max - min + 1]; //該數組大小為待排序數組中的最大值減最小值+1
輸出數組 int[] res = new int[arr.length];
1.求出待排序數組的最大值max=4， 最小值min=1
2.執行個體化輔助計數數組help，help數組中每個下标對應arr中的一個元素， help用來記錄每個元素出現的次數
3.計算 arr 中每個元素在help中的位置 position = arr[i] - min，此時 help = [1,0,2,2]; （4出現了兩次，2未出現）
4.根據 help 數組求得排序後的數組，此時 res = [1,3,3,4,4]
/**
* 分類 ------------ 内部非比較排序
* 資料結構 --------- 數組
* 最差時間複雜度 ---- O(n + k)
* 最優時間複雜度 ---- O(n + k)
* 平均時間複雜度 ---- O(n + k)
* 所需輔助空間 ------ O(n + k)
* 穩定性 ----------- 穩定
*/
public static int[] countSort(int[] arr){
if (arr == null || arr.length == 0) {
return null;
}
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
//找出數組中的最大最小值
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
int help[] = new int[max];
//找出每個數字出現的次數
for(int i = 0; i < arr.length; i++){
int mapPos = arr[i] - min;
help[mapPos]++;
}
int index = 0;
for(int i = 0; i < help.length; i++){
while(help[i]-- > 0){
arr[index++] = i+min;
}
}
return arr;
}
下圖給出了對{ 4, 1, 3, 4, 3 }進行計數排序的簡單示範過程
計數排序的時間複雜度和空間複雜度與數組A的資料範圍（A中元素的最大值與最小值的差加上1）有關，是以對于資料範圍很大的數組，計數排序需要大量時間和記憶體。
例如：對0到99之間的數字進行排序，計數排序是最好的算法，然而計數排序并不适合按字母順序排序人名，将計數排序用在基數排序算法中，能夠更有效的排序資料範圍很大的數組。
基數排序(Radix Sort)
基數排序的發明可以追溯到1887年赫爾曼·何樂禮在打孔卡片制表機上的貢獻。它是這樣實作的：将所有待比較正整數統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始進行基數為10的計數排序，一直到最高位計數排序完後，數列就變成一個有序序列（利用了計數排序的穩定性）。
基數排序的實作代碼如下：
/**
* 分類 ------------- 内部非比較排序
* 資料結構 ---------- 數組
* 最差時間複雜度 ---- O(n * dn)
* 最優時間複雜度 ---- O(n * dn)
* 平均時間複雜度 ---- O(n * dn)
* 所需輔助空間 ------ O(n * dn)
* 穩定性 ----------- 穩定
*/
public static void radixSort(int[] data, int radix, int d) {
// 緩存數組
int[] tmp = new int[data.length];
// buckets用于記錄待排序元素的資訊
// buckets數組定義了max-min個桶
int[] buckets = new int[radix];
for (int i = 0, rate = 1; i < d; i++) {
// 重置count數組，開始統計下一個關鍵字
Arrays.fill(buckets, 0);
// 将data中的元素完全複制到tmp數組中
System.arraycopy(data, 0, tmp, 0, data.length);
// 計算每個待排序資料的子關鍵字
for (int j = 0; j < data.length; j++) {
int subKey = (tmp[j] / rate) % radix;
buckets[subKey]++;
}
for (int j = 1; j < radix; j++) {
buckets[j] = buckets[j] + buckets[j - 1];
}
// 按子關鍵字對指定的資料進行排序
for (int m = data.length - 1; m >= 0; m--) {
int subKey = (tmp[m] / rate) % radix;
data[--buckets[subKey]] = tmp[m];
}
rate *= radix;
}
}
下圖給出了對{ 329, 457, 657, 839, 436, 720, 355 }進行基數排序的簡單示範過程
基數排序的時間複雜度是O(n * dn)，其中n是待排序元素個數，dn是數字位數。這個時間複雜度不一定優于O(n log n)，dn的大小取決于數字位的選擇（比如比特位數），和待排序資料所屬資料類型的全集的大小；dn決定了進行多少輪處理，而n是每輪處理的操作數目。
如果考慮和比較排序進行對照，基數排序的形式複雜度雖然不一定更小，但由于不進行比較，是以其基本操作的代價較小，而且如果适當的選擇基數，dn一般不大于log n，是以基數排序一般要快過基于比較的排序，比如快速排序。由于整數也可以表達字元串（比如名字或日期）和特定格式的浮點數，是以基數排序并不是隻能用于整數排序。
桶排序(Bucket Sort)
桶排序也叫箱排序。工作的原理是将數組元素映射到有限數量個桶裡，利用計數排序可以定位桶的邊界，每個桶再各自進行桶内排序（使用其它排序算法或以遞歸方式繼續使用桶排序）。
桶排序的實作代碼如下：
/**
* 分類 ------------- 内部非比較排序
* 資料結構 --------- 數組
* 最差時間複雜度 ---- O(nlogn)或O(n^2)，隻有一個桶，取決于桶内排序方式
* 最優時間複雜度 ---- O(n)，每個元素占一個桶
* 平均時間複雜度 ---- O(n)，保證各個桶内元素個數均勻即可
* 所需輔助空間 ------ O(n + bn)
* 穩定性 ----------- 穩定
*/
public static void bucketSort(int[] arr){
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
//桶數
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
//将每個元素放入桶
for(int i = 0; i < arr.length; i++){
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
//對每個桶進行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}
System.out.println(bucketArr.toString());
}
下圖給出了對{ 29, 25, 3, 49, 9, 37, 21, 43 }進行桶排序的簡單示範過程
桶排序不是比較排序，不受到O(nlogn)下限的影響，它是鴿巢排序的一種歸納結果，當所要排序的數組值分散均勻的時候，桶排序擁有線性的時間複雜度。
Refrence:
https://blog.csdn.net/apei830/article/details/6596104
https://mp.weixin.qq.com/s/kZmhNZqXxxyv1zEPuF77Ig