排序三：桶排序、计数排序、基数排序

这一篇我们来看三种时间复杂度为O(n)的排序算法：桶排序、计数排序、基数排序。我们把这类时间复杂度为O(n)的排序算法叫做线性排序。这类排序算法之所以能够做到线性时间，其实是因为它们都不是基于比较来实现排序的。

1. 桶排序

1.1 什么是桶排序

桶排序的基本思想就是将数据拆分到多个有大小区分的桶里面，然后分别对每个桶里面的数据进行排序，完成每个桶里面的数据的排序之后，按照桶与桶之间的数据的大小关系，依次合并数据就得到了所要的有序序列


桶排序过程示意图

1.2 桶排序的性能分析

假设我们要将n条数据进行排序，如果我们有m个桶，我们把这n条数据均匀的划分到这m个桶里面，每个桶里的数据就是k=n/m。然后我们对每个桶使用快速排序进行排序，时间复杂度就是O(klogk)。m个桶总的时间复杂度就是O(mklogk)。因为k=n/m。所以整个事件复杂度就是O(nlog(n/m))。当m接近n的时候，log(n/m)就是一个非常小的常数，整个桶排序的时间复杂度就接近O(n)。

它的空间复杂度O(n)，但是并不是需要两倍的数据内存才能进行排序，因为排序过程中存储的只是实际数据的索引

桶内排序时选用稳定排序算法，则它就能做到稳定排序

1.3 桶排序对数据的特殊要求

桶排序看起来很快，但是要达到O(n)的时间复杂度，它对待排序的数据是有要求的

  1. 首先，待排序的数据需要能很容易的划分成m个桶，并且桶与桶之间要有天然的大小关系。
  2. 其次，数据在各个桶之间的分布要是比较均匀的。如果数据经过划分之后，有些桶里面的数据非常多，有些非常少，那桶内排序的时间复杂度就不是常量级的。极端情况下，如果数据全部在一个桶里面的话，算法的复杂度就退化成了O(nlogn)

1.4 桶排序的算法实现

桶排序的实现思路

  1. 根据数据范围和预估的桶的数据容量计算桶的个数，申请桶空间
  2. 将待排序的数据划分到各个桶中
  3. 对每个桶进行排序
  4. 合并排序之后的桶中的数据

完整代码如下

public static void sort(int[] array, int bucketSize) {
    if (array == null || array.length < 2) {
        return;
    }
    //计算用多少个桶来装数据
    int min = array[0];
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] < min) {
            min = array[i];
        } else if (array[i] > max) {
            max = array[i];
        }
    }
    System.out.println("min:" + min);
    System.out.println("max:" + max);
    int bucketCount = (max - min) / bucketSize + 1;
    System.out.println("bucketCount:" + bucketCount);
    //申请桶空间
    int[][] buckets = new int[bucketCount][bucketSize];
    int[] indexArray = new int[bucketCount];
    //将数据装入桶里面
    for (int i = 0; i < array.length; i++) {
        int bucketIndex = (array[i] - min) / bucketSize;
        if (indexArray[bucketIndex] == buckets[bucketIndex].length) {// buckets[bucketIndex]满了，需要扩容
            ensureCapacity(buckets, bucketIndex);
        }
        buckets[bucketIndex][indexArray[bucketIndex]] = array[i];
        indexArray[bucketIndex]++;
    }
    //对每个桶进行排序
    int k = 0;
    for (int i = 0; i < bucketCount; i++) {
        sort(buckets[i], 0, indexArray[i] - 1);
        //合并桶中的数据
        for (int j = 0; j < indexArray[i]; j++) {
            array[k++] = buckets[i][j];
        }
    }
}

private static void sort(int[] a, int left, int right) {
    if (left < right) {
        int low = left;
        int hight = right;
        int pivot = a[low];
        //找到分区点的位置
        while (low < hight) {//有元素之间的位置交换，所以不是稳定排序
            while (low < hight && a[hight] >= pivot) {
                hight--;
            }
            a[low] = a[hight];
            while (low < hight && a[low] <= pivot) {
                low++;
            }
            a[hight] = a[low];
        }
        a[low] = pivot;
        //对左右两个分区进行排序
        if (left + 1 < low) {
            sort(a, left, low - 1);
        }
        if (right - 1 > low) {
            sort(a, low + 1, right);
        }
    }
}

private static void ensureCapacity(int[][] buckets, int bucketIndex) {
    int[] tempArr = buckets[bucketIndex];
    int[] newArr = new int[tempArr.length * 2];
    for (int j = 0; j < tempArr.length; j++) {
        newArr[j] = tempArr[j];
    }
    buckets[bucketIndex] = newArr;
}

1.5 桶排序的实际应用

桶排序比较适合用在外部排序中。比如说有10GB的订单数据需要按照订单金额进行排序，但是能够使用的内容只有1GB，没有办法一次把所有数据都加载到内存中来，这个时候就可以使用桶排序

具体怎么做呢？

  1. 先扫描一遍记录，查看订单金额的数据范围。假设订单的金额范围是1-10万元，我们可以把数据划分到100个桶里面，第一个桶存储1元-1000元之间的订单，第二个桶存储1001-2000之间的订单，依次内推。
  2. 然后我们再次遍历订单记录，开始加载我们第一个桶需要的数据进行排序，排好序之后写入到编号为001的桶中。然后在加载第二个桶的数据排序，依次类推。
  3. 待所有桶中的数据都排序好了之后，依次读取这排序好的100个文件中的订单数据，写入到一个文件中，这样文件中存储的就是金额从小到大排序的订单数据了

如果某个桶的数据规模过大，依然无法用1GB的内存排序如何处理？

再次对这个桶中的数据进行拆分处理。比如订单在1-1000元的记录特别多，我们可以继续将它划分为1-100,101-200，……901-1000。然后以同样的方式去排序

什么是外部排序

外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。

1.6 简单示例

使用桶排序给交易记录按照价格来进行排序，我们把加一记录简化成只有价格和编号id的方式

交易记录

public static class Record {
        private int money;
        private String id;
        ...
    }

桶排序算法

public static void sort(Record[] array, int bucketSize) {
    if (array == null || array.length < 2) {
        return;
    }
    //计算用多少个桶来装数据
    int min = array[0].money;
    int max = array[0].money;
    for (int i = 1; i < array.length; i++) {
        if (array[i].money < min) {
            min = array[i].money;
        } else if (array[i].money > max) {
            max = array[i].money;
        }
    }
    System.out.println("min:" + min);
    System.out.println("max:" + max);
    int bucketCount = (max - min) / bucketSize + 1;
    System.out.println("bucketCount:" + bucketCount);
    //申请桶空间
    Record[][] buckets = new Record[bucketCount][bucketSize];
    int[] indexArray = new int[bucketCount];
    //将数据装入桶里面
    for (int i = 0; i < array.length; i++) {
        int bucketIndex = (array[i].money - min) / bucketSize;
        if (indexArray[bucketIndex] == buckets[bucketIndex].length) {// buckets[bucketIndex]满了，需要扩容
            ensureCapacity(buckets, bucketIndex);
        }
        buckets[bucketIndex][indexArray[bucketIndex]] = array[i];
        indexArray[bucketIndex]++;
    }
    //对每个桶进行排序
    int k = 0;
    for (int i = 0; i < bucketCount; i++) {
//            sort(buckets[i], 0, indexArray[i] - 1);//快排，不稳定
        sort2(buckets[i], indexArray[i]);//冒泡，稳定排序
        //合并桶中的数据
        for (int j = 0; j < indexArray[i]; j++) {
            array[k++] = buckets[i][j];
        }
    }
}

/**
 * 冒泡
 *
 * @param array
 */
private static void sort2(Record[] array, int size) {
    if (array == null || array.length == 1) {
        return;
    }
    for (int i = 0; i < size; i++) {
        boolean isExchanged = false;
        for (int j = 0; j < size - i - 1; j++) {//这里的i表示经过了几次冒泡排序了，经过一次有在最后面多了一位已经排好序的元素，所以下一次要比较的范围也较少1
            if (array[j].money > array[j + 1].money) {//只有在后面的元素大于前面的元素的时候才交互，可以保证排序的稳定性
                Record temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
                isExchanged = true;
            }
        }
        if (!isExchanged) {//当某一趟冒泡排序中没有交换发送的时候，说明序列已经有序了
            break;
        }
    }
}

这里我们注意使用稳定排序来做桶内排序，保证排序的稳定性

测试用例

@Test
public void test() {
    int size = 10;
    BucketSortRecord.Record[] array = new BucketSortRecord.Record[size];
    for (int i = 0; i < size; i++) {
        BucketSortRecord.Record person = new BucketSortRecord.Record();
        person.setMoney(10 + new Random().nextInt(size));
        person.setId("record_" + i);
        array[i] = person;
    }
    print(array, "   org:");
    BucketSortRecord.sort(array, 2);
    print(array, "sorted:");
}

测试结果

   org:{money=13, name='record_0'},{money=14, name='record_1'},{money=14, name='record_2'},{money=12, name='record_3'},{money=14, name='record_4'},
sorted:{money=12, name='record_3'},{money=13, name='record_0'},{money=14, name='record_1'},{money=14, name='record_2'},{money=14, name='record_4'},

我们可以看到排序结果是稳定的

2. 计数排序

2.1 什么是计数排序

计数排序可以看做一种特殊的桶排序，每个桶里面的数据都是相同的，也就不用进行同类排序了。当我们要对n个数据进行排序的时候，我们先计算一下它的数据区间，比如最小值是1，最大值是K，则数据区间就是看，然后将这些数据拆分到这k个桶里面，由于每个桶里面的数据都是相同的，所以我们不用进行桶内排序，拆分完成之后，我们再次遍历每个桶，合并数据就得到了要排序的有序序列


计数排序过程示意图

2.2 计算排序的性能分析

计算排序在桶排序的基础上省去了桶内排序，所以它的时间复杂度就是O(n)

它的空间复杂度O(n)

它是稳定排序

2.3 计数排序对数据的特殊要求

计数排序只能用在数据范围不大的场景中，如果数据范围K很大，就不适合使用计数排序了。因为它需要申请与范围同样大小的空间来进行计数，范围太大，内存就可能不够了。

2.4 计数排序的算法实现

计数排序算法实现思路

  1. 计算数据之间的区间，申请计数数组
  2. 遍历待排序数组，计算每个元素的个数，存入计数数组的对应位置
  3. 计算计数数组中元素在将来排好序的序列中的位置
  4. 遍历待排序数组，结合计数数组，将待排序数据存入到存放有序序列的数组的对应位置

算法实现

public static void sort(int[] array) {
    /**
     * 计数排序的的步骤
     * 1. 计算数据之间的区间，申请计数数组
     * 2. 遍历待排序数组，计算每个元素的个数，存入计数数组的对应位置
     * 3. 计算计算数组中元素在将来排好序的序列中的位置
     * 4. 遍历待排序数组，结合计数数组，将待排序数据存入到存放有序序列的数组的对应位置
     */
    if (array == null || array.length < 2) {
        return;
    }
    //1. 计算数据分别的区间，申请计数数组
    int min = array[0];
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] < min) {
            min = array[i];
        } else if (array[i] > max) {
            max = array[i];
        }
    }
    System.out.println("min:" + min);
    System.out.println("max:" + max);
    int interval = max - min;
    System.out.println("interval:" + interval);
    int[] c = new int[interval + 1];
    //2. 遍历待排序数组，计算每个元素的个数，存入计数数组的对应位置
    for (int i = 0; i < array.length; i++) {
        c[array[i] - min]++;
    }
    //3. 计算计算数组中元素在将来排好序的序列中的位置
    for (int i = 1; i < c.length; i++) {
        c[i] = c[i - 1] + c[i];
    }
    //4. 遍历待排序数组，结合计数数组，将待排序数据存入到存放有序序列的数组的对应位置
    int[] temp = new int[array.length];
    for (int i = array.length - 1; i >= 0; i--) {//倒序保证稳定性
        int index = c[array[i] - min] - 1;
        temp[index] = array[i];
        c[array[i] - min]--;
    }
    for (int i = array.length - 1; i >= 0; i--) {
        array[i] = temp[i];
    }
}

2.5 计数排序的实际应用

计数排序可以应用在考试成绩的排名上，比如高考成绩的快速排名。

假如高考总分是900分，最小分时0分，总共有50万名考生，我们就可以将这些学生划分到901个桶里面，由于桶里面的分数相同，所以不同再进行排序，我们只要一次扫描每个桶，将桶内的考生依次输出到一个数组中，就能实现对50万名考生的成绩的排序了。

2.6 简单实例

我们简单的实现一些对考生成绩的排序，这里我们将考生信息简化成只有总成绩和名字两个部分

考生信息

public static class Person {
    private int age;
    private String name;

    ...
}

计数排序算法

public static void sort(Person[] array) {
    /**
     * 计数排序的的步骤
     * 1. 计算数据分别的区间，申请计数数组
     * 2. 遍历待排序数组，计算每个元素的个数，存入计数数组的对应位置
     * 3. 计算计算数组中元素在将来排好序的序列中的位置
     * 4. 遍历待排序数组，结合计数数组，将待排序数据存入到存放有序序列的数组的对应位置
     */
    if (array == null || array.length < 2) {
        return;
    }
    //1. 计算数据分别的区间，申请计数数组
    int min = array[0].age;
    int max = array[0].age;
    for (int i = 1; i < array.length; i++) {
        if (array[i].age < min) {
            min = array[i].age;
        } else if (array[i].age > max) {
            max = array[i].age;
        }
    }
    System.out.println("min:" + min);
    System.out.println("max:" + max);
    int interval = max - min;
    System.out.println("interval:" + interval);
    int[] c = new int[interval + 1];
    //2. 遍历待排序数组，计算每个元素的个数，存入计数数组的对应位置
    for (int i = 0; i < array.length; i++) {
        c[array[i].age - min]++;
    }
    //3. 计算计算数组中元素在将来排好序的序列中的位置
    for (int i = 1; i < c.length; i++) {
        c[i] = c[i - 1] + c[i];
    }
    //4. 遍历待排序数组，结合计数数组，将待排序数据存入到存放有序序列的数组的对应位置
    Person[] temp = new Person[array.length];
    for (int i = array.length - 1; i >= 0; i--) {
        int index = c[array[i].age - min] - 1;
        temp[index] = array[i];
        c[array[i].age - min]--;
    }
    for (int i = array.length - 1; i >= 0; i--) {
        array[i] = temp[i];
    }
}

测试代码

@Test
public void test() {
    int size = 5;
    CountingSortPerson.Person[] array = new CountingSortPerson.Person[size];
    for (int i = 0; i < size; i++) {
        CountingSortPerson.Person person = new CountingSortPerson.Person();
        person.setAge(10 + new Random().nextInt(5));
        person.setName("name_" + i);
        array[i] = person;
    }
    print(array, "   org:");
    CountingSortPerson.sort(array);
    print(array, "sorted:");
}

测试结果

   org:{age=10, name='name_0'},{age=13, name='name_1'},{age=12, name='name_2'},{age=11, name='name_3'},{age=11, name='name_4'},
sorted:{age=10, name='name_0'},{age=11, name='name_3'},{age=11, name='name_4'},{age=12, name='name_2'},{age=13, name='name_1'},

3. 基数排序

3.1 什么是基数排序

基数排序是一种多关键字的排序算法，其中每个关键字可以使用线性排序算法来完成排序，通过依次对每个关键字进行排序之后，就得到了要的有序序列。这里要求每个关键字使用的线性排序要能保证稳定性。

基数排序过程示意图

3.2 基数排序的性能分析

基数排序使用其他线性排序来完成关键字的排序，所以它的时间复杂度也是O(n)，空间复杂度O(n)，它是稳定排序

3.3 基数排序对数据的特殊要求

基数排序对数据的要求:

  1. 待排序的数据必须能够分割成多个关键字来比较，且关键字之间有递进关系，比如a的高位比b的高位大，则a必定大于b。
  2. 关键字的范围不能太大，要可以使用线性排序算法来排序。

3.4 基数排序的算法实现

这里直接编写一个对手机号码进行排序的算法

算法实现思路

  1. 拆分关键字
  2. 分别对每个关键字进行线性排序

代码实现

public static void sort(int[] array) {
    // 从个位开始，对数组arr按"指数"进行排序
    for (int exp = 1; array[0] / exp > 0; exp *= 10) {
        countingSort(array, exp);
    }
}

private static void countingSort(int[] array, int exp) {
    if (array == null || array.length < 2) {
        return;
    }
    //1. 计算数据分别的区间，申请计数数组
    int[] c = new int[10];
    //2. 遍历待排序数组，计算每个元素的个数，存入计数数组的对应位置
    for (int i = 0; i < array.length; i++) {
        c[(array[i] / exp) % 10]++;
    }
    //3. 计算计算数组中元素在将来排好序的序列中的位置
    for (int i = 1; i < c.length; i++) {
        c[i] = c[i - 1] + c[i];
    }
    //4. 遍历待排序数组，结合计数数组，将待排序数据存入到存放有序序列的数组的对应位置
    int[] temp = new int[array.length];
    for (int i = array.length - 1; i >= 0; i--) {//倒序保证稳定性
        int cindex = (array[i] / exp) % 10;
        temp[c[cindex] - 1] = array[i];
        c[cindex]--;
    }
    for (int i = array.length - 1; i >= 0; i--) {
        array[i] = temp[i];
    }
}

测试用例

@Test
public void test1() {
    int size = 10;
    int[] array = new int[size];
    int[] array2 = new int[size];
    for (int i = 0; i < size; i++) {
        int num = 1;
        for (int j = 0; j < 5; j++) {
            num = num * 10 + new Random().nextInt(10);
        }
        array[i] = num;
        array2[i] = num;
    }
    print(array, "   org:");
    print(array2, "   org:");
    RadixSort.sort(array);
    MergeSort.sort(array2);
    print(array, "sorted:");
    print(array2, "sorted:");
}

测试结果

   org:186402,159502,111311,107840,111943,191059,181161,147774,143482,199457,
   org:186402,159502,111311,107840,111943,191059,181161,147774,143482,199457,
sorted:107840,111311,111943,143482,147774,159502,181161,186402,191059,199457,
sorted:107840,111311,111943,143482,147774,159502,181161,186402,191059,199457,

这里我们采用归并排序来做一个结果对比，验证排序的正确性

3.5 基数排序的实际应用

基数排序还可以用在单词的排序中等场景

源码

完整源码和测试用例，请查看github之排序

  1. 桶排序：BucketSort.java、BucketSortTest.java、BucketSortRecord.java、BucketSortRecordTest.java
  2. 计数排序：CountingSort.java、CountingSortTest.java、CountingSortPerson.java、CountingSortPersonTest.java
  3. 基数排序：RadixSort.java、RadixSortTest.java

说明

算法示意图来源：算法动画演示网站

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,937评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,503评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,712评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,668评论 1赞 276
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,677评论 5赞 366
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,601评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,975评论 3赞 396
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,637评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,881评论 1赞 298
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,621评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,710评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,387评论 4赞 319
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,971评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,947评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,189评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 44,805评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,449评论 2赞 342