35 - 范围排序的神器：计数排序

鱼C-小师妹

上一讲的堆排序应该会难倒很多可爱的鱼油吧～

抽象思维不够，就一定要多上手实践，一步一步按规则对数据进行处理，会帮你理解算法的玩法。

这次我们换个思路，不像之前一样基于数据之间先比较再交换。

因为并不是所有排序都必须进行交换，就像这讲的主角：计数排序。

这个排序的基本思想就是：

将待排序数据值转换为键，存储在额外开辟的数组空间中。

计数排序要求输入的数据必须是有确定范围的整数，因此计数排序法适用于量大、范围小的数据。

例如一定范围内的成绩排名，身高统计等等。

假设有这样的一个考试排名：

1. 96，93，99，90，91，92，93，90

复制代码

我们就采用计数排序进行从小到大的递增排序。

首先我们要找到最大值 99 和最小值 90，确定范围为 90 到 99。

那么就需要准备 99-90+1 个计数器，即 10 个计数器，编号从 90 到 99。

计数器就是用来统计每个数出现的次数。

示意图如下所示：



接下来我们将对应数字放到计数器中，放入一个计数加 1。

第一个数字 96，放到 96 号计数器中，计数加 1：



以此类推将所有数字放到计数器中并计数后：



按照计数器编号依次将数据取出：



此时所有数据就已经排好序啦～

我们用 Python 来实现上述过程。

基础部分还是和之前一样：

1. data = [96,93,99,90,91,92,93,90]
   
2. print("原始数据：")
   
3. for k in range(len(data)):
   
4.     print(f"{data[k]}",end=' ')
   
5. data2 = countSort(data)
   
6. print('\n----我是分界线------\n')
   
7. print("计数排序后结果：")
   
8. for k in range(len(data2)):
   
9.           print(f"{data2[k]}",end=' ')

复制代码

来实现核心的 countSort() 部分。

首先要找到待排序列表中的最大值 max_num，开辟一个长度为 k+1 的计数列表，计数列表中的值都为 0。

1. def countSort(array):
   
2.     if len(array) < 2:
   
3.         return array
   
4.     max_num = max(array)
   
5.     count = [0] * (max_num + 1)

复制代码

遍历待排序列表，如果遍历到的元素值为 num，则计数列表中索引 num 的值加 1：

1.     for num in array:
   
2.         count[num] += 1

复制代码

接下来就要遍历完整待排序列表，计数列表中索引 i 的值 j，表示 i 的个数为 j，统计出待排序列表中每个值的数量。

先要创建一个新列表，遍历计数列表，依次在新列表中添加 j 个 i，新列表就是排好序后的列表。

而这个过程中我们就不需要比较待排序列表中的数据大小：

1. new_array = list()
   
2.     for i in range(len(count)):
   
3.         for j in range(count[i]):
   
4.             new_array.append(i)
   
5.     return new_array

复制代码

运行看结果：



童鞋们现在应该理解为什么一开始说计数排序适用于“量大、范围小”的数据。

因为创建计数器是基于最大值和最小值，如果范围太大，如此排序反而效率降低啦。

好了，下课！

源码：

游客，如果您要查看本帖隐藏内容请回复

andy大宝

沙发

Hyjxsssss

done

hornwong

憨憨学py

def countSort(array):
    if len(array) < 2:
        return array
    max_num = max(array)
    print(max_num)
    count = [0] * (max_num + 1)
    for num in array:
        count[num] += 1
    new_array = list()
    for i in range(len(count)):
        for j in range(count[i]):
            new_array.append(i)
    return new_array


data = [96, 93, 99, 90, 91, 92, 93, 90]
print("原始数据：")
for k in range(len(data)):
    print(f"{data[k]}", end=' ')
data2 = countSort(data)
print('\n----我是分界线------\n')
print("计数排序后结果：")
for k in range(len(data2)):
    print(f"{data2[k]}", end=' ')