python实现基本算法之计数排序(Counting Sort)

时间:2020-9-6 作者:admin


基本算法之计数排序(Counting Sort)

基本算法—05、计数排序(Counting Sort)算法
其他的基本算法也已经发布,可以一并收藏学习


文章目录


0、前言

评判一个算法的好坏的标准:

  • 时间复杂度
  • 空间复杂度

1、计数排序是什么?

计数排序要求输入数据的范围在 [0,N-1] 之间,则可以开辟一个大小为 N 的数组空间,将输入的数据值转化为键存储在该数组空间中,数组中的元素为该元素出现的个数。

  • 计数排序不是基于比较的排序算法
  • 核心是在于将输入的数值转化为键存储在额外开辟的数值空间里面
  • 线性时间复杂度的排序算法
  • 要求是数据必须是有确定空间的整数

原理:

1.找到元素中的最大值m,然后构建一个m大的数组L
2.统计数组中每个值为 i 元素出现的次数,记录在数组 L 中的第 i
3.遍历数组L,遇到值不是0的就输出坐标值,具体输出几次看这一个位置上的数值是几
4.将输出的数值,依次的写入到我们输入的数值中,每输出一次,索引加一

开辟一个非常大的空间,是根据数组的最大值决定的。所以如果数组中的最大值特别大的话,效率就不会很高!

2、算法过程图解

python实现基本算法之计数排序(Counting Sort)

3、代码实现

代码如下:

"""
Counting Sort计数排序
时间复杂度:O(n+k)
"""

def countingSort(nums):
	# 桶的个数,这一是取决于,这一个列表中最大的那个数字
    bucket = [0] * (max(nums) + 1) 

    for num in nums:  # 用num下标的位置,记录其出现的次数
        bucket[num] += 1
    i = 0  # nums 的索引
    # 循环遍历整个桶
    for j in range(len(bucket)):
        # 找到第j个元素,就是出现j的次数,如果不是0次没代表出现
        while bucket[j] > 0:
            # 出现了,就把这一个写入到原本的nums列表中,
            # 同时出现的次数减一,nums列表加一
            nums[i] = j
            bucket[j] -= 1
            i += 1
    return nums

if __name__ == '__main__':
    alist = [54, 26, 93, 17, 93, 17, 77, 77,54, 26, 4, 2, 6,93, 17, 77, 31, 44, 55, 20, 31, 44, 55, 20]
    print(f'计数排序(Counting Sort)之前原列表的顺序:{alist}')
    alist = countingSort(alist)
    print(f'计数排序(Counting Sort)之后的列表的顺序:{alist}')
    print(f'计数排序(Counting Sort)之后的正确的顺序:[2, 4, 6, 17, 17, 17, 20, 20, 26, 26, 31, 31, 44, 44, 54, 54, 55, 55, 77, 77, 77, 93, 93, 93]')



4、评判算法

  • 最好时间复杂度:O(n+k)
  • 最坏时间复杂度:O(n+k)
  • 平均时间复杂度:O(n+k)
  • 空间复杂度:O(k)
  • 算法稳定性:稳定的排序
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。