共计 2591 个字符，预计需要花费 7 分钟才能阅读完成。
不基于比拟的排序，核心思想就是桶排序，工夫复杂度都是 O(N)，常见的不基于比拟的排序有 计数排序、基数排序。
一、计数排序
实用于排序元素的值 范畴比拟小的，且是整数。（例如：年龄）
1、外围思路：
（1）先筹备一个无限个数（比方 200）的整型辅助数组，挨个遍历原始数组，失去的值是 i，则将辅助数组 i 地位的值加一
（2）遍历辅助数组，如果数组地位 i 上的值是 k，则输入 k 个 i，失去的即是排好序的数组
2、具体参考代码：
/**
* @author Java 和算法学习：周一
*/
public static void countSort(int[] arr) {if (arr == null || arr.length < 2) {return;}
// 统计
int max = Integer.MIN_VALUE;
for (int v : arr) {max = Math.max(max, v);
}
int[] bucket = new int[max + 1];
for (int v : arr) {bucket[v]++;
}
// 排序
int i = 0;
for (int j = 0; j < bucket.length; j++) {while (bucket[j]-- > 0) {arr[i++] = j;
}
}
}
从第一步中就能看进去，如果排序的值跨度比拟大，那么得筹备一个很大的辅助数组，然而数组绝大部分都是空着的，所以极大的节约空间，由此也能看出计数排序的局限性。
二、基数排序
实用于十进制正整数。
1、外围思路：
（1）遍历整个数组，失去最大值的十进制位数，同时将不满足最大位数的数高位补 0
（2）筹备十个桶，从 0 – 9 编号，每个桶大小为原数组大小
（3）遍历数组，以个位数为规范，个位数的值是 i，则将其放到第 i 号桶里；遍历完后，从 0 号桶开始，挨个将外面的数倒进去（先进先出）。此时的数是依据个位数排序
（4）遍历数组，以十位数为规范，十位数的值是 i，则将其放到第 i 号桶里；遍历完后，从 0 号桶开始，挨个将外面的数倒进去（先进先出）。此时的数是依据十位数排序
……直到遍历到最高位，最初倒进去的数即已排好序。
理论代码编写的时候，并没有筹备十个桶，而是筹备的一个长度为 10 的数组，这样能够大大节俭空间。
2、具体参考代码：
/**
* @author Java 和算法学习：周一
*/
public static void radixSort(int[] arr) {if (arr == null || arr.length < 2) {return;}
sort(arr, 0, arr.length - 1, maxBit(arr));
}
/**
* 查找数组最大十进制位数
*/
public static int maxBit(int[] arr) {
int max = Integer.MIN_VALUE;
for (int value : arr) {max = Math.max(max, value);
}
int res = 0;
while (max != 0) {
res++;
max /= 10;
}
return res;
}
private static void sort(int[] arr, int l, int r, int digit) {
int radix = 10;
// 辅助数组
int[] help = new int[r - l + 1];
// 有多少位就进桶几次、出桶几次
for (int d = 1; d <= digit; d++) {// 前缀和数组：count[i]以后位（d 位）是 [0-i] 的数有多少个
int[] count = new int[radix];
// 统计此时数组 d 位上的数各呈现了几次，for (int i = l; i <= r; i++) {// 失去 d 位上的值，范畴[0,9]
int v = getDigit(arr[i], d);
count[v]++;
}
// 此时，count[i]示意以后位（d 位）是 [0-i] 的数有多少个
for (int i = 1; i < radix; i++) {count[i] = count[i] + count[i - 1];
}
// 从右到左出桶
for (int i = r; i >= l; i--) {
// 失去 d 位上的值
int v = getDigit(arr[i], d);
help[--count[v]] = arr[i];
}
// 拷贝回原数组
for (int i = 0; i < help.length; i++) {arr[l + i] = help[i];
}
}
}
public static int getDigit(int x, int d) {return ((x / ((int) Math.pow(10, d - 1))) % 10);
}
三、基于比拟的排序和不基于比拟的排序比照
基于比拟的排序适用范围更广（任何状况都能够），但工夫复杂度极限是 O(N*logN)
不基于比拟的排序适用范围很窄，但工夫复杂度更好 O(N)
本文全副代码：https://github.com/monday-pro/algorithm-study/tree/master/src/basic/nocomparesort
