Java教程

算法学习笔记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 基数排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!