百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 编程网 > 正文

走进开发,5分钟熟悉快速排序和计数排序

yuyutoo 2024-10-12 01:07 6 浏览 0 评论

本文通过动态可视化图来解析快速排序法和计数排序法。

这几天“手机壳颜色换主题色”需求引起一波轰动,关于事情真伪这里不做判断。但技术仍然是实施手段,产品最终还是要靠技术来实现,产品还是不能远离技术。多理解一点技术知识,和开发大佬说话就多了一份硬气。连基础的排序算法都不懂的产品经理很难的得到开发及项目组的青睐。

那么你花5分钟阅读,再花5分钟理解。以后就可以在公司走路带风,抬头挺胸。

关于“冒泡排序、插入及选择排序”可以看之前一篇文章:走进开发,5分钟熟悉3种经典排序算法

一、快速排序法

快速排序是冒泡排序的改进版,整个过程就在拆拆补补,东拆西补或西拆东补,一边拆一边补,直到所有元素达到有序状态。

1. 快速排序法基本思路

  • 先从数列中取出一个数作为基准数,然后进行大小分区;
  • 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边;
  • 再对左右区间重复第二步,直到各区间只有一个数,排序完成。

下面先通过图文形式一步一步进行拆解。

拿[4,1,6,2,9,3]这个数组举例。

第一遍遍历:

  • 先进行拆分 [4,1,6,2,9,3] 选择元素 4 作为轴心点
  • 检查是否 1 < 4 (轴心点)
  • 检查是否 6 < 4 (轴心点)
  • 检查是否 2 < 4 (轴心点)
  • 2 < 4 (轴心点) 是为真,将指数2和 存储指数 6 进行交换
  • 检查是否 9 < 4 (轴心点)
  • 检查是否 3 < 4 (轴心点)
  • 3 < 4 (轴心点) 为真,将指数3和存储指数6 进行交换
  • 将轴心点4和存储指数3进行交换
  • 此时轴心点4左边全部小于4,右边大于4

目前数组顺序为[3,1,2,4,9,6]。

下一步:

  • 先将左边先排好序
  • 选择元素 3 作为轴心点
  • 检查是否 1 < 3 (轴心点)
  • 检查是否 2 < 3 (轴心点)
  • 将轴心点 3和存储指数值 2进行交换
  • 现在轴心点已经在排序过后的位置
  • 进行拆分 [2,1] 选择 2 作为轴心点
  • 检查是否 1 < 2 (轴心点)
  • 左边遍历完成,将轴心点2和存储指数1 进行交换

右边同理……避免视觉疲劳就不一一描述了,可看下面动态演示图。

2. 快速排序法全流程

3. 快速排序法总结

  • 默认取第一个元素为轴心点(轴心点的确认区分了 “快速排序法”和“随机排序法”)两种算法,而随机排序则随机rand一个元素为轴心点;
  • 如果两个不相邻元素交换,可以一次交换消除多个逆序,加快排序进程。

二、计数排序法

计数排序,顾名思义,就是把要排序的元素都一一计数,某个数值如果总共有5个相同的,该元素对应的个数就记为5;总共有10个相同的,就记为10。

1. 计数排序法基本思路

  • 创建计数器;
  • 遍历数组中的每个元素在相应的计数器增加1;
  • 将计数器储存好的元素从小到大重新收集;
  • 重新将计数器元素重新存储于原数组。

下面通过图文形式一步一步进行案例拆解。

拿[8,6,4,1,6,2,9,6,2,4,3]这个数组举例。

  • 创建计数器1-9从小到大依次排列,然后遍历数组里每一个元素对应丢到相应计数器
  • 将8存到计数器8 此时计数器8有1个元素
  • 将6存到计数器6 此时计数器6有1个元素
  • 将4存到计数器4 此时计数器4有1个元素
  • 将1存到计数器1 此时计数器1有1个元素
  • 将6存到计数器6 此时计数器6有2个元素
  • 将2存到计数器2 此时计数器2有1个元素
  • 将9存到计数器9 此时计数器9有1个元素
  • 将6存到计数器6 此时计数器6有3个元素
  • 将2存到计数器2 …..
  • 将4存到计数器4 ……
  • 将3存到计数器3 ……

第二步:

  • 将计数器里面的数组从小到大依次储存于新数组列表
  • 计数器1 有1个元素 重新放入新列表[1]
  • 计数器2 有2个元素 重新放入新列表[1,2,2]
  • 计数器3 有1个元素 重新放入新列表[1,2,2,3]
  • 计数器4 有2个元素 重新放入新列表[1,2,2,3,4,4]
  • 计数器6 有3个元素 重新放入新列表[1,2,2,3,4,4,6,6,6]
  • 计数器8 有1个元素 重新放入新列表[1,2,2,3,4,4,6,6,6,8]
  • 计数器9 有1个元素 重新放入新列表[1,2,2,3,4,4,6,6,6,8,9]

2. 计数排序全流程

3. 计数排序总结

  • 排序不需要进行比较
  • 在当待排序数组内有大量重复的数值并且这些数值较为集中时,使用计数排序有明显的优势

除了以上两种排序算法,还有许多不同的排序算法,每个都有其自身的优点和使用场景,当然也有局限性。可以多看几遍全流程动态图弄清来龙去脉,理解性地记忆,希望对你有用。

本文由 @动物园园长 原创发布于人人都是产品经理。未经许可,禁止转载

题图来自 Pexels ,基于 CC0 协议

相关推荐

国产RISC-V终端Sipeed Lichee Console4A上架,1699元起

IT之家12月11日消息,国内著名开源硬件厂商Sipeed矽速科技推出RISC-V终端LicheeConsole4A,售价1699元(不带LM4A模块)-3299元。Li...

H3C交换机常用配置命令

1、配置主机名...

ThinkPad老版Bios中英文对应详解

ThinkPad老版Bios中文对应详解。解决方案:...

澳大利亚Console Connect与非洲数据中心达成战略合作,增强整个非洲的数据连接

据techafricanews网11月13日报道,在2024年非洲科技节上,澳大利亚ConsoleConnect与非洲数据中心共同宣布了一项具有里程碑意义的战略合作协议,该协议致力于提升非洲大陆关键...

多功能调焦 腾龙TAP-in Console延期发售

最新消息传出,腾龙TAP-inConsole(modeltap-01)多功能调焦器由于生产方面原因原本预计3月24日发售延迟至3月30日,腾龙的这款调焦器功能类似于适马的USBDock调焦底座,...

关于交换机上存在的不同接口介绍(一)

生活中常见的电子设备有很多,其中明交换机主要起到的是连接的作用,上面有非常多的接口,下面就一起来看看这些不同的接口作用是什么。1、RJ-45接口这是我们见的最多、应用最广的一种接口类型,它属于双绞线以...

颜值更高?微软新推精英版Xbox One手柄

本月,微软的XboxOne升级了更强大的版本——XboxOneEliteconsole(精英版?),升级版的控制手柄功能更强大,可以主导你的客厅;从曝光的图片上看得出,新版XboxOneE...

“全球首个”:Console Connect为全球物联网项目推出连接解决方案

据DevelopingTelecoms2月27日报道,在MWC2023上,全球网络即服务(NaaS)平台ConsoleConnect推出了“全球首个”私有连接解决方案,可帮助企业在全球范围内动态...

密码遗忘专题——Console口密码遗忘

如果忘记了Console口密码,用户可以通过以下两种方式来设置新的Console口密码:方法一:通过STelnet/Telnet登录设备修改Console口密码。...

为锐捷路由器交换机开启web和telnet,实现轻松管理

笔者上一篇文章写了关于锐捷二层交换机配置教程,那么接下来讲一下锐捷的路由交换设备配置web、telnet技巧。同样,今天的教程也是基于命令行,比较简单,适合新手小白进行学习。准备工作配置前准备:con...

C# - 类文件构成,C#基本语法,Console属性与方法 007

类文件(.cs)构成类文件主要分为引用命名空间与自己项目的命名空间...

Console OS系统帮你在PC上自由切换Windows和安卓应用

通过ConsoleOS你可以在你的PC上安装自己喜欢的安卓游戏,需要时之间切换回Windows进行其他工作,ConsoleOS能够完全利用你的PC硬件配置,该系统可以安装在PC的内置硬盘里,也可以...

交换机通过串口线console口登录设备

一、功能简介:PC端通过设备的Console口登录,实现对第一次上电的设备进行基本配置和管理。...

(每日持续更新)jdk api之Console基础、应用、实战

博主18年的互联网软件开发经验,从一名程序员小白逐步成为了一名架构师,我想通过平台将经验分享给大家,因此博主每天会在各个大牛网站点赞量超高的博客等寻找该技术栈的资料结合自己的经验,晚上进行用心精简、整...

KFC推出“真正的次世代主机”KFConsole!真4K/120帧

今天KFCGaming官方推特发布了一则“主机”宣传片,正式公布了旗下名为KFConsole的全新主机产品。并宣称:游戏的未来就在这里,介绍真正的次世代主机!根据官方介绍,本款KFC主机功能强大,支...

取消回复欢迎 发表评论: