Python实现计数排序

Python实现计数排序

一、计数排序简介

计数排序(Counting Sort)是一种不比较数据大小的排序算法，是一种牺牲空间换取时间的排序算法。

计数排序适合数据量大且数据范围小的数据排序，如对人的年龄进行排序，对考试成绩进行排序等。

计数排序先找到待排序列表中的最大值 k，开辟一个长度为 k+1 的计数列表，计数列表中的所有初始值都为 0。走访待排序列表，如果走访到的元素值为 i，则计数列表中索引 i 的值加1，走访完整个待排序列表，就可以统计出待排序列表中每个值的数量。然后创建一个新列表，根据计数列表中统计的数量，依次在新列表中添加对应数量的 i ，得到排好序的列表。

二、计数排序原理

计数排序的原理如下：

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

2. 走访待排序列表，如果走访到的元素值为 i，则计数列表中索引 i 的值加1。

3. 走访完整个待排序列表，计数列表中索引 i 的值 j 表示 i 的个数为 j，统计出待排序列表中每个值的数量。

4. 创建一个新列表，遍历计数列表，依次在新列表中添加 j 个 i，新列表就是排好序后的列表，整个过程没有比较待排序列表中的数据大小。

以列表 [5, 7, 3, 7, 2, 3, 2, 5, 9, 5, 7, 6] 进行升序排列为例。列表的初始状态如下图。

1. 待排序列表中的最大值为9，所以开辟一个长度为10的计数列表，索引为0~9，值全为0。

2. 走访待排序列表，如果走访到的元素值为 i，则计数列表中索引 i 的值加1。第一个元素值为5，计数列表中索引5的值加1，从0变为1。

2. 第二个元素值为7，计数列表中索引7的值加1，从0变为1。

3. 第三个元素值为3，计数列表中索引3的值加1，从0变为1。

4. 第四个元素值为7，计数列表中索引7的值加1，从1变为2。

5. 重复走访完整个待排序列表，所有元素的个数都统计到了计数列表中。

6. 创建一个新列表，遍历计数列表，依次在新列表中添加对应数量的元素。0和1都是0个，不需要添加，2有两个，在新列表中添加两个2。添加后计数列表中减掉对应的数量。

7. 3有两个，继续在新列表中添加两个3。添加后计数列表中减掉对应的数量。

8. 遍历整个计数列表，添加完所有的数据，新列表就是排序完成后的列表。排序结果如下图。

三、Python实现计数排序

# coding=utf-8
def counting_sort(array):
    if len(array) < 2:
        return array
    max_num = max(array)
    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


if __name__ == '__main__':
    array = [5, 7, 3, 7, 2, 3, 2, 5, 9, 5, 7, 6]
    print(counting_sort(array))

运行结果：

[2, 2, 3, 3, 5, 5, 5, 6, 7, 7, 7, 9]

代码中，使用Python内置函数max()求出待排序列表中的最大值。然后根据上面分析的排序原理，进行计数，再将数据添加到新列表中。i 表示计数列表的索引，也表示待排序列表中值为 i 的元素，j 表示值为 i 的元素有 j 个。

四、计数排序的时间复杂度和稳定性

1. 时间复杂度

在计数排序中，需要走访待排序列表中的每一个元素，进行计数，列表长度为 n ，然后需要遍历计数列表，添加数据到新列表中，计数列表长度为 k+1 ，时间复杂度为 T(n)=n+k+1，再乘计数和添加数据的步骤数(常数，不影响大O记法)，所以计数排序的时间复杂度为 O(n+k) 。

2. 稳定性

根据计数排序的应用场景，待排序列表中有很多值相等的元素。不过，计数排序没有比较待排序列表中的数据大小，也没有进行位置交换，相等数据的相对次序是保持不变的。所以计数排序是一种稳定的排序算法。

 

 

本文地址：https://blog.csdn.net/weixin_43790276/article/details/107398262