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

用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...

一个基于ASP.NET Core完全开源的CMS 解决方案

...

用 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 Core EFCore 属性配置与DbContext 详解

...

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和...

取消回复欢迎 发表评论: