上一篇总结了常用的比较排序算法，主要有冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
这篇文章中我们来探讨一下常用的非比较排序算法：计数排序，基数排序，桶排序。在一定条件下，它们的时间复杂度可以达到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