本文共 612 字，大约阅读时间需要 2 分钟。

做笔试题看到有一个排序算法的时间复杂度要求为O(N)，当时懵了没想到，后来想到有一个叫计数排序的排序算法貌似可以达到要求

• 记录一下实现的过程（计数排序）

def bucket_sort(array):    maxnum = max(array)    bucket = [0] * (maxnum + 1)    for i in array:        bucket[i] += 1        newarray = []    for j in range(len(bucket)):        if bucket[j] != 0:            for _ in range(bucket[j]):                newarray.append(j)    return newarrayarray = [5,6,3,2,1,65,2,0,8,0]print(bucket_sort(array))

实现的流程大概如下：

• 由于计数排序是根据下标以及下标所处位置的值来返回最后结果，所以速度比快排还要快。
• 所以首先要根据所给数组中最大元素的数值来创建“槽”的长度
• 然后遍历之前的数组，数组中有几就在“槽”的第几位上+1 （如果有两个0，那么桶中的第0个元素就要+2）
• 取出元素，循环遍历“槽”，输出“槽”下标位置元素的值（次数）的下标值（假如array[0]的值是3，那么输出三次0）

转载地址：http://qheyz.baihongyu.com/