Python算法——计数排序

举报
Echo_Wish 发表于 2023/11/07 08:57:35 2023/11/07
【摘要】 计数排序(Counting Sort)是一种非比较性排序算法,适用于对一定范围内的整数进行排序。它通过统计每个元素出现的次数,然后根据统计信息重新构建有序数组。计数排序是一种线性时间复杂度的排序算法,具有稳定性和适用性广泛的特点。本文将详细介绍计数排序的工作原理和Python实现。 计数排序的工作原理 计数排序的基本思想是:统计数组中每个元素出现的次数,得到元素的频率统计信息。根据频率统计信...

计数排序(Counting Sort)是一种非比较性排序算法,适用于对一定范围内的整数进行排序。它通过统计每个元素出现的次数,然后根据统计信息重新构建有序数组。计数排序是一种线性时间复杂度的排序算法,具有稳定性和适用性广泛的特点。本文将详细介绍计数排序的工作原理和Python实现。

计数排序的工作原理

计数排序的基本思想是:

  1. 统计数组中每个元素出现的次数,得到元素的频率统计信息。
  2. 根据频率统计信息,重建有序数组。
    计数排序的关键在于如何统计元素的频率以及如何重建有序数组。计数排序适用于整数排序,特别适用于有限范围内的整数排序。
下面是一个示例,演示计数排序的过程:

原始数组:[4, 2, 2, 8, 3, 3, 1]

  1. 统计数组中每个元素出现的次数,得到频率统计信息:{1: 1, 2: 2, 3: 2, 4: 1, 8: 1}。
  2. 根据频率统计信息,重建有序数组:[1, 2, 2, 3, 3, 4, 8]。

Python实现计数排序

下面是Python中的计数排序实现:

def counting_sort(arr):
    max_val = max(arr)
    min_val = min(arr)
    range_val = max_val - min_val + 1

    # 初始化计数数组
    count = [0] * range_val

    # 统计元素频率
    for num in arr:
        count[num - min_val] += 1

    # 重建有序数组
    result = []
    for i in range(range_val):
        result.extend([i + min_val] * count[i])

    return result
  • arr 是待排序的整数数组。
  • max_val 和 min_val 分别是数组的最大值和最小值。
  • range_val 表示元素范围的大小。
  • 初始化计数数组 count,用于统计每个元素出现的次数。
  • 统计元素频率,注意需要将元素减去最小值以适配计数数组。
  • 重建有序数组,根据计数数组信息构建有序数组。

示例代码

下面是一个使用Python进行计数排序的示例代码:

def counting_sort(arr):
    max_val = max(arr)
    min_val = min(arr)
    range_val = max_val - min_val + 1

    count = [0] * range_val

    for num in arr:
        count[num - min_val] += 1

    result = []
    for i in range(range_val):
        result.extend([i + min_val] * count[i])

    return result

# 测试排序
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print("排序后的数组:", sorted_arr)

时间复杂度

计数排序的时间复杂度为 O(n + k),其中 n 是数组的长度,k 是元素范围的大小。计数排序是一种非比较性排序算法,适用于整数排序,特别适用于有限范围内的整数排序。

总之,计数排序是一种高效的非比较性排序算法,通过统计每个元素的频率,重建有序数组,实现了对整数数组的排序。了解计数排序有助于理解非比较性排序算法的思想,并为特定场景提供了一个高效的排序解决方案。

【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。