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

这个排序这么酷，为什么知道的人很少？

糖太宗 • • 技术 • 阅读 16
有一种很神奇的排序，基数排序(Radix Sort)，时间复杂度为O(n)，今天花1分钟，通过几幅图，争取让大家搞懂细节。
画外音：居然还有时间复杂度为O(n)的排序算法？不但有，其实还有很多。
 
举个栗子：
假设待排序的数组arr={72, 11, 82, 32, 44, 13, 17, 95, 54, 28, 79, 56}
这个排序这么酷，为什么知道的人很少？
基数排序的两个关键要点：
（1）基：被排序的元素的“个位”“十位”“百位”，暂且叫“基”，栗子中“基”的个数是2（个位和十位）；
画外音：来自野史，大神可帮忙修正。
（2）桶：“基”的每一位，都有一个取值范围，栗子中“基”的取值范围是0-9共10种，所以需要10个桶（bucket），来存放被排序的元素；
 
基数排序的算法步骤为：

FOR (每一个基) {

//循环内，以某一个“基”为依据

第一步：遍历数据集arr，将元素放入对应的桶bucket

第二步：遍历桶bucket，将元素放回数据集arr

}

 
更具体的，对应到上面的栗子，“基”有个位和十位，所以，FOR循环会执行两次。
 
第一次：以“个位”为依据。
这个排序这么酷，为什么知道的人很少？
画外音：上图中标红的部分，个位为“基”。
第一步：遍历数据集arr，将元素放入对应的桶bucket；
 
这个排序这么酷，为什么知道的人很少？
操作完成之后，各个桶会变成上面这个样子，即：个位数相同的元素，会在同一个桶里。
 
第二步：遍历桶bucket，将元素放回数据集arr；
画外音：需要注意，先入桶的元素要先出桶。
这个排序这么酷，为什么知道的人很少？
操作完成之后，数据集会变成上面这个样子，即：整体按照个位数排序了。
画外音：个位数小的在前面，个位数大的在后面。
 
第二次：以“十位”为依据。
这个排序这么酷，为什么知道的人很少？
画外音：上图中标红的部分，十位为“基”。
第一步：依然遍历数据集arr，将元素放入对应的桶bucket；
这个排序这么酷，为什么知道的人很少？
操作完成之后，各个桶会变成上面这个样子，即：十位数相同的元素，会在同一个桶里。
 
第二步：依然遍历桶bucket，将元素放回数据集arr；
这个排序这么酷，为什么知道的人很少？
操作完成之后，数据集会变成上面这个样子，即：整体按照十位数也排序了。
画外音：十位数小的在前面，十位数大的在后面。
 
首次按照个位从小到大，第二次按照十位从小到大，即：排序结束。
 
神奇不神奇！！！
 
几个小点：
（1）基的选取，可以先从个位开始，也可以先从十位开始，结果是一样的；
（2）基数排序，是一种稳定的排序；
（3）时间复杂度，可以认为是线性的O(n)；
 
希望这一分钟，大家有收获。
架构师之路-分享可落地的技术文章
 
推荐阅读：
《世界上最漂亮的排序算法！》
《一次搞透，面试中的TopK问题！》
 
调研：
你知道哪些排序算法，时间复杂度是O(n)吗？

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

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

相关推荐

  • 7000字+24张图带你彻底弄懂线程池 技术

    7000字+24张图带你彻底弄懂线程池

    大家好。今天跟大家聊一聊无论是在工作中常用还是在面试中常问的线程池，通过画图的方式来彻底弄懂线程池的工作原理，以及在实际项目中该如何自定义适合业务的线程池。 一、什么是线程池 线程池其实是一种池化的技术的实现，池化技术的核心思想其实就是实现资源的一个复用，避免资源的重复创建和销毁带来的性能开销。在线程池中，线程池可以管理一堆线程，让线程执行完任务之后不会进行...

    糖太宗 糖太宗
    2023年1月26日
    1200
  • 关于MySQL，这篇都没人赞，太没天理了！ 技术

    关于MySQL，这篇都没人赞，太没天理了！

    这是一篇关于MySQL数据库，redo log，LSN，崩溃恢复，在线热备的长文，耐心读完，如果没有收获，可以捶我。   研发的童鞋每次对MySQL库表做重大操作之前，例如： （1）修改表结构； （2）批量修改或者删除数据； 都会向DBA申请进行数据库的备份。 画外音：又或者说，不备份直接操作啦？   那DBA童鞋是怎么进行MySQL备份的呢？  ...

    糖太宗 糖太宗
    2022年5月11日
    1900
  • 洞态IAST落地实践 技术

    洞态IAST落地实践

    IAST作为开展sdl中黑白盒测试的有效补充，还是很有必要去了解使用的。笔者为了完善公司的SDL流程，调研了开源的IAST产品进行测试和内部推广   刚开始，笔者测试百度OpenRASP的IAST功能（主动式IAST），OpenRASP的IAST通过对agent采集到的流量数据进行重放，根据hook点信息做选择性的扫描；与主动式漏扫相比，这种方式减...

    常山赵子龙 常山赵子龙
    2022年6月13日
    16200

  • 甲方安全建设的一些思路和思考

      0x00 前言 本文主要是介绍一下笔者对于甲方安全能力建设的一些经验，心得和零散的思考。需要特别强调的是不同企业的实际情况不尽相同，本文仅供参考，不具普遍意义。   0x01 Red Teaming 近几年随着Red Team建设的话题越来越流行，不管是甲方或者乙方都在极力的发展自己的Red Teaming能力，尤其是各个乙方都推出了...

    常山赵子龙 常山赵子龙
    技术 2022年5月28日
    2100
  • 老板问我，什么是关联规则推荐？ 技术

    老板问我，什么是关联规则推荐？

    工程架构方向的程序员，看到推荐/搜索/广告等和算法相关的技术，心中或多或少有一丝胆怯。但认真研究之后，发现其实没有这么难。 今天给大家介绍下推荐系统中的“关联规则推荐”，保证大伙弄懂。 画外音：可以看excel截图，或者看公式，大伙结合自己能够理解的程度自取。   一、概念 什么是关联规则（Association Rules）？ 答：关联规则是数据挖掘中的概...

    糖太宗 糖太宗
    2022年5月10日
    6200

发表回复

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

联系我们

400-800-8888

在线咨询： QQ交谈

邮件：admin@example.com

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

关注微信