百万考生分数如何排序 – 计数排序

关注「码哥字节」，这里有算法系列、大数据存储系列、Spring 系列、源码架构拆解系列、面试系列……敬请期待。设置星标不迷路

其实计数排序是桶排序的一种非凡状况。 桶排序的核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再独自进行排序。桶内排完序之后，再把每个桶里的数据依照程序顺次取出，组成的序列就是有序的了。

「码哥字节」之前分享了百万订单如何依据金额排序，就是使用了桶排序。

计数排序的外围在于将输出的数据值转换成键保留在数组下标，所以作为一种线性工夫复杂度的排序，输出的数据必须是 有确定且范畴不大的整数。比方当要排序的 n 个数据，所处的范畴不大的时候，最大值是 m，咱们就把数据化划分成 m 个桶。每个桶内的数据都是雷同的大小，也就不须要桶内排序，这是与桶排序最大的区别。

场景重现

高考查分数零碎，零碎会展现咱们的问题以及所在省的排名。如果 H 省有 80 万考生，如何通过问题疾速排序得出排名呢？

再比方统计每个省人口的每个年龄人数并且从小到大排序，又如何实现呢？

考生的满分是 750 分，最小是 0 分，合乎咱们之前说的条件：数据范畴小且是整数。咱们能够划分为 751 个桶别离对应分数为 0 ~ 750 分数的考生。

接着开始遍历考生数据，每个考生依照分数则划分到对应数组下标，雷同数组的下标则将该下标的数据值 + 1。其实就是每个数组下标地位对应的是数列数据呈现的次数，最初间接遍历该数组，输入元素的下标就是对应的分数，下标对应的元素值是多少咱们就输入几次。

桶内的数据都是分数雷同的考生，所以并不需要再进行排序。咱们只须要顺次扫描每个桶，将桶内的考生顺次输入到一个数组中，就实现了 80 万考生的排序。因为只波及扫描遍历操作，所以工夫复杂度是 O(n)。

计数排序的算法思维就是这么简略，跟桶排序十分相似，只是桶的大小粒度不一样。不过，为什么这个排序算法叫“计数”排序呢？“计数”的含意来自哪里呢？

刚刚所说的是奢侈版的排序，只是简略的依照统计数组的下标输入元素值，并没有给原始数列进行排序。

在事实中，给学生排序遇到雷同分数的就分不清谁是谁？比方并列 95 分的张无忌与周芷若，却不晓得是张无忌哪个是周芷若。带着这些问题，请持续看上面的图解思路……

图解思路

为了不便了解，对数据进行简化，假如只有 8 个考生，分数在 0 ~ 5 之间，所以有 5 个桶对应考生分数，值代表每种分数的考生个数。考生的原始数据咱们放在数组 SourceArray[8] = {2，5，3，0，2，3，0，3}。

考生的问题从 0 到 5，应用 大小数组为 6 的 countArray[6] 示意桶，下标对应分数，值存储的是该分数的考生个数。咱们只有遍历一遍原始数据就能够失去 countArray[6]。

能够晓得，分数为 3 分的学生有 3 个，< 3 分的学生有 4 个，所以问题 = 3 分的学生在排序后的有序数组 sortedArray[8] 中的下标会在 4, 5, 6 的地位，也就是排名是 5,6,7。如下图所示

咱们如何计算出每个分数的考生在有序数组对应的存储地位呢？这个思路很奇妙，次要是对之前的 countArray[6] 做一下转换。

划重点了同学们：咱们对 countArray[6] 数组程序求和，countArray[k] 外面存储的是 ≤ k 分数的考生个数 。这样加的目标是什么？

其实是让统计数组存储的元素值，等于相应考试成绩数据的最终排序地位的序号。

当初我就要讲计数排序中最简单、最难了解的一部分了，保持啃下来。

1. 从后往前遍历原始输出数组 SourceArray[8] = {2，5，3，0，2，3，0，3}，扫描问题为 3 的小强，咱们就从 数组 countArray[6] 中取出下标 = 3 的值 = 7，也就意味着包含本人在内，分数 ≤ 3 的考生有 7 位，示意在 sortedArray 中排在第七位，当把小强问题放到 sortedArray 之后 ≤ 3 的问题就剩下 6 个了，所以 countArray[3] 要 – 1，变成 6.
2. 遍历成绩表倒数第二个数据，问题是 0，找到在 countArray[0] 的元素 = 2，示意排名第二，同时 countArray[0] 的元素值 -1。
3. 以此类推，当扫描残缺个原始数组之后，sortedArray 数据就是依照分数从小到大有序排列了。

代码实战

整个步骤:

1. 查找数列最大值。
2. 依据数列最大值确定 countArray 统计数组长度。
3. 遍历原始数据填充统计数组，统计对应元素的个数。
4. 统计数组做变形，前面的元素等于后面元素之和。
5. 倒序遍历原始数组，从统计数组中找到元素的正确排位，输入到后果数组中。

源码详见 GitHub: https://github.com/UniqueDong…

package com.zero.algorithms.linear.sort;

/**
 * 公众号：码哥字节
 * 计数排序
 */
public class CountingSort {public int[] sort(int[] sourceArray) {if (sourceArray == null || sourceArray.length <= 1) {return new int[0];
        }
        // 1. 查找数列最大值
        int max = sourceArray[0];
        for (int value : sourceArray) {max = Math.max(max, value);
        }
        // 2. 依据数据最大值确定统计数组长度
        int[] countArray = new int[max + 1];
        // 3. 遍历原始数组映射到统计数组中, 统计元素的个数
        for (int value : sourceArray) {countArray[value]++;
        }
        // 4. 统计数组变形，前面的元素等于后面元素之和。目标是定位在后果数组中的排位
        for (int i = 1; i <= max; i++) {countArray[i] += countArray[i - 1];
        }
        // 5. 倒序遍历原始数组，从统计数组查找对应的正确地位，输入到后果表
        int[] sortedArray = new int[sourceArray.length];
        for (int i = sourceArray.length - 1; i >= 0; i--) {int value = sourceArray[i];
            // 分数在 countArray 中的排名, - 1 则是后果数组的下标
            int index = countArray[value] - 1;
            sortedArray[index] = value;
            countArray[value]--;
        }
        return sortedArray;
    }
}

复杂度剖析

第 1、3、5 步都波及遍历原始数组，工夫复杂度都是 O(n)，第 4 步统计数组变形，工夫复杂度是 O(m)，所以总体的工夫复杂度是 O(3n +m)，去掉系数 O(n) 工夫复杂度。

空间复杂度，后果数组 O(n)。

优化思路

后面的代码，第一步咱们查找最大值，如果原始数据是 {99,98,92,80,88,87,82,88,99,97,92}, 最大值是 99，最小值是 80，如果间接创立 100 长度的数组，那么 从 0 到 79 的空间全都节约了。

要怎么解决呢？

跟着「码哥字节」来优化，很简略，咱们不再应用 max + 1 作为统计数组的长度，而是 max – min + 1 作为统计数组的长度即可。

代码如下:

package com.zero.algorithms.linear.sort;

/**
* 公众号：码哥字节
* 计数排序
*/
public class CountingSort {public int[] sort(int[] sourceArray) {if (sourceArray == null || sourceArray.length <= 1) {return new int[0];
       }
       // 1. 查找数列最大值, 最小值
       int max = sourceArray[0];
       int min = sourceArray[0];
       for (int value : sourceArray) {max = Math.max(max, value);
           min = Math.min(min, value);
       }
       int d = max - min;
       // 2. 依据数据最大值确定统计数组长度
       int[] countArray = new int[d + 1];
       // 3. 遍历原始数组映射到统计数组中, 统计元素的个数
       for (int value : sourceArray) {countArray[value - min]++;
       }
       // 4. 统计数组变形，前面的元素等于后面元素之和。目标是定位在后果数组中的排位
       for (int i = 1; i < countArray.length; i++) {countArray[i] += countArray[i - 1];
       }
       // 5. 倒序遍历原始数组，从统计数组查找对应的正确地位，输入到后果表
       int[] sortedArray = new int[sourceArray.length];
       for (int i = sourceArray.length - 1; i >= 0; i--) {int value = sourceArray[i];
           // 分数在 countArray 中的排名, - 1 则是后果数组的下标
           int index = countArray[value - min] - 1;
           sortedArray[index] = value;
           countArray[value - min]--;
       }
       return sortedArray;
   }
}

总结一下

计数排序实用于在数据范畴不大的场景中，并且只能给非负整数排序，对于其余类型的数据，要排序的话要在不扭转绝对大小的状况下，转成非负整数。

比方数据范畴 [-1000, 1000]，就对每个数据 +1000，转换成非负整数。

计数排序这么弱小，然而局限性次要有如下两点：

1. 当数列的最大与最小值差距过大，不适宜应用计数排序。

比方 20 个随机整数，范畴在 0 – 1 亿之间，这时候应用计数排序须要创立长度为 1 亿的数组，重大节约空间。

1. 数列元素不是整数，不适宜应用

参考资料

极客工夫《数据结构与算法之美》

漫画算法 - 小灰的算法之旅

关注「码哥字节」后盾回复加群，可增加集体微信进入专属技术群。

读者的分享、点赞、在看、珍藏三连是最大的激励

顺手点击下方广告，给「码哥」加鸡腿。