python实现·十大排序算法之计数排序(Counting Sort)

发布于: 2020 年 05 月 28 日
python实现·十大排序算法之计数排序(Counting Sort)

简介

计数排序(Counting Sort)不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。它的基本思想是:给定的输入序列中的每一个元素x,确定该序列中值小于等于x元素的个数,然后将x直接存放到最终的排序序列的正确位置上。

算法实现步骤

  1. 根据待排序集合中最大元素和最小元素的差值范围,申请额外空间;

  2. 遍历待排序集合,将每一个元素出现的次数记录到元素值对应的额外空间内;

  3. 对额外空间内数据进行计算,得出每一个元素的正确位置;

  4. 将待排序集合每一个元素移动到计算得出的正确位置上。

Python 代码实现

# counting_sort 代码实现
from typing import List
def counting_sort(arr:List[int]):
max=min=0
for i in arr:
if i < min:
min = i
if i > max:
max = i
count = [0] * (max - min +1)
for j in range(max-min+1):
count[j]=0
for index in arr:
count[index-min]+=1
index=0
for a in range(max-min+1):
for c in range(count[a]):
arr[index]=a+min
index+=1

# 测试数据
if __name__ == '__main__':
import random
random.seed(54)
arr = [random.randint(0,100) for _ in range(10)]
print("原始数据:", arr)
counting_sort(arr)
print("计数排序结果", arr)

# 输出结果
原始数据: [17, 56, 71, 38, 61, 62, 48, 28, 57, 42]
计数排序结果 [17, 28, 38, 42, 48, 56, 57, 61, 62, 71]

动画演示

算法分析

  • 时间复杂度

数据取值范围是常数 k,待排序元素个数是 n,总的时间复杂度是

  • 空间复杂度

计数排序只需要额外的空间复杂度为,所以计数排序的空间复杂度为

  • 稳定性

计数排序不会改变相等元素的相对位置,所以计数排序是稳定的。

  • 综合评价

联系我们

个人博客网站:http://www.bling2.cn/

Github地址:https://github.com/lb971216008/Use-Python-to-Achieve

知乎专栏:https://zhuanlan.zhihu.com/Use-Python-to-Achieve

小专栏:https://xiaozhuanlan.com/Use-Python-to-Achieve

博客园:https://www.cnblogs.com/Use-Python-to-Achieve

发布于: 2020 年 05 月 28 日 阅读数: 3
用户头像

南风以南

关注

南风以南 2018.11.12 加入

石油开发系研究生

评论

发布
暂无评论
python实现·十大排序算法之计数排序(Counting Sort)