三大基础排序算法——冒泡排序、选择排序、插入排序
目录
- 前言
- 一、排序简介
- 二、冒泡排序
- 三、选择排序
- 四、插入排序
- 五、对比
- References
前言
在此之前,我们已经介绍了十大排序算法中的:归并排序、快速排序、堆排序(还不知道的小伙伴们可以参考我的 「数据结构与算法」 专栏),今天我们就来介绍三大基础的排序算法:冒泡排序,选择排序和插入排序。
一、排序简介
排序算法(Sorting Algorithm)是一种将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样,性质也大多不同。
稳定性
排序算法的稳定性并不是指最坏时间复杂度和最好时间复杂度是否相等,而是指相等的元素在经过排序之后其相对位置是否发生改变。
下图展示了稳定排序和不稳定排序之间的区别:

按照是否稳定可对十大排序算法做出如下分类:
稳定排序 | 不稳定排序 |
---|---|
冒泡排序、插入排序、归并排序、计数排序、桶排序、基数排序 | 选择排序、希尔排序、快速排序、堆排序 |
时间复杂度
排序算法的时间复杂度分为最好时间复杂度、平均时间复杂度和最坏时间复杂度。
基于比较的排序算法的时间复杂度下限是 O(nlogn)O(n\log n)O(nlogn)。
二、冒泡排序
冒泡排序多次遍历数组,它比较相邻的元素,将不合顺序的进行交换,每一轮遍历都将下一个最大值放到正确的位置上。本质上,每个元素通过「冒泡」找到自己所属的位置。
经过 iii 次遍历后,数组末尾的 iii 项必然是最大的那 iii 项,因此冒泡排序最多需要遍历 n−1n-1n−1 遍数组就能完成排序。
动画演示:

冒泡排序实现:
// a是待排序数组,n是数组长度
void bubble_sort(int a[], int n) {for (int i = n - 1; i; i--)for (int j = 0; j < i; j++)if (a[j] > a[j + 1]) swap(a[j], a[j + 1]);
}
可以看出,若两个元素相等,则它们之间不会发生交换,因此冒泡排序具有稳定性。
冒泡排序通常被认为是效率最低的排序算法,因为在确定最终的位置前必须交换元素。注意到如果在一轮遍历中没有发生元素交换,就说明数组已经有序,此时可以提前终止以避免后续的无用功。
改进后的冒泡排序如下(又称短冒泡):
void bubble_sort(int a[], int n) {int round = n - 1; // 因为冒泡排序至多n-1轮遍历就会结束bool flag = true; // flag为false时代表一轮遍历中没有发生元素交换while (round && flag) {flag = false;for (int i = 0; i < round; i++)if (a[i] > a[i + 1]) {flag = true;swap(a[i], a[i + 1]);}round--;}
}
分析时间复杂度。若数组已经是有序的,则冒泡排序只需遍历一遍数组,不用执行任何交换操作,时间复杂度为 O(n)O(n)O(n)。显然冒泡排序的平均时间复杂度和最坏时间复杂度均为 O(n2)O(n^2)O(n2),且在最坏情况下,冒泡排序需要执行 n(n−1)/2n(n-1)/2n(n−1)/2 次交换操作。
三、选择排序
选择排序在冒泡排序的基础上进行了改进,每次遍历数组时只做一次交换。要实现这一点,选择排序在每次遍历时寻找最小值,并在遍历完后将它放到正确的位置上。第一次遍历后,最小的元素就位;第二次遍历后,第二小的元素就位,以此类推。
📝 当然也可以每次遍历时寻找最大值。
动画演示:

选择排序实现:
void selection_sort(int a[], int n) {for (int i = 0; i < n - 1; i++) {int ith = i;for (int j = i + 1; j < n; j++)if (a[j] < a[ith]) ith = j;swap(a[i], a[ith]);}
}
从代码中可以看出选择排序的最好、平均、最坏时间复杂度均为 O(n2)O(n^2)O(n2)。
选择排序是不稳定的。设有数组 [5,3,3][5,\textcolor{red}{3},\textcolor{green}{3}][5,3,3],第一轮遍历后得到 [3,3,5][\textcolor{green}{3},\textcolor{red}{3},5][3,3,5],第二轮遍历时不会有任何元素交换,可以看到两个 333 的相对位置发生了改变。
四、插入排序
插入排序是一种简单直观的排序算法。它在列表较低的一端(即索引较小的一端)维护一个有序子数组,并逐个将每个新元素「插入」这个子数组。
一个与插入排序相同的操作是打扑克牌时,从牌桌上抓一张牌,按牌面大小插到手牌后,再抓下一张牌。
动画演示:

插入排序实现:
void insertion_sort(int a[], int n) {for (int i = 1; i < n; i++) {int key = a[i];int j = i - 1;while (j >= 0 && a[j] > key) {a[j + 1] = a[j];j--;}a[j + 1] = key;}
}
在数组已经是有序的情况下,while
循环不会被执行,因此插入排序的最好时间复杂度为 O(n)O(n)O(n)。显然,插入排序的平均时间复杂度和最坏时间复杂度均为 O(n2)O(n^2)O(n2)。
插入排序是稳定的,因为它会将待插入元素插入到有序子数组中首个发现的大于等于该元素的位置(因为是从右向左遍历,所以首个发现的位置一定靠右),并不会发生交换。
这里再介绍一下二分插入排序。因为数组的左边已经是有序的了,所以可以用二分查找去寻找待插入元素应当插入的位置。<algorithm>
库中有一个 upper_bound
函数,它可以用来查找一个有序序列中首个大于 xxx 的元素,并返回指向该元素的迭代器。
二分插入排序的实现:
void insertion_sort(int a[], int n) {for (int i = 1; i < n; i++) {int key = a[i];int mid = upper_bound(a, a + i, key) - a;for (int j = i - 1; j >= mid; j--) a[j + 1] = a[j];a[mid] = key;}
}
从时间复杂度的角度来看,二分插入排序与直接插入排序相同。
五、对比
三大基础排序算法的比较列在下表中:
排序算法 | 最好时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
---|---|---|---|---|---|
冒泡排序 | O(n)O(n)O(n) | O(n2)O(n^2)O(n2) | O(n2)O(n^2)O(n2) | O(1)O(1)O(1) | 稳定 |
选择排序 | O(n2)O(n^2)O(n2) | O(n2)O(n^2)O(n2) | O(n2)O(n^2)O(n2) | O(1)O(1)O(1) | 不稳定 |
插入排序 | O(n)O(n)O(n) | O(n2)O(n^2)O(n2) | O(n2)O(n^2)O(n2) | O(1)O(1)O(1) | 稳定 |
References
[1] https://oi-wiki.org/basic/sort-intro/
[2] https://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
[3] https://www.runoob.com/w3cnote/ten-sorting-algorithm.html
[4] https://zhuanlan.zhihu.com/p/42586566
相关文章:

三大基础排序算法——冒泡排序、选择排序、插入排序
目录前言一、排序简介二、冒泡排序三、选择排序四、插入排序五、对比References前言 在此之前,我们已经介绍了十大排序算法中的:归并排序、快速排序、堆排序(还不知道的小伙伴们可以参考我的 「数据结构与算法」 专栏)࿰…...

负载均衡上传webshell+apache换行解析漏洞
目录一、负载均衡反向代理下的webshell上传1、nginx负载均衡2、负载均衡下webshell上传的四大难点难点一:需要在每一台节点的相同位置上传相同内容的webshell难点二:无法预测下一次请求是哪一台机器去执行难点三:当我们需要上传一些工具时&am…...
【ESP 保姆级教程】玩转emqx数据集成篇③ ——消息重发布
忘记过去,超越自己 ❤️ 博客主页 单片机菜鸟哥,一个野生非专业硬件IOT爱好者 ❤️❤️ 本篇创建记录 2023-02-10 ❤️❤️ 本篇更新记录 2023-02-10 ❤️🎉 欢迎关注 🔎点赞 👍收藏 ⭐️留言📝🙏 此博客均由博主单独编写,不存在任何商业团队运营,如发现错误,请…...

支持分布式部署的主流方式 - Session 持久化到 Redis
1.为什么要将 Session 存储在 Redis 中如果我们不将 Session 存储在 MySQL 或者 Redis 中, 那么做出来的项目就只能支持单机部署, 不支持分布式部署. 因为之前我们只是将 Session 存储在当前电脑的内存里面. 当张三去登录的时候, 将 Session 信息存储在 A 服务器, 这个时候负载…...

计算机网络|第二章 物理层|湖科大课程|从零开始的计网学习——物理层(计网入门就看这篇!)
图片来源于胡科大计算机网络课程,https://www.bilibili.com/video/BV1c4411d7jb?p20&vd_sourcedeb12d86dce7e419744a73045bc66364。文章非盈利商业用途,供博主与大家学习参考,如有侵权,请联系我删除!2.1物理层的基…...

【微服务】RabbitMQSpringAMQP消息队列
🚩本文已收录至专栏:微服务探索之旅 👍希望您能有所收获 一.初识MQ (1) 引入 微服务间通讯有同步和异步两种方式: 同步通讯:就像打电话,可以立即得到响应,但是你却不能跟多个人同时通话。 异…...

jenkins +docker+python接口自动化之docker下安装jenkins(一)
jenkins dockerpython接口自动化之docker下安装jenkins(一) 目录:导读 1、下载jenkins 2、启动jenkins 3、访问jenkins 4.浏览器直接访问http://ip/:8080 5.然后粘贴到输入框中,之后新手入门中先安装默认的插件即可,完成后出…...

SpringBoot——Banner介绍
一、什么是BannerBanner即横幅标语,我们在启动SpringBoot项目时会将Banner信息打印至控制台。我们可以输出一些图形、SpringBoot版本信息等内容。默认情况下是通过实现类SpringBootBanner输出的Banner内容,默认的输出内容如下。二、自定义Banner如果不想…...

【STL】综述
STL,一文即可知 文章目录一、STL基本知识概述容器二、序列式容器详述数组容器array向量容器vector双端队列容器deque链式容器list正向链容器forward_list二、关联式容器详述红黑树RB-Tree哈希表参考博客😊点此到文末惊喜↩︎ 一、STL基本知识 概述 STL…...
C++中编译的静态库与动态库
1.什么是库库是写好的现有的,成熟的,可以复用的代码。现实中每个程序都要依赖很多基础的底层库,不可能每个人的代码都从零开始,因此库的存在意义非同寻常。本质上来说库是一种可执行代码的二进制形式,可以被操作系统载…...
JS对象到原始值的转换
JS对象到原始值转换的复杂性 主要由于某些对象类型存在不止一种原始值的表示 对象到原始值转换的三种基本算法 在解释三种算法前需要了解toString valueOf这两个方法 toString 返回对象的字符串表示Array类的toString方法会将每个元素转换为字符串,再使用逗号作为…...

深度复盘-重启 etcd 引发的异常
作者信息: 唐聪、王超凡,腾讯云原生产品中心技术专家,负责腾讯云大规模 TKE 集群和 etcd 控制面稳定性、性能和成本优化工作。 王子勇,腾讯云专家级工程师, 腾讯云计算产品技术服务专家团队负责人。 概况 作为当前中国…...
2023年春招热点面试题(一)------新特性
文章目录一、Spring 6.0 新特性二、Spring Boot 3.0 新特性三、JDK 系列 新特性A.**JDK8新特性(2014年初)(LTS版本)**B. **JDK9新特性(2017年9月)**C.**JDK10新特性(2018年3月)**D.*…...
工程项目管理系统源码+spring cloud 系统管理+java 系统设置+二次开发
工程项目各模块及其功能点清单 一、系统管理 1、数据字典:实现对数据字典标签的增删改查操作 2、编码管理:实现对系统编码的增删改查操作 3、用户管理:管理和查看用户角色 4、菜单管理:实现对系统菜单的增删改查操…...

想要精通算法和SQL的成长之路 - 接雨水
想要精通算法和SQL的成长之路 - 接雨水前言一. 接雨水前言 想要精通算法和SQL的成长之路 - 系列导航 一. 接雨水 原题链接 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 输入:height [0,…...

Vue3 更高效的构建工具——Vite
文章目录前言一、Vite简介1. Vite组成2.为什么选 Vite?二、Vite的优缺点vite优点vite缺点三、使用Vite创建Vue3项目1. 创建 vite 的项目2.项目的结构前言 本文讲解了构建工具 Vite,目前只有vue3才可以使用Vite,如果本文对你有所帮助请三连支持博主。 下…...

优思学院|從《狂飙》高启强爱看的《孙子兵法》到六西格玛项目管理
近期最受人瞩目的,无疑是电视剧《狂飙》中出类拔萃的反派高启强。而在剧中,指引高启强走向顶峰的,正是那部著名的军事经典——《孙子兵法》。 在剧中,高启强在一次村庄改造项目上遇到了困难,但他仍保持冷静࿰…...
如何利用状态机编程实现启保停控制(含Stateflow模型介绍)
状态机的介绍这里不再赘述,概念也很简单没有过多的复杂理论。下面我们直接给出具体实现过程。有限自动状态机详细讲解请参看下面的文章链接: PLC面向对象编程系列之有限状态机(FSM)详解_RXXW_Dor的博客-CSDN博客_有限状态机 plc实现编写PLC控制机器动作类程序时,当分支比较…...

4. sql 语句中常用命令
1. 数据表: 本文中所有命令,测试的数据表结构如下图: 2. 查询语句: 2.1 基础查询:select //查询单个字段: select 字段名 from 表名; //查询多个字段 select 字段名1,字段名2,... from 表名; //查询所…...

第三章 Opencv图像像素操作
目录1.像素1-1.确定像素位置1-2.获取指定像素的像素值1-3.修改像素的BGR值2.用numpy模块操作像素2-1.创建图像1.创建黑白图像2.创建彩色图像3.创建随机图像2-2.拼接图像1.水平拼接hstack()方法2.垂直拼接vstack()方法1.像素 1.像素是构成数字图像的最小单位。每一幅图像都是由M…...

【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...

定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...

【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...