Python3 数据结构与算法之计数排序

简介: Python3 数据结构与算法之计数排序

本文讲述一个在编程过程中并不是很常见的一种排序算法——计数排序。


计数排序

根据这个排序的名字,我们不难想到该排序的主体就在于计数二字上,那么具体有什么数字需要我们记录呢,下面通过一个例子来简单的说明一下。

这里给定一个数组:

arr = [2, 3, 5, 14, 5, 7, 22, 7, 7, 11]

我们能看到一个数组中的数字不仅是大小不一的,还有可能是重复的,既然有重复的数据,那么我们就先来讲这些重复的数据找出来并做一定的标记。


我们既想要记录每个数字是多少又想要记录出现的次数,你可能会想到二维数组、字典等等的数据结构,我在这里给出一个很简单的思想用一个一维数组解决这个问题,首先我们定义一个长度为max(arr)-min(arr)+1的数组countArr,有个这个较长的数组后,我们就可以用索引来表示数字的值用数组的空间去存储该值出现的次数,来用代码实现以下这个操作:

    maxnum = max(arr)
    minnum = min(arr)
    countArr_length = maxnum - minnum + 1
    countArr = [0 for i in range(countArr_length)]
    # 统计每个数字出现的次数,存在计数数组中。
    for i in arr:
        countArr[i - minnum] += 1

每一次循环的结果如下:

12.png

有了这个数组,我们只需要将每个数在一个新的数组中填入到他们相应的位置并输出即可,全部代码如下:

def count_sort(arr):
    maxnum = max(arr)
    minnum = min(arr)
    countArr_length = maxnum - minnum + 1
    countArr = [0 for i in range(countArr_length)]
    res = [0 for i in range(len(arr))]
    # 统计每个数字出现的次数,存在计数数组中。
    for i in arr:
        countArr[i - minnum] += 1
    # 统计每个数字前面有几个比自己小的数,并更新到计数数组中。
    for j in range(1, countArr_length):
        countArr[j] = countArr[j] + countArr[j - 1]
    # 根据每个数字前面有几位比自己小的数的个数进行输出。
    for k in range(len(arr)):
        res[countArr[arr[k] - minnum] - 1] = arr[k]
        countArr[arr[k] - minnum] -= 1
    return res
arr = [2, 3, 5, 14, 5, 7, 22, 7, 7, 11]
print(count_sort(arr))

排序结果如下:

13.png

说明一下代码中最后一个循环中的内容:


res[countArr[arr[k] - minnum] - 1] = arr[k],该步骤用于寻找数字arr[k]之前有几个比他的数字n,并把数字arr[k]放在n-1的位置上(-1是因为索引需要从0开始)。


countArr[arr[k] - minnum] -= 1,该步骤将上一步中排序好的数字弹出再集训进行循环。


复杂度:

假定原始数列的规模是N,最大值和最小值的差是M,计数排序的时间复杂度是O(N+M),如果不考虑结果数组,只考虑中间数组大小的话,空间复杂度是O(M)。


计数排序的局限性:

1、当数列的最大和最小值差距过大时,并不适用计数排序。

2、当数列元素不是整数,并不适用计数排。

目录
打赏
0
0
0
0
16
分享
相关文章
解锁文件共享软件背后基于 Python 的二叉搜索树算法密码
文件共享软件在数字化时代扮演着连接全球用户、促进知识与数据交流的重要角色。二叉搜索树作为一种高效的数据结构,通过有序存储和快速检索文件,极大提升了文件共享平台的性能。它依据文件名或时间戳等关键属性排序,支持高效插入、删除和查找操作,显著优化用户体验。本文还展示了用Python实现的简单二叉搜索树代码,帮助理解其工作原理,并展望了该算法在分布式计算和机器学习领域的未来应用前景。
深度洞察内网监控电脑:基于Python的流量分析算法
在当今数字化环境中,内网监控电脑作为“守城卫士”,通过流量分析算法确保内网安全、稳定运行。基于Python的流量分析算法,利用`scapy`等工具捕获和解析数据包,提取关键信息,区分正常与异常流量。结合机器学习和可视化技术,进一步提升内网监控的精准性和效率,助力企业防范潜在威胁,保障业务顺畅。本文深入探讨了Python在内网监控中的应用,展示了其实战代码及未来发展方向。
探秘文件共享服务之哈希表助力 Python 算法实现
在数字化时代,文件共享服务不可或缺。哈希表(散列表)通过键值对存储数据,利用哈希函数将键映射到特定位置,极大提升文件上传、下载和搜索效率。例如,在大型文件共享平台中,文件名等信息作为键,物理地址作为值存入哈希表,用户检索时快速定位文件,减少遍历时间。此外,哈希表还用于文件一致性校验,确保传输文件未被篡改。以Python代码示例展示基于哈希表的文件索引实现,模拟文件共享服务的文件索引构建与检索功能。哈希表及其分布式变体如一致性哈希算法,保障文件均匀分布和负载均衡,持续优化文件共享服务性能。
|
17天前
|
公司电脑网络监控场景下 Python 广度优先搜索算法的深度剖析
在数字化办公时代,公司电脑网络监控至关重要。广度优先搜索(BFS)算法在构建网络拓扑、检测安全威胁和优化资源分配方面发挥重要作用。通过Python代码示例展示其应用流程,助力企业提升网络安全与效率。未来,更多创新算法将融入该领域,保障企业数字化发展。
40 10
|
18天前
|
基于 Python 广度优先搜索算法的监控局域网电脑研究
随着局域网规模扩大,企业对高效监控计算机的需求增加。广度优先搜索(BFS)算法凭借其层次化遍历特性,在Python中可用于实现局域网内的计算机设备信息收集、网络连接状态监测及安全漏洞扫描,确保网络安全与稳定运行。通过合理选择数据结构与算法,BFS显著提升了监控效能,助力企业实现智能化的网络管理。
27 7
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
59 12
基于 Python 的布隆过滤器算法在内网行为管理中的应用探究
在复杂多变的网络环境中,内网行为管理至关重要。本文介绍布隆过滤器(Bloom Filter),一种高效的空间节省型概率数据结构,用于判断元素是否存在于集合中。通过多个哈希函数映射到位数组,实现快速访问控制。Python代码示例展示了如何构建和使用布隆过滤器,有效提升企业内网安全性和资源管理效率。
52 9
内网桌面监控软件深度解析:基于 Python 实现的 K-Means 算法研究
内网桌面监控软件通过实时监测员工操作,保障企业信息安全并提升效率。本文深入探讨K-Means聚类算法在该软件中的应用,解析其原理与实现。K-Means通过迭代更新簇中心,将数据划分为K个簇类,适用于行为分析、异常检测、资源优化及安全威胁识别等场景。文中提供了Python代码示例,展示如何实现K-Means算法,并模拟内网监控数据进行聚类分析。
48 10
控制局域网上网软件之 Python 字典树算法解析
控制局域网上网软件在现代网络管理中至关重要,用于控制设备的上网行为和访问权限。本文聚焦于字典树(Trie Tree)算法的应用,详细阐述其原理、优势及实现。通过字典树,软件能高效进行关键词匹配和过滤,提升系统性能。文中还提供了Python代码示例,展示了字典树在网址过滤和关键词屏蔽中的具体应用,为局域网的安全和管理提供有力支持。
63 17
员工电脑监控屏幕场景下 Python 哈希表算法的探索
在数字化办公时代,员工电脑监控屏幕是保障信息安全和提升效率的重要手段。本文探讨哈希表算法在该场景中的应用,通过Python代码例程展示如何使用哈希表存储和查询员工操作记录,并结合数据库实现数据持久化,助力企业打造高效、安全的办公环境。哈希表在快速检索员工信息、优化系统性能方面发挥关键作用,为企业管理提供有力支持。
58 20
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等