Python 计数排序
原理
当输入的元素是n个0到k之间的整数时,它的运行时间是Θ(n+k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。
由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。例如:计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名。但是,计数排序可以用在基数排序算法中,能够更有效的排序数据范围很大的数组。
步骤
找出待排序的数组中最大和最小的元素
统计数组中每个值为i的元素出现的次数,存入数组C的第i项
对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)
反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1
代码
defcount_sort(list):
min=2147483647
max=0
#取得最大值和最小值
forxinlist:
ifx min=x ifx>max: max=x #创建数组C count=[0]*(max-min+1) forindexinlist: count[index-min]+=1 index=0 #填值 forainrange(max-min+1): forcinrange(count[a]): list[index]=a+min index+=1 returnlist 以上内容为大家介绍了Python计数排序,希望对大家有所帮助,如果想要了解更多Python相关知识,请关注IT培训机构:千锋教育。

猜你喜欢LIKE
相关推荐HOT
更多>>
python函数中使用for循环
python函数中使用for循环1、在for循环中使用函数需要更长的执行时间,因为每次迭代都会调用该函数。2、如果for循环是在函数内部实现的,那么该...详情>>
2023-11-14 13:53:34
python3.1版本的特性有哪些
python3.1中的特性有哪些1、千位数格式化,可以在使用字符串格式化函数时直接完成。在格式化大数时,通常是每三位数放置逗号,使数字更易读(例...详情>>
2023-11-14 13:18:27
python__new__()和__init__()有什么区别?
在python中,__new__()不是一定要有,只有继承自object的类才有,该方法可以return父类(通过super(当前类名,cls).__new__())出来的实例,或者直...详情>>
2023-11-14 12:38:55
pythonwheel是什么
python的第一个主流打包格式是.egg文件,现在大家庭中又有了一个叫做Wheel(*.whl)的新成员。wheel“被设计成包含PEP376兼容安装(一种非常接近于...详情>>
2023-11-14 11:30:39热门推荐
技术干货






