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

ifwinds 2019-07-01

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 次。因为借助的是稳定排序,所以前面的排序顺序不会被打乱,我用了一个简单的字符数组来模拟这个过程:

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

相关推荐