桶排序、计数排序、基数排序 是三种不基于比较的时间复杂度为O(n)的排序算法。
桶排序 Bucket Sort
桶排序的核心思想是：将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
时间复杂度的分析：将n个数据均匀分入m个桶中，每个桶有k=n/m个数据。对每个桶进行快速排序，每个桶的复杂度是O(klogk)，所以总时间复杂度是O(mklogk)，即O(nlogk)。
当n和m接近时，logk近似为很小的常数。在这种情况下，时间复杂度为O(n)。
从时间复杂度的分析中可以看出桶排序存在很多使用时的限制：
数据能够被很容易地分进m个桶中，且数据在各个桶中时均匀分布的。
桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。
计数排序 Counting Sort
public class CountingSort {
public static void sort(int[] arr) {
if (arr.length == 0) {
return;
}
// 初始化计数数组
int[] countArr = initCountArr(arr);
// 临时数组，存储排序后结果
int[] tempArr = new int[arr.length];
// 从尾遍历原数组，根据计数数组，将遍历元素放入临时数组中排序后位置
for (int i = arr.length - 1; i >= 0; i--) {
tempArr[countArr[arr[i]] - 1] = arr[i];
countArr[arr[i]]--;
}
// 临时数组覆盖原数组
for (int i = 0; i < arr.length; i++) {
arr[i] = tempArr[i];
}
}
// 初始化计数数组
private static int[] initCountArr(int[] arr) {
// 确定被排序数组的范围
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
// 初始化一个元素全为0的计数数组
int[] countArr = new int[max + 1];
// 开始统计每个元素出现的次数
for (int i = 0; i < arr.length; i++) {
countArr[arr[i]]++;
}
// 累加计算次数和
for (int i = 1; i < countArr.length; i++) {
countArr[i] += countArr[i - 1];
}
return countArr;
}
}
计数排序的原理很简单，统计每个元素出现的次数构造计数数组，从尾遍历原数组，根据计数数组中的数据将遍历元素放入临时数组中排序后位置，遍历结束后，临时数组就是排序后的结果。
计数数组存储小于等于索引值的元素个数；例如countArr[3]==7，表示原数组中小于等于3的元素有7个，所以可以把3放入临时数组第7位，即tempArr[6]。放入后原数组中小于等于3的元素就少了一个，所以countArr[3]需要自减1。
计数排序同样存在很多限制：
数据范围不能太大；只能对非负整数进行排序（若不是非负整数，需要预处理进行转化再排序）
适用场景：排序100万考生的考试成绩。
基数排序 Radix Sort
基数排序的原理是：将要排序的数据按照分割好的“位”进行独立排序，从低位到高位。
举个例子：从小到大排序100万个手机号码。
手机号码是存在高低位关系的，比较两个手机号码时，开头前几位大的号码必然是两者中更大的。
我们可以从后往前按“位”排序，当排到手机号第一位时，100万手机号码就被排序好了。
基数排序同样存在很多限制：
- 基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。
- 对每一“位”独立排序时需要使用稳定的排序算法。
- 若需要排序的数据长度不同，需要进行补全，补成相同长度。
- 除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。
