拜托,面试别再问我基数排序了!!!
排序,面试中考察基本功问的比较多,工作多年以后,对排序的细节记忆不那么清楚的小伙伴,面试时会比较吃亏。
有一种很神奇的排序,基数排序(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);
希望这一分钟,大家有收获。
原文发布时间为:2018-10-10
本文作者:58沈剑
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
收藏起来,史上最全的 MySQL 高性能优化实战总结!
一、前言 MySQL 对于很多 Linux 从业者而言,是一个非常棘手的问题,多数情况都是因为对数据库出现问题的情况和处理思路不清晰。在进行 MySQL 的优化之前必须要了解的就是 MySQL 的查询过程,很多的查询优化工作实际上就是遵循一些原则让MySQL 的优化器能够按照预想的合理方式运行而已。 今天给大家体验 MySQL 的优化实战,助你高薪之路顺畅! 图 - MySQL查询过程 二、优化的哲学 注意:优化有风险,涉足需谨慎! 1. 优化可能带来的问题 ● 优化不总是对一个单纯的环境进行,还很可能是一个复杂的已投产的系统。 ● 优化手段本来就有很大的风险,只不过你没能力意识到和预见到! ● 任何的技术可以解决一个问题,但必然存在带来一个问题的风险! ● 对于优化来说解决问题而带来的问题,控制在可接受的范围内才是有成果。 ● 保持现状或出现更差的情况都是失败! 2. 优化的需求 ● 稳定性和业务可持续性,通常比性能更重要! ● 优化不可避免涉及到变更,变更就有风险! ● 优化使性能变好,维持和变差是等概率事件! ● 切记优化,应该是各部门协同,共同参与的工作,任何单一部门都不能对数...
- 下一篇
Java后端技术栈,到底如何深入学习?
Java,是现阶段中国互联网公司中,覆盖度最广的研发语言。有不少朋友问,如何深入学习Java后端技术栈,今天分享一个,互联网牛人整理出来的Java深入学习路线图,以及免费学习资料。 一、阅读源码 深入的Java学习,经典源码阅读不可少: ● 常见的 设计模式 ,编码必备 ● Spring5 ,做应用必不可少的最新框架 ● MyBatis ,玩数据库必不可少的组件 画外音:大家扪心自问,除了写业务代码,看过多少优秀开源代码? 二、分布式架构 随着业务越来越复杂,数据量越来越大,并发量越来越大,单体的架构模式显然再也无法对应,作为Java后端架构师,高并发+高可用+海量数据的分布式架构体系,是必不可少的: ● 分布式 架构原理 ● 分布式 架构策略 ● 分布式 中间件 ● 分布式架构 实战 画外音:额, 这些分布式理论,是不是感觉零零星星的听过,而没有系统的学习过? 三、微服务技术体系 服务分层,微服务架构是架构升级的必由之路,Java技术体系,和微服务相关的技术有哪需要深入学习呢? ● 微服务框架 ● Spring Cloud ● Docker与虚拟化 ● 微服务架构 画外音:明明知道S...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,CentOS8安装Elasticsearch6.8.6
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- Linux系统CentOS6、CentOS7手动修改IP地址
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- SpringBoot2全家桶,快速入门学习开发网站教程