首页 > 新闻中心 > 行业资讯

用5分钟熟悉3种经典排序算法,浅显易懂!

发布时间:2018-08-09      发布者:本站      来源:首席吹牛官(ID:ITman-99)
7394 1

若干年前pony在腾讯产品暨技术峰会上就说过:“我们希望的产品经理是从技术晋升而来的。”技术是实施手段,产品最终还是要靠技术来实现,产品还是不能远离技术。


那么不想通过枯燥的代码来理解几大排序算法,本文通过动态可视化图来解析冒泡排序、选择排序及插入排序。


排序算法最终目的是让无序的数据组合变成有序的数据组合。


一、冒泡法


从字面上能理解, “冒泡”即小值的浮上来,大值沉下去。


1. 冒泡排序法基本思路

第一步比较相邻的元素大小。如果第一个比第二个大,就交换两个元素位置。

之后对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点最后的元素应该会是最大的数。

针对所有的元素重复以上的步骤,除了最后一个。

持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

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

拿[20,10,15,30,12]这个数组举例。

第一遍循环

检查是否 20 > 10;是,交换元素位置;

检查是否 20 > 15;是,交换元素位置;

检查是否 20 > 30;否,位置不做交换;

检查是否 30 > 12;是,交换元素位置;


第一遍循环结束,此时将最后一个没有排序过的元素标记为已排序(即30)。因为在最近的一次扫描过程中至少有一次交换发生过,我们可以进行另一轮扫描。此轮扫描只需要循环判断前面4个元素。


第二遍循环开始

检查是否 10 大于 15;否,位置不做交换;

检查是否 15 大于 20;否,位置不做交换;

检查是否 20 大于 12; 是,交换元素位置;


此时标记 “20”为已排序,那么同理下一轮循环遍历只需循环判断前面3个元素。

……….

避免视觉疲劳,图文只说明前面2轮循环,下面的3轮循环大家自己思考和理解。


2. 冒泡排序法全流程


3. 冒泡法总结

每一轮左右元素两两比较,不进行跨元素比较

每一轮循环比较都会产生当前最大值(当前最大值:这一轮下来的最大值)

每一轮循环后就会少一个元素进行比较(因为每结束一轮就会产生一个当前最大值)


二、选择排序法


选择排序是从冒泡排序演化而来,每一轮比较得出最小的那个值,然后依次和每轮“无序区”中参与比较的第一个值进行交换。


1. 选择排序法基本思路

初始时在序列中找到最小元素

放到序列的起始位置作为已排序序列

然后再从剩余未排序元素中继续寻找最小元素,放到已排序序列的末尾

以此类推,直到所有元素均排序完毕


注意选择排序与冒泡排序的区别:

冒泡排序通过依次交换相邻两个顺序不合法的元素位置,从而将当前最大元素放到合适的位置;而选择排序每循环遍历一次都记住了当前最小元素的位置,最后仅需一次交换操作即可将其放到合适的位置。

下面还是以[20,10,15,30,12]这个数组举例。

第一遍循环

先把最小值设置成为 20 , 然后通过遍历剩下的没有排序过的元素来找到真正的最小值;

检查是否 10 小于现在的最小值 (20)。是,将 10 设为新的最小值;

检查是否 15 小于现在的最小值 (10)。否,10仍然是最小值;

检查是否 30 小于现在的最小值 (10)。否,10仍然是最小值;

检查是否 12 小于现在的最小值 (10)。否,10仍然是最小值。

一轮过后,最小值出现。

交换最小的元素 (10) 和第一个没有排序过的元素 (20)。

现在10是被认定整个数组最小的值。


第二遍循环

把现在的最小值设置成为 20 , 然后通过遍历剩下的没有排序过的元素来找到真正的最小值;

检查是否 15 小于现在的最小值 (20)。是,将 15 设为新的最小值;

检查是否 30 小于现在的最小值 (15)。否,15仍然是最小值;

检查是否 12小于现在的最小值 (15)。是,将 12 设为新的最小值;

交换最小的元素 (12) 和第一个没有排序过的元素 (20);


数组排序顺序更新为 10 12 15 30 20。


避免视觉疲劳,图文只说明前面2轮循环,下面的3轮循环大家自己思考和理解。


2. 选择排序法全流程


3. 选择排序法总结

每一轮进行跨元素比较

每一轮循环比较都会产生当前最小值(当前最小值:这一轮下来的最小值)

每一轮循环比较后就会少一个元素进行比较(因为每结束一轮就会产生一个当前最小值)


三、插入排序法(直接插入)


插入排序是基于互相比较的排序。所谓的“比较”,就是通过比较数组中的元素,看谁大谁小,根据结果对应调整元素的位置。


1. 插入排序法基本思路

初始时先默认将第一个元素标记为已排序

然后提取第一个没有排序过的元素,找出插入提取元素的地方并和已经排序过的元素进行比较。

比较大小若条件成立,则将已排序过的元素往右移1个单位,如果条件不成立,则在现有位置直接插入。

以此类推,直到所有元素均排序完毕


还以[20,10,15,30,12]这个数组举例

将第一个元素 (20) 标记为已经排序过;

提取第一个没有排序过的元素 (10);

找出插入提取元素的地方;和已经排序过的元素 20 比较;

20 大于 10 成立,  则将现在已经排序过的元素20向右移动1格;

在数组的最开始(没有东西可以比较),则在现有位置上插入元素。


提取第一个没有排序过的元素 (15);

找出插入提取元素的地方;和已经排序过的元素 20 比较;

20 大于 15 成立,  则将现在已经排序过的元素20 向右移动1格;

10 大于 15 不成立, 在现有位置上插入一个元素;

提取第一个没有排序过的元素 (30);

找出插入提取元素的地方;和已经排序过的元素 20 比较。

20 大于 30 不成立, 在现有位置上插入一个元素;

提取第一个没有排序过的元素 (12)。

……..

避免篇幅过大导致视觉疲劳,下面几步大家进行自我思考和理解。


2. 插入排序法全流程


3. 插入排序法总结

由“有序组”和“待插入组”组成

每一轮都有一个待插入对象(可以接收实时数据进行排序)直到“待插入组元素为0”


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

分享到:

您可能感兴趣的新闻

百度智能小程序最新进展:月活用户突破3亿,Q3季度智能小程序数量翻番!

百度智能小程序最新进展:月活用户突破3亿,Q3季度智能小程序数量翻番!

自流量竞争升级到平台竞争开始,小程序也成为互联网巨头战略布局的重点。在此背景下,各具特色的小程序开始出现。11月25日,百度披露智能小程序月活..

一则关于建站产品选择的实用导览指南!

一则关于建站产品选择的实用导览指南!

网站作为企业在互联网上最直观的展示名片,已经被越来越多的企业接受和推广。就连众多传统企业、政府机关、事业单位等,也一并被时代的浪潮冲到了线..

怎样快速区分响应式布局与自适应式布局?企业又该如何抉择?

怎样快速区分响应式布局与自适应式布局?企业又该如何抉择?

随着智能手机、ipad等智能移动设备的普及,推动了网站风格样式的更新迭代。为解决PC端和移动端不同访客的用户体验问题,众多的建站产品供应商分别提..

400-0731-177
传真:0731-82735258
邮箱:jwkj@hnjing.com
地址:湖南省长沙市岳麓区尖山路18号B7栋 竞中心
竞网智赢官方微信扫一扫关注官方微信

关注竞网

官方微信
官方微博
官网首页
QQ咨询
百度商桥
建站需求

给我们拨打电话

400-0731-177

微信沟通
微信沟通 微信沟通
返回顶部

请问您的建站需求是?

留下您的联系方式,我们会尽快为您免费提供建站方案

立即开启您的互联网营销之旅

输入您的电话号码,点击通话,稍后您将接到我们的电话,该通话对您 完全免费 ,请放心接听!

可获得免费提供建站方案或免费网站诊断服务

¥ 500 元直减券

恭喜您!
抽到 竞网建站
发出的红包