数据结构与算法——线性排序

1. 回顾

前面已经说完了几种非线性排序，它们分别是时间复杂度为 O(n²) 、适合小规模数据的冒泡排序、选择排序、插入排序，和应用较广泛的时间复杂度为 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 次。因为借助的是稳定排序，所以前面的排序顺序不会被打乱，我用了一个简单的字符数组来模拟这个过程：