Python排序算法8：计数排序（1）

qiuyouzhi

Python排序算法8：计数排序（1）

计数排序的原理

计数排序，是一种不需要比较的算法（还有桶排序，这个后面讲)。

这种排序方法使用下标排序(和访问列表的方式差不多)。

举个例子可能会更清晰一点：

假设有20个随机整数，范围在0~10，要求用最快的速度
将他们排序。
考虑到这些整数只能在0~10这11个数内取值，范围有限，
所以可以建立一个长度为11的列表，用于存放数据。

[0 0 0 0 0 0 0 0 0 0 0 ]

        

0 1 2 3 4 5 6 7 8 9 10

假设20个随机整数是酱紫的：

9, 3, 5, 4, 9, 1, 2, 7, 8, 1, 3, 6, 5, 3, 4, 0, 10, 9, 7, 9

然后下面就开始遍历这个数列：

第一个值，它的值是9，那么就给元素下标为9的元素加1

差不多是这样的：

[0 0 0 0 0 0 0 0 0 1 0 ]

        

0 1 2 3 4 5 6 7 8 9 10

然后以此类推（原谅我太懒），最后就是这个样子：

[1 2 1 3 2 2 1 2 1 4 1]

        

0 1 2 3 4 5 6 7  8 9 10

然后直接遍历数组，输出数组元素的下标值，元素的

值是几，就输出几遍。

zltzlt

又学到了新的排序方法

from random import randint
l1 = [0] * 11
sorted_l = []
lforsort = [randint(0, 10) for _ in range(20)]

for i in lforsort:
    l1[i] += 1

for i in range(len(l1)):
    sorted_l.extend([i] * l1[i])

print(sorted_l)

qiuyouzhi

zltzlt 发表于 2020-3-8 09:30
又学到了新的排序方法

qiuyouzhi

zltzlt 发表于 2020-3-8 09:30
又学到了新的排序方法

话说回来，你这代码写的是真辣眼睛，l和1分不清楚
还是这样好：

def countSort(arr):
    unsortedl = [0 for i in range(len(arr))]
    result = []

    for i in arr:
        unsortedl[i] += 1

    for i in range(len(arr)):
        result.extend([i] * unsortedl[i])
        
    return result