算法学习笔记4 基数排序

本文主要是介绍算法学习笔记4 基数排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

计数排序

计数排序不是一个比较排序算法，该算法于1954年由 Harold H. Seward提出，通过计数将时间复杂度降到了O(N)。
找出原数组中元素值最大的，记为max。创建一个新数组count，其长度是max加1，其元素默认值都为0。遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。最后将count数组的索引值按个数append到result数组中，即可得到有序数组。

计数排序代码实现：

def count_sort(li, max_count=100):
    count = [0 for _ in range(max_count+1)]		# 生成长度为max_count+1的全0的数组
    for val in li:
        count[val] += 1
    li.clear()
    for ind, val in enumerate(count):	# count数组中有val个ind值
        for i in range(val):	# 将val个ind值添加到result数组中，这里直接覆盖原数组，节省空间
            li.append(ind)

for val in li时间复杂度为O(n)，后面虽然嵌套了两层循环，但是append的元素总个数为原数组的长度n，故时间复杂度也为O(n)。总体时间复杂度为O(n)。

这篇关于算法学习笔记4 基数排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！