不为成仙,只为在这红尘中等你回来。

您现在的位置是:网站首页>>算法与数据结构

计数排序

2020年11月6日 22:50 | 分类:算法与数据结构 | 标签: Python

  • 对列表进行排序,已知列表中的数范围都在 0 到 100 之间。设计时间复杂度为 O(n) 的算法。

计数排序

def count_sort(lst, max_count=100):
    count = [0 for _ in range(max_count+1)] # 生成一个包含 max_count 个零的列表
    for val in lst:
        count[val] += 1
    lst.clear() # 清空原列表
    for ind, val in enumerate(count):
        for i in range(val):
            lst.append(ind)


import random

lst = [random.randint(0, 100) for _ in range(1000)]
print(lst)
count_sort(lst)
print(lst)