共计 1499 个字符，预计需要花费 4 分钟才能阅读完成。
1. 回顾
前面已经说完了几种非线性排序，它们分别是时间复杂度为 O(n2)、适合小规模数据的冒泡排序、选择排序、插入排序，和应用较广泛的时间复杂度为 O(nlogn) 的希尔排序、归并排序、快速排序。其实这几种排序都有一个特性，那就是它们都是基于数据的比较和移动，而今天介绍的这几种线性排序，他们的时间复杂度都是 O(n)，因为不涉及到数据的比较和移动。
2. 桶排序
桶排序的思路是：将要排序的数据按照一定的范围划分到有序的桶内，在桶内进行排序，然后依次从桶中将数据取出来，这样整个数据就有序了。
例如我们要排序一组大小在 [0 – 50] 的数据，可以划分 5 个桶，每个桶存放的数据范围为：[1 – 10]、[11-20]、[21 – 30] 以此类推，就像下图这样：然后在将桶内的数据排序，依次取出来，整个数据就有序了。
实际上，桶排序的应用场景十分的有限，对数据的要求比较苛刻。首先，它要求每个桶的数据范围是有序的，就像上面那样依次排列，这样才能够保证从桶中取出的数据仍然保持有序，其次，要保证数据较为均匀的划分到各个桶中，如果出现数据集中到某个或几个桶内，那么时间复杂度就会下降。极端情况下，如果数据全部划分到一个桶内，就变成了非线性排序了。
下面我模拟了一个简单的桶排序：
public class BucketSort {
// 测试场景：数组中有 10000 个数据，范围在 0 -100000 之间
// 使用 100 个桶，每个桶存放的数据范围为：0-999, 1000-1999, 2000-2999，依次类推
public static void bucketSort(int[] data){
// 新建 100 个桶，使用 ArrayList 作为桶
ArrayList<ArrayList<Integer>> buckets = new ArrayList<>(100);
for (int i = 0; i < 100; i++) {
buckets.add(new ArrayList<>());
}
// 遍历数组，将数据放置到桶中
for (int i = 0; i < data.length; i++) {
buckets.get(data[i] / 1000).add(data[i]);
}
// 在桶内部进行排序
int k = 0;
for (int i = 0; i < buckets.size(); i++) {
ArrayList<Integer> list = buckets.get(i);
Integer[] integers = list.toArray(new Integer[10]);
Arrays.sort(integers);
// 拷贝到 data 中
for (int j = 0; j < integers.length; j++) {
data[k ++] = integers[j];
}
}
}
}
2. 计数排序
计数排序其实是桶排序的一种特殊情况，假如要排序的数据范围不大，例如为 n，那么我们可以划分 n 个桶，每个桶内存放数值相同的数据，然后再遍历取出来，这样整个数据就有序了。
例如我们需要根据年龄给 10 万人排序，年龄的范围其实不大，我们可以假设年龄最小为 0，最大为 120，那么我们直接划分 121 个桶，遍历数组，将年龄相同的数据存放到同一个桶中，然后取出来，就完成了排序。是不是很简单呢？
这里我就不代码演示了，和上面的桶排序非常的类似，就是没有了桶内排序的这个部分，你可以自己尝试写一下。
3. 基数排序
再来看看基数排序，假如我们要对 10 万个手机号码进行排序，应该怎么做呢？手机号码有 11 位，太长，不适合用桶排序或是计数排序。借助于稳定排序，我们可以从号码的最后一位开始比较，比较 11 次。因为借助的是稳定排序，所以前面的排序顺序不会被打乱，我用了一个简单的字符数组来模拟这个过程：
