原创投稿
  1. 趣知天下事首页
  2. 科技
  3. 技术

虽然小象被淘汰了，但我学会了这种O(n)的排序算法

糖太宗 • • 技术 • 阅读 22
时间复杂度为O(n)的排序，除了昨天介绍的基数排序(Radix Sort)，还有计数排序(Counting Sort)。
 
计数排序的适用范围？
待排序的元素在某一个范围[MIN, MAX]之间。
画外音：很多业务场景是符合这一场景，例如uint32的数字排序位于[0, 2^32]之间。
 
计数排序的空间复杂度？
计数排序需要一个辅助空间，空间大小为O(MAX-MIN)，用来存储所有元素出现次数（“计数”）。
画外音：计数排序的核心是，空间换时间。
 
计数排序的关键步骤？
步骤一：扫描待排序数据arr[N]，使用计数数组counting[MAX-MIN]，对每一个arr[N]中出现的元素进行计数；
步骤二：扫描计数数组counting[]，还原arr[N]，排序结束；
 
举个栗子：
假设待排序的数组，
arr={5, 3, 7, 1, 8, 2, 9, 4, 7, 2, 6, 6, 2, 6, 6}
很容易发现，待排序的元素在[0, 10]之间，可以用counting[0,10]来存储计数。
 
第一步：统计计数
虽然小象被淘汰了，但我学会了这种O(n)的排序算法
扫描未排序的数组arr[N]，对每一个出现的元素进行计数。
 
扫描完毕后，计数数组counting[0, 10]会变成上图中的样子，如粉色示意，6这个元素在arr[N]中出现了4次，在counting[0, 10]中，下标为6的位置计数是4。
 
第二步：还原数组
虽然小象被淘汰了，但我学会了这种O(n)的排序算法
扫描计数数组counting[0, 10]，通过每个元素的计数，还原arr[N]。
 
如上图粉色示意，count[0, 10]下标为6的位置计数是4，排完序是4个连续的6。
从counting下标MIN到MAX，逐个还原，填满arr[N]时，排序结束。
 
神奇不神奇！！！
 
计数排序(Counting Sort)，总结：
（1）计数排序，时间复杂度为O(n)；
（2）当待排序元素个数很多，但值域范围很窄时，计数排序是很节省空间的；
 
希望这一分钟，大家有收获。
架构师之路-分享可落地的技术文章
 
相关文章：
《基数排序，一个O(n)的排序算法》
 
作业题：
还有哪些时间复杂度为O(n)的排序算法呢？

发布者：糖太宗，转载请注明出处：https://www.qztxs.com/archives/science/technology/6006

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
糖太宗糖太宗
0 0
上一篇 2022年5月11日 下午8:10
下一篇 2022年5月11日 下午8:12

相关推荐

  • 开源蜜罐HFish使用心得4 - 溯源2 fingerprintjs 技术

    开源蜜罐HFish使用心得4 - 溯源2 fingerprintjs

    FingerprintJS FingerprintJS 是一个浏览器指纹库，可查询浏览器属性并从中计算出散列的访问者标识符。与 cookie 和本地存储不同，指纹在隐身/隐私模式下保持不变，即使浏览器数据被清除。   项目地址：https://github.com/fingerprintjs/fingerprintjs 简单使用 通过调用该库，会返...

    糖太宗 糖太宗
    2022年5月27日
    11300

  • mongodb开启认证

    修改配置文件，开启认证 1 2 3 4 # vi /etc/mongod.conf security: authorization:enablesd   创建密码 db.createUser({ user: “w11scan”, pwd: “w11scan”, roles: [{ role: “dbOwner”, db: “w11scan_conf...

    常山赵子龙 常山赵子龙
    技术 2022年5月28日
    3900

  • 99%的人会答错，你敢不敢挑战一下？

    用户产品讲直觉，商业产品更讲逻辑。 设计师讲直觉，工程师更讲逻辑。 打德州，一部分同学讲究“就赌最后一张了”让人血脉喷张，一部分同学“没把牌计算概率”让人崩溃。 这样一些有意思的问题，凭直觉99%会答错。 问题一 一枚硬币，随机投掷一次，是正面和反面的概率各为50%。 随机投掷两次，有四种可能，正正，反反，正反，反正，概率各为25%。   现在，投掷第一次，...

    糖太宗 糖太宗
    技术 2022年5月11日
    3100
  • 如何在12个小时，搞定日志监控？ 技术

    如何在12个小时，搞定日志监控？

    日志监控，是每个公司必须解决的一个问题。创业型公司，如何用半天的时间，搞定一个可扩展，通用的日志监控框架，是今天要聊的话题。   什么是日志监控？ 关于日志，不同公司，情况不同： （1）A类公司：没有日志； （2）B类公司：有日志，只有用户说系统挂了，或者有bug的时候，才会登录到系统看看日志，大部分日志打印得对心所欲，缺乏组织性和系统性； 画外音：很多时候...

    糖太宗 糖太宗
    2022年5月15日
    1800
  • 为什么MySQL要升级组复制？1分钟系列 技术

    为什么MySQL要升级组复制？1分钟系列

    前几天发了《Galera，MySQL主从之外的另一种选择》之后，很多朋友在评论里留言： “这不就是Oracle Rac吗？” “这不就是MGR吗？” …   思路比结论重要，为什么比是什么重要，今天就花1分钟，说下这里面架构演进的思路。 画外音：大家不想听底层细节，就不深入细节了。   最早的数据库都是单机的，其最大的痛点是啥？ 无法线性扩展。   磁盘能力...

    糖太宗 糖太宗
    2022年5月11日
    1700

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

联系我们

400-800-8888

在线咨询： QQ交谈

邮件：admin@example.com

工作时间：周一至周五，9:30-18:30，节假日休息

关注微信