losophy

计数排序

发表于 更新于

假如 H 省有 80 万考生，如何通过成绩快速排序得出排名呢？

计数排序

计数排序是一种稳定的排序算法。 它的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。但是，计数排序也是很高冷！作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

沿用上面的例子。考生的满分是 750 分，最小是 0 分，符合我们之前说的条件：数据范围小且是整数。我们可以划分为 751 个桶分别对应分数为 0 ~ 750 分数的考生。
接着开始遍历考生数据，每个考生按照分数则划分到对应数组下标，相同数组的下标则将该下标的数据值 + 1。其实就是每个数组下标位置对应的是数列数据出现的次数，最后直接遍历该数组，输出元素的下标就是对应的分数，下标对应的元素值是多少我们就输出几次。
桶内的数据都是分数相同的考生，所以并不需要再进行排序。我们只需要依次扫描每个桶，将桶内的考生依次输出到一个数组中，就实现了 80 万考生的排序。因为只涉及扫描遍历操作，所以时间复杂度是 O(n)。

计数排序

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int[] countSort(int[] A) {
    // 找出数组A中的最大值
    int max = Integer.MIN_VALUE;
    for (int num : A) {
        max = Math.max(max, num);
    }
    // 初始化计数数组count
    int[] count = new int[max+1];
    // 对计数数组各元素赋值
    for (int num : A) {
        count[num]++;
    }
    // 创建结果数组
    int[] result = new int[A.length];
    // 创建结果数组的起始索引
    int index = 0;
    // 遍历计数数组，将计数数组的索引填充到结果数组中
    for (int i=0; i<count.length; i++) {
        while (count[i]>0) {
            result[index++] = i;
            count[i]--;
        }
    }
    // 返回结果数组
    return result;
}

如果我们要输出的不仅仅是分数还有学生信息呢，比如说从小到大输出所有学生的姓名和分数，那么这个时候也只要做一点小小的变动。
我们用一个结构体去表示一个学生，如下：

1
2
3
4
5
typedef struct students{ 
    char name[15];
    unsigned int score;
    students *next;
}student;

排序的过程中，我们依次遍历所有的学生分数，假设某个学生的分数为 i ,那么就在 score[i] 的后面插入该学生的节点。排完序后再按每个分数组打印链表中的学生姓名和分数。

适用场景

需要排序的元素必须是整数，二是排序元素的取值要在一定范围内（例子是0-750。如果只排350-750分段，数组长度需要删减），并且比较集中。只有这两个条件都满足，才能最大程度发挥计数排序的优势。

计数排序与桶排序

其实计数排序是桶排序的一种特殊情况（桶不用再排序）。 桶排序的核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

相关文章