个人技术博客地址：http://songmingyao.com/
原理
- 找出列表中最大和最小的元素
- 构建新列表，元素全为零，长度为最大值与最小值之间的差值加一
- 统计待排序列表中每个值i出现的次数，并将新列表中下标为i-min的值加一
- 将新列表中非零值的下标反转回原有元素i（即加上最小值），构建有序列表
源码
def count_sort(l):
max = 0
min = 1024
for item in l:
if item > max:
max = item
elif item < min:
min = item
count = [0]*(max-min+1)
for index in l:
count[index-min] += 1
index = 0
for i in range(max-min+1):
for j in range(count[i]):
l[index] = i+min
index += 1
if __name__ == '__main__':
l = [6, 5, 2, 8, 9, 4, 1, 0, 3, 7]
print(l)
count_sort(l)
print(l)
时间复杂度
- 最优时间复杂度：O(n+k)
- 最坏时间复杂度：O(n+k)
- 稳定性（多个元素等值的情况下是否会破坏原有顺序）：稳定
