【数据结构与算法】排序算法(上)——插入排序与选择排序

文章目录

  • 一、常见的排序算法
  • 二、插入排序
    • 2.1、直接插入排序
    • 2.2、希尔排序( 缩小增量排序 )
  • 三、选择排序
    • 3.1、直接选择排序
    • 3.2、堆排序
      • 3.2.1、堆排序的代码实现

一、常见的排序算法

在这里插入图片描述
常见排序算法中有四大排序算法，第一是插入排序，二是选择排序，三是交换排序，四是归并排序。本站文章针对前两个排序，这其中不才将拿出每个排序中所具有代表性的排序算法进行深入解读。

二、插入排序

基本思想：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中我们玩扑克牌时，就用了插入排序的思想
在这里插入图片描述

2.1、直接插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：


把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移
在这里插入图片描述
代码实现：

void InsertSort(int* arr, int n) {// 外层循环，从第二个元素开始，逐步处理每个元素for (int i = 0; i < n - 1; i++) {// tmp 是当前元素的索引，初始值是 i+1，表示从第二个元素开始int tmp = i + 1;// end 是已排序部分的最后一个索引，初始值是 iint end = i;// 把当前比较的数据保护起来int num = arr[tmp];// 内层循环，寻找当前元素插入的位置while (end >= 0) {// 如果已排序部分的元素大于当前元素if (arr[end] > num) {// 已经把当前元素比较保护好，可以将已排序部分的元素向右移动arr[tmp] = arr[end];// tmp 和 end 都向左移一位tmp--;end--;}else {// 找到合适的位置，不需要继续向左移动了break;}}// 将当前元素插入到合适的位置arr[tmp] = num;}
}

时间复杂度：

  • 最好的情况是：如果数组已经是有序的（或者几乎有序），只需要进行一轮比较，时间复杂度是O(n)。
  • 最坏的情况是：数组是逆序的，每次都要比较所有已排序的元素，时间复杂度是O(n²)。

直接插入排序的特性总结：

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：稳定

2.2、希尔排序( 缩小增量排序 )

希尔排序法又称缩小增量法。希尔排序法的基本思想是：

先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时即为直接插入排序，所有记录在统一组内排好序。

希尔排序的工作原理：

  1. 初始间隔（gap）：希尔排序的关键点在于选择一个合适的“间隔”序列，也叫做增量序列。初始时，希尔排序会使用一个较大的间隔，比如n/2，然后通过逐渐缩小间隔来进行多次排序。

  2. 分组插入排序：每次排序时，希尔排序将待排序的序列按间隔分成多个子序列。然后对每个子序列分别进行插入排序。例如：间隔为2时，序列的第一个元素、第三个元素、第五个元素、第七个元素、第九个元素，形成一个子序列(如下图gap=2时)。然后对这个子序列进行插入排序。接着处理间隔更小的子序列，直到间隔为1时，整个序列就是有序的。

  3. 逐渐减小间隔：随着间隔的逐步减小，元素变得越来越接近排序完成，最后，当间隔为1时，希尔排序就变成了直接插入排序。

在这里插入图片描述
总的来说，希尔排序就是直接排序PRO MAX版本。使用希尔排序，它可以快速地把大数放在右边，小数放在左边。在快速区分大小数位置之后，就比原先的混乱顺序变得更有序，在直接插入排序中，我们知道元素集合越接近有序，直接插入排序算法的时间效率越高，我们就不断的往有序的方向靠近，最后再直接在使用直接排序就可以缩短大部分时间。如下图，我们使用gap来表示每一次比较的跨越元素个数。

代码的实现：（两种循环的实现）

void shellSort(int* arr, int n) {int gap = n / 3 + 1;while (gap > 1) {// 判断收缩gap的值，直到gap值为1时，完成插入排序//int gap = 3;//for (int j = 0; j < gap; j++) {//end要分别对gap分出的gap个数组进行排序，这样便可完成数组中每个位置的比较//for (int i = 0; i < n - 1 - gap; i += gap) { // 把间距把分开的每个tmp位置都进行插入排序for (int end = 0; end < n  - gap; end++) { //这样设置循环可以把end在数组中的每个位置都走一边 与上面两层循环相比只是逻辑不同，效率上没有变化//int end = i + j;int tmp = arr[end + gap];while (end >= 0) { //把当前tmp插入到合适的位置if (arr[end] > tmp) {arr[end + gap] = arr[end];end -= gap;}else {break;}}arr[end + gap] = tmp;}//}//}gap = gap / 3 + 1;}
}
  • 排序代码的实现得有里到外的编写，这样容易把控
  • 首先编写一个正常的直接插入排序，并且把gap加上。
for (int i = 0; i < n - 1; i++) {int gap = 1;int tmp = i + gap;int end = i;int num = arr[i + gap];while (end >= 0){if (arr[end] > num) {arr[tmp] = arr[end];tmp--;end--;}else {break;}}arr[tmp] = num;
}
  • 这样我们就改好了直接插入排序有gap时的写法了
  • 我们开始修改gap每次跳转的范围，首先以gap=2为例，首先我们把i每次增加的个数都增加gap个。我们也优化变量
int gap = 2;
for (int i = 0; i < n - 1 - gap; i += gap) {int end = i;int tmp = arr[end + gap];while (end >= 0) { //把当前tmp插入到合适的位置if (arr[end] > tmp) {arr[end + gap] = arr[end];end -= gap;}else {break;}}arr[end + gap] = tmp;
}
  • 这个时候，我们就完成了一个子序列：第一个元素、第三个元素、第五个元素、第七个元素、第九个元素的元素排序。但是，我们gap = 2时，我们是把原数组分为两个子序列。所以要对两个子序列都进行排序。这样我们就必须在外面再套一层循环来把gap分开的子序列都进行排序。(如下图中被分开为红蓝两个子序列)在这里插入图片描述
int gap = 2;
for (int j = 0; j < gap; j++) {for (int i = 0; i < n - 1 - gap; i += gap) {int end = i + j;int tmp = arr[end + gap];while (end >= 0) { //把当前tmp插入到合适的位置if (arr[end] > tmp) {arr[end + gap] = arr[end];end -= gap;}else {break;}}arr[end + gap] = tmp;}
}
  • 子序列的第一个节点起始点，永远不会再第一个子序列的第二个节点的后面，所以我们可以通过套用外层循环j遍历的控制end的起始地址，则这样就可以完成多个子序列的访问。
    在这里插入图片描述
  • 这时候我们就可以完成所有子序列的第一次排序。但是为了完成原数组的整体排序，我们必须要让gap每完成一个排序就减少，直到gap = 1时，变为直接插入排序完成数组的排序。
int gap = 2;
while (gap > 0) {for (int j = 0; j < gap; j++) {for (int i = 0; i < n - 1 - gap; i += gap) {int end = i + j;int tmp = arr[end + gap];while (end >= 0) { //把当前tmp插入到合适的位置if (arr[end] > tmp) {arr[end + gap] = arr[end];end -= gap;}else {break;}}arr[end + gap] = tmp;}}gap--;
}
  • 这样我们就完成了一个低效版本的希尔排序

为何说是低效版本呢？因为gap的值是固定的。当数据量达到数十亿的级别之后。我们一个区区的常量2的效率与直接插入排序的效率几户一样。

这时候就有大佬研究出目前位置希尔排序gap的最好取值之二(n是数组的元素个数)：gap = n/2或gap = n/3 + 1(最快)。我们再自己手搓希尔排序时，使用gap选择哪个都可以。不才选择gap = n/3 + 1作为示范。

int gap = n;
while (gap > 1) {gap = (gap / 3) + 1;for (int j = 0; j < gap; j++) {for (int i = 0; i < n - 1 - gap; i += gap) {int end = i + j;int tmp = arr[end + gap];while (end >= 0) { //把当前tmp插入到合适的位置if (arr[end] > tmp) {arr[end + gap] = arr[end];end -= gap;}else {break;}}arr[end + gap] = tmp;}}
}
  • 在使用gap = n/3 + 1之后，每次gap缩小值都是gap/3 + 1。无论是什么数循环到一定次数后最后除三的都会变为零。当除3等于0时再加一gap就等于1，这时候就是直接插入排序。当gap == 1时，就不会再进入循环。

但此时，上面循环中i、j就只是为了控制end变量起始位置可以遍历一遍数组，end每次都是与gap位后的数值进行比较。那么我们就可以把两层循环变为一层循环

void shellSort(int* arr, int n) {int gap = n;while (gap > 1) {// 再收缩gap的值，直到gap值为1时，完成插入排序gap = gap / 3 + 1;for (int end = 0; end < n  - gap; end++) { //这样设置循环可以把end在数组中的每个位置都走一边，但效率上没有变化int tmp = arr[end + gap];while (end >= 0) { //把当前tmp插入到合适的位置if (arr[end] > tmp) {arr[end + gap] = arr[end];//每次都与前gap值为比较end -= gap;}else {break;}}arr[end + gap] = tmp;}}
}

希尔排序的特性总结：

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就
    会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
  3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书籍中给出的希尔排序的时间复杂度都不固定：

《数据结构-用面相对象方法与C++描述》— 殷人昆

在这里插入图片描述
不才上面使用的是Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，暂时就按照：O(n1.25)到O(1.6*n1.25)来算，按照我们也可以粗略的归类与O(n * logn)的量级，但是真实的时间复杂度是比O (n * logn)大。

三、选择排序

基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

3.1、直接选择排序

  • 在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
  • 若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
  • 在剩余的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素
    在这里插入图片描述

直接选择排序的特性总结：

  1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定

3.2、堆排序

在堆的的逻辑结构中是严格遵循有序但这并不意味着整个堆的物理存储结构是有序的。堆排序的目的是对堆中的元素进行排序，通过堆这种数据结构的特性来实现元素的排序。

排序中分为升序和降序，堆排序即利用堆的思想来进行排序

  • 排升序对应着建大堆
  • 排降序对应着建小堆

堆排序的方法：

  • 因为堆排序的逻辑与堆的删除逻辑是完全一致的，都是先把堆顶元素与最后一个元素进行交换之后向下调整。与删除不同的是，删除需要把数组中最后一个元素完全删除，排序只需要不再理会数组最后一个元素，不用真正删除元素。

排升序建大堆的原因在把堆顶元素与最后一个元素进行交换之后，堆中的中最大的值被放置在物理结构的最右边，如此循环即可完成结构的升序。降序同理
在这里插入图片描述

把堆中元素进行升序排序

我们使用上述大堆的例子创建有序的物理结构，物理结构：[95，70，8，21，5，3，4，6，9，1]
在这里插入图片描述
首先交换堆顶与最后一个元素(如下图)
在这里插入图片描述
在交换完成后逻辑结构上不再把95结点当作堆的结点，之后进行向下调整(如下图)
在这里插入图片描述
此时，物理结构为：[70，21，8，9，5，3，4，6，1，95]。这样就把最大值放置在物理结构最右边，并且忽略最后一个结点后，其他结点依旧保持着大堆结构。(与删除堆顶逻辑完全相同)

循环上述操作可得下图：
在这里插入图片描述
一定次数的循环后，会得到下图
在这里插入图片描述
观察上图可以看到此时物理结构:[8，6，3，1，5，4，9，21，70，95]，只要循环次数足够，就可以把物理结构排为升序

最终可得下图：
在这里插入图片描述
此时我们就完成了：堆中元素的升序排序。物理结构为：[1，3，4，5，6，8，9，21，70，95]。

3.2.1、堆排序的代码实现

void HeapSort(HPDataType* arr, int capacity, int farent) {assert(arr); // 确保传入的数组指针不为空int cp = capacity; // 存储堆的初始容量// 当堆中还有元素时进行排序while (cp != 0) {// 将堆顶元素（最大或最小元素）与当前堆的最后一个元素交换HeapSwap(arr, 0, cp - 1); // 减少堆的有效大小（去除已排序的最大元素）--cp;// 调整堆结构，确保堆的性质依然保持AdjustDown(arr, cp, farent);}
}
  • 首先把堆顶元素与最后一个叶子节点的元素进行交换。
  • 之后--元素个数，把已经交换完成的最大值(最小值)忽略。
  • 完成后再向下调整。把交换完成后的顺序表，重新调整为大堆(小堆)。

堆排序的特性总结：

  1. 堆排序使用堆来选数，效率就高了很多。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定

ps：剩下的两大排序真正紧张制作中，欲知后事如何，请听下回分解~~

以上就是本章所有内容。若有勘误请私信不才。万分感激💖💖 如果对大家有帮助的话，就请多多为我点赞收藏吧~~~💖💖
请添加图片描述

ps:表情包来自网络，侵删🌹

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/482142.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

qml项目创建的区别

qml项目创建的区别

在Qt框架中&#xff0c;你可以使用不同的模板来创建应用程序。你提到的这几个项目类型主要针对的是Qt的不同模块和用户界面技术。下面我将分别解释这些项目类型的区别&#xff1a; 根据你提供的信息&#xff0c;以下是每个项目模板的详细描述和适用场景&#xff1a; Qt Widgets…
阅读更多...
【热门主题】000077 物联网智能项目：开启智能未来的钥匙

【热门主题】000077 物联网智能项目：开启智能未来的钥匙

前言&#xff1a;哈喽&#xff0c;大家好&#xff0c;今天给大家分享一篇文章&#xff01;并提供具体代码帮助大家深入理解&#xff0c;彻底掌握&#xff01;创作不易&#xff0c;如果能帮助到大家或者给大家一些灵感和启发&#xff0c;欢迎收藏关注哦 &#x1f495; 目录 【热…
阅读更多...
时序约束进阶六：Set_Clock_Groups详解

时序约束进阶六：Set_Clock_Groups详解

目录 一、前言 二、时钟间关系 2.1 时钟关系分类 2.2 时钟关系查看 三、set_clock_groups设置 3.1 使用格式 3.2 优先级 3.3 约束设置示例 3.4 约束效果查看 四、Exclusive差异说明 4.1 Asynchronous 4.2 Logically_exclusive与Physically_exclusive 4.3 logical…
阅读更多...
智慧银行反欺诈大数据管控平台方案（一）

智慧银行反欺诈大数据管控平台方案（一）

智慧银行反欺诈大数据管控平台建设方案的核心在于通过整合先进的大数据技术和深度学习算法&#xff0c;打造一个全面、智能且实时的反欺诈系统&#xff0c;以有效识别、预防和应对各类金融欺诈行为。该方案涵盖数据采集、存储、处理和分析的全流程&#xff0c;利用多元化的数据…
阅读更多...
系统架构：MVVM

系统架构：MVVM

引言 MVVM 全称 Model-View-ViewModel&#xff0c;是在 MVP&#xff08;Model-View-Presenter&#xff09;架构模式基础上的进一步演进与优化。MVVM 与 MVP 的基本架构相似&#xff0c;但 MVVM 独特地引入了数据双向绑定机制。这一创新机制有效解决了 MVP 模式中 Model 与 Vie…
阅读更多...
ARM CCA机密计算安全模型之硬件强制安全

ARM CCA机密计算安全模型之硬件强制安全

安全之安全(security)博客目录导读 [要求 R0004] Arm 强烈建议所有 CCA 实现都使用硬件强制的安全（CCA HES）。本文件其余部分假设系统启用了 CCA HES。 CCA HES 是一个可信子系统的租户——一个 CCA HES 主机（Host），见下图所示。它将以下监控安全域服务从应用处理元件（P…
阅读更多...
【电子通识】失效分析的流程和方法

【电子通识】失效分析的流程和方法

在文章：【电子通识】失效分析的基本概念-CSDN博客 中我们讲到失效分析是是指产品失效后，根据失效的现象/模式，通过分析和验证，模拟重现失效的现象，找出失效的原因，挖掘出失效的机理的活动。 同时还讲到失效模式和失效机理，并且以LED和贴片电阻做为举例。 失效模式是失效…
阅读更多...
Flutter：页面滚动

Flutter：页面滚动

1、单一页面&#xff0c;没有列表没分页的&#xff0c;推荐使用&#xff1a;SingleChildScrollView() return Scaffold(backgroundColor: Color(0xffF6F6F6),body: SingleChildScrollView(child: _buildView()) );2、列表没分页&#xff0c;如购物车页&#xff0c;每个item之间…
阅读更多...
facebook欧洲户开户条件有哪些又有何优势？

facebook欧洲户开户条件有哪些又有何优势？

在当今数字营销时代&#xff0c;Facebook广告已成为企业推广产品和服务的重要渠道。而为了更好地利用这一平台&#xff0c;广告主们需要理解不同类型的Facebook广告账户。Facebook广告账户根据其属性可分为多种类型&#xff0c;包括个人广告账户、企业管理&#xff08;BM&#…
阅读更多...
WEB攻防-通用漏洞CSRFSSRF协议玩法内网探针漏洞利用

WEB攻防-通用漏洞CSRFSSRF协议玩法内网探针漏洞利用

CSRF构造工具&#xff0c;也可以用bp构造 选中要保存的请求&#xff0c;点击Generate HTML,生成带有添加用户请求的html文件&#xff0c;然后将构造的html放在网站上&#xff0c;生成访问地址&#xff0c;诱导管理员点击链接&#xff0c;就会添加用户 start Recording之后就会…
阅读更多...
C#面向对象之访问限制，类基础，继承

C#面向对象之访问限制，类基础，继承

文章目录 1 访问限制1.1 简介 2 类基础讲解2.1 类定义2.2 构造函数2.2.1 构造函数2.2.2 静态构造函数2.2.3 初始化顺序2.2.4 对象初始化器 2.3 析构函数2.4 类的静态成员2.5 匿名对象2.5.1 定义2.5.2 匿名对象的创建 3 继承3.1 基类和派生类3.2 基类初始化3.3 Partial类3.3.1 定…
阅读更多...
代码之丑第一期-缩进

代码之丑第一期-缩进

各位小伙伴们&#xff0c;大家好&#xff01;咱今天就算是正式开张了。实不相瞒&#xff0c;第一期的内容早已写好&#xff0c;但唯独这开篇方式&#xff0c;笔者想了好些时间&#xff0c;包括但不限于如下风格&#xff1a; 斗破苍穹式&#xff08;已经三刷&#xff09;&#…
阅读更多...
JVM 性能调优 -- JVM常用调优工具【jps、jstack、jmap、jstats 命令】

JVM 性能调优 -- JVM常用调优工具【jps、jstack、jmap、jstats 命令】

前言&#xff1a; 前面我们分析怎么去预估系统资源&#xff0c;怎么去设置 JVM 参数以及怎么去看 GC 日志&#xff0c;本篇我们分享一些常用的 JVM 调优工具&#xff0c;我们在进行 JVM 调优的时候&#xff0c;通常需要借助一些工具来对系统的进行相关分析&#xff0c;从而确定…
阅读更多...
linux上离线部署Mysql5.7.22

linux上离线部署Mysql5.7.22

官网下载地址: https://downloads.mysql.com/archives/community/ Mysql安装步骤&#xff1a; 1.上传mysql安装包 上传 mysql-5.7.22-linux-glibc2.12-x86_64.tar.gz 到服务器指定目录 2.解压缩 tar -zxvf mysql-5.7.22-linux-glibc2.12-x86_64.tar.gz 3.修改名称 mv mysq…
阅读更多...
日志与线程池

日志与线程池

这里写自定义目录标题 日志Log.hpp测试main.cpp结果 线程池线程池的种类ThreadPool.hpp测试 Task.hpp 和 main.cppTask.hppmain.cpp结果 线程池的单例模式实现方式SignalThreadPool.hpp测试main.cpp 线程安全与重入问题死锁死锁的四个必要条件 日志 日志需要包含的信息 • 时间…
阅读更多...
1.1 数据结构的基本概念

1.1 数据结构的基本概念

1.1.1 基本概念和术语 一、数据、数据对象、数据元素和数据项的概念和关系 数据&#xff1a;是客观事物的符号表示&#xff0c;是所有能输入到计算机中并被计算机程序处理的符号的总称。 数据是计算机程序加工的原料。 数据对象&#xff1a;是具有相同性质的数据元素的集合&…
阅读更多...
泷羽sec学习打卡-shell命令5

泷羽sec学习打卡-shell命令5

声明 学习视频来自B站UP主 泷羽sec,如涉及侵权马上删除文章 笔记的只是方便各位师傅学习知识,以下网站只涉及学习内容,其他的都 与本人无关,切莫逾越法律红线,否则后果自负 关于shell的那些事儿-shell5 字符串运算符逻辑运算符之布尔运算符实践是检验真理的唯一标准 字符串运算…
阅读更多...
Elasticearch索引mapping写入、查看、修改

Elasticearch索引mapping写入、查看、修改

作者&#xff1a;京东物流 陈晓娟 一、ES Elasticsearch是一个流行的开源搜索引擎&#xff0c;它可以将大量数据快速存储和检索。Elasticsearch还提供了强大的实时分析和聚合查询功能&#xff0c;数据模式更加灵活。它不需要预先定义固定的数据结构&#xff0c;可以随时添加或修…
阅读更多...
Mybatis Plus 增删改查方法（一、增）

Mybatis Plus 增删改查方法（一、增）

先定义一个简单的测试表&#xff0c;执行脚本如下&#xff1a; create table user(id bigint primary key auto_increment,name varchar(255) not null,age int not null default 0 check (age > 0) ); 根据Spingbootmybatisplus的结构根据表自行构建结构&#xff0c;大致…
阅读更多...
本地部署 WireGuard 无需公网 IP 实现异地组网

本地部署 WireGuard 无需公网 IP 实现异地组网

WireGuard 是一个高性能、极简且易于配置的开源虚拟组网协议。使用路由侠内网穿透使其相互通讯。 第一步&#xff0c;服务端&#xff08;假设为公司电脑&#xff09;和客户端&#xff08;假设为公司外的电脑&#xff09;安装部署 WireGuard 1&#xff0c;点此下载&#xff08;…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023