用5分钟熟悉3种经典排序算法,浅显易懂!
yuyutoo 2024-10-12 01:08 10 浏览 0 评论
来源:首席吹牛官(ID:ITman-99)
编辑:妮子小菇凉
若干年前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. 选择排序法总结
每一轮进行跨元素比较
每一轮循环比较都会产生当前最小值(当前最小值:这一轮下来的最小值)
每一轮循环比较后就会少一个元素进行比较(因为每结束一轮就会产生一个当前最小值)
三、插入排序法(直接插入)
插入排序是基于互相比较的排序。所谓的“比较”,就是通过比较数组中的元素,看谁大谁小,根据结果对应调整元素的位置。
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”
除了以上三种排序算法,还有许多不同的排序算法,每个都有其自身的优点和使用场景,当然也有局限性。可以多看几遍全流程动态图弄清来龙去脉,理解性地记忆,希望对你有用。
前自带bug程序员,现不知名产品经理,随缘更新~
欢迎留言
本文由首席吹牛官(ID:ITman-99)原创发布,授权互联网早读课转载。内容仅代表作者独立观点,不代表早读课立场。如需转载,请联系原作者。
相关推荐
- 网络规划建设原来也可以这么简单!
-
废话少说,直接上干货。天气炎热,请各位看官老爷静心阅读。整体思路下图是关于网络建设的所有相关领域,接下来我为大家逐一讲解。网络分层...
- 网络规划设计师笔记-第 1 章 计算机网络原理
-
计算机网络原理1.1计算机网络概论(P1-10)...
- 别输在远见上,网工这样做职业规划,比啥都强
-
01职业中的规划,人生中的buff“职业规划“这个词,其实对很多年轻人,包括曾经年轻的我来说,都不屑一提。...
- 网络规划设计师学习中(个人自学笔记分享1),有一起学习的吗?
-
网络规划设计师,上午考试内容学习:第一章:计算机网络概述(上部分):如果你也在一起学习,那么我们来一起学习吧!坚持1年,争取明年一次性通过!...
- 在微服务中使用 ASP.NET Core 实现事件溯源和 CQRS
-
概述:事件溯源和命令查询责任分离(CQRS)已成为解决微服务设计的复杂性的强大架构模式。基本CQRS表示形式在本文中,我们将探讨ASP.NETCore如何使你能够将事件溯源和CQRS...
- 用 Nginx 部署 ASP.NET Core 应用程序
-
用Nginx部署ASP.NETCore应用程序步骤如下:在Linux中安装.NETCore运行时和Nginx:...
- Asp.net Core启动流程讲解(一)(asp.net core 入门)
-
asp.netcore默认项目包括项目根目录级的Startup.cs、Program.cs、appsettings.json(appsettings.Development.json)launch...
- 十天学会ASP之第五天(十天学会asp教程)
-
学习目的:学会数据库的基本操作1(写入记录)数据库的基本操作无非是:查询记录,写入记录,删除记录,修改记录。今天我们先学习写入记录。先建立一个表单:<formname="form1"met...
- ASP.NET Core 的 WebApplication 类
-
ASP.NETCore提供了3个主机类(Host)。这些类用于配置应用、管理生命周期和启动Web服务。...
- ASP.NET Core中的键控依赖注入(.net依赖注入原理)
-
大家好,我是深山踏红叶,今天我们来聊一聊ASP.NETCore中的FromKeyedServices,它是在.Net8中引入的。这一特性允许通过键(如字符串或枚举)来注册和检索依赖注入(D...
- Asp.net常用方法及request和response-a
-
asp.net教程asp.net常用方法:1、Request.UrlReferrer请求的来源,可以根据这个判断从百度搜的哪个关键词、防下载盗链、防图片盗链,可以伪造(比如迅雷)。(使用全局一般处理...
- asp.net常考面试题(aspnet题库)
-
asp.net常考面试题一,列举ASP.Net页面之间传递值的几种方式?1,使用QueryString,如:......?id=1;response.Redirect()......2,使用Sessi...
- 在Windows系统搭建.NET Core环境并创建运行ASP.NET网站
-
微软于6月27日在红帽DevNation峰会上正式发布了.NETCore1.0、ASP.NET1.0和EntityFrameworkCore1.0,其将全部支持Windows、OSX和...
你 发表评论:
欢迎- 一周热门
- 最近发表
- 标签列表
-
- mybatis plus (70)
- scheduledtask (71)
- css滚动条 (60)
- java学生成绩管理系统 (59)
- 结构体数组 (69)
- databasemetadata (64)
- javastatic (68)
- jsp实用教程 (53)
- fontawesome (57)
- widget开发 (57)
- vb net教程 (62)
- hibernate 教程 (63)
- case语句 (57)
- svn连接 (74)
- directoryindex (69)
- session timeout (58)
- textbox换行 (67)
- extension_dir (64)
- linearlayout (58)
- vba高级教程 (75)
- iframe用法 (58)
- sqlparameter (59)
- trim函数 (59)
- flex布局 (63)
- contextloaderlistener (56)