【数据结构与算法篇】手撕八大排序算法之交换排序

在这里插入图片描述

​👻内容专栏: 《数据结构与算法篇》
🐨本文概括:常见交换排序包括冒泡排序与快速排序,本篇讲述冒泡排序与快速排序的思想及实现、复杂度分析。
🐼本文作者: 花 蝶
🐸发布时间:2023.8.27

一、冒泡排序

基本思想

冒泡排序(Bubble Sort)是一种简单的排序算法,其基本思想是通过两两交换相邻元素的位置,使得较大(或较小)的元素逐步“冒泡”到数组的一端(顶部或底部),重复“冒泡”的过程,直到序列没有要交换的元素为止,从而实现排序。

​算法步骤

1、 从数组的起始位置开始,依次比较相邻的两个元素。如果相邻元素的顺序错误(前者大于后者,或者前者小于后者,取决于是升序还是降序排序),则交换这两个元素的位置;
2、继续进行相邻元素的比较和交换,直到遍历到数组的末尾。这样一轮下来,最大(或最小)的元素就会“冒泡”到数组的一端。
3、重复上述步骤,但不再考虑已经排序好的末尾部分。每一轮操作都会将一个最大(或最小)的元素移到正确的位置。
4、 经过多轮的比较和交换,最终整个数组会变得有序。如果在某一轮没有进行任何交换操作时,说明数组已经有序,可以直接跳出循环。

动图演示

在这里插入图片描述

代码实现

//冒泡排序
//时间复杂度:O(N^2)
void BubbleSort(int* a, int n)
{//控制冒泡排序的趟数for(int i = 0; i < n - 1; i++){//假设数组有序int flag = 1;//控制每趟的过程for (int j = 0; j < n - 1 - i; j++){if (a[j] > a[j + 1]){Swap(&a[j], &a[j + 1]);flag = 0;}}//说明没有发生交换,数组已经有序,跳出循环即可if (flag == 1) break;}
}

冒泡排序的特性

冒泡排序的核心思想就是通过反复比较相邻元素并交换它们的位置,从而逐步将最大(或最小)的元素移动到合适的位置。尽管冒泡排序的时间复杂度较高(平均和最坏情况下都是 O(N^2),可以看作是一个等差数列的求和),但它的实现相对简单,适用于小规模的数据集,因此具有较强的教学意义,想必大家在刚开始学习编程时学的一个排序就是冒泡排序吧哈哈。

二、快速排序(递归版本)

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

//快排(递归版本)
void QuickSort(int* a, int begin, int end)
{if (begin >= end) return;int keyi = Partition(a, begin, end); //前序遍历//递归基准值左边的区间QuickSort(a, begin, keyi - 1);//递归基准值右边的区间QuickSort(a, keyi + 1, end);
}

上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,大家在写递归框架时可想想二叉树前序遍历规则即可快速写出来,后续只需分析如何按照基准值来对区间中数据进行划分的方式即可。
下面用三个版本实现:hoare版本、挖坑法、前后指针法

1.hoare版本

1、选择基准元素key,通常是数组中的第一个元素。
2、使用两个指针LR,一个指向数组的开头(较小值的区域),一个指向数组的末尾(较大值的区域)。
3、交换的目标是L找到比基准大的元素,R找到比基准小的元素。不断交换指针所指的元素,直到两个指针相遇。
4、当两个指针相遇时,交换基准元素与当前相遇位置的元素,此时数组被划分为左右两个子数组。
5、对左右两个子数组递归地应用相同的分区步骤,直到所有子数组都有序

算法分析

👇①:原始序列
在这里插入图片描述
👇②:right向前移动,找比key小的位置,left往后移动找比key大的位置,然后交换。
在这里插入图片描述
👇③:继续往后寻找,直到两个指针相遇。
在这里插入图片描述
👇④:交换基准元素与当前相遇位置的元素。
在这里插入图片描述
👇⑤:这样子我们发现基准值左边的区间里面的元素都比基准值小,右边的区间里面的元素都比基准值大。我们可以按照前序遍历的思想对左边区间进行递归操作,右边区间也进行递归操作。

代码实现

//hoare版本
int Partition1(int* a, int left, int right)
{int keyi = left;while (left < right){//注意: 要加上left < right 否则会出现越界//若不判断等于基准值,也会出现死循环的情况//右边找小while (left < right && a[right] >= a[keyi]){right--;}//左边找大while (left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);return left;
}//快排(递归版本)
void QuickSort(int* a, int begin, int end)
{//当区间不存在或者只剩一个元素,就回溯if (begin >= end) return;int keyi = Partition1(a, begin, end);//前序遍历//递归基准值左边的区间QuickSort(a, begin, keyi - 1);//递归基准值右边的区间QuickSort(a, keyi + 1, end);
}

2.挖坑法

挖坑法的基本思想是:

  • 1、首先,选择一个基准元素(通常是数组中的第一个元素)作为“坑”(hole)。前提需要将这个基准元素用一个临时变量key存起来。
  • 2、将基准元素挖出,形成一个空位(坑)。
  • 3、从数组的另一端开始,从右向左遍历,找到一个比基准元素小的元素,然后将这个元素填入之前的坑中。
  • 4、继续从左向右遍历,找到一个比基准元素大的元素,然后将这个元素填入上一步的坑中。
  • 5、重复执行步骤 3 和步骤 4,直到左右指针相遇。
  • 6、此时,基准元素的位置就是这个相遇的位置,将基准元素填入这个坑中。

算法分析

👇①:原始序列
在这里插入图片描述
👇②:将基准值存放到临时变量key中,形成一个坑位。
在这里插入图片描述
👇③:从右向左遍历,R找到比基准值小的元素,将这个元素填入到之前的坑中,此时当前位置就形成了新坑。
在这里插入图片描述
👇④:紧接着,从左往右遍历,L寻找比基准值大的元素,将这个元素填入到上一步的坑中,此时当前位置形成了新坑。
在这里插入图片描述
👇⑤:重复以上步骤后,直到左右指针相遇,最后会形成一个坑,将临时变量放入坑中。
在这里插入图片描述
👇⑥:这样子我们发现基准值左边的区间里面的元素都比基准值小,右边的区间里面的元素都比基准值大。我们可以按照前序遍历的思想对左边区间进行递归操作,右边区间也进行递归操作。

代码实现

//挖坑法
int Partition2(int* a, int left, int right)
{int key = a[left];//挖坑int hole = left;while (left < right){//右边找小while (left < right && a[right] >= key){right--;}a[hole] = a[right];hole = right;//左边找大while (left < right && a[left] <= key){left++;}a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}
//快排(递归版本)
void QuickSort(int* a, int begin, int end)
{//当区间不存在或者只剩一个元素,就回溯if (begin >= end) return;int keyi = Partition2(a, begin, end);//前序遍历//递归基准值左边的区间QuickSort(a, begin, keyi - 1);//递归基准值右边的区间QuickSort(a, keyi + 1, end);
}

3.前后指针法

基本思想:在快速排序的划分过程中,使用前后指针法来确定基准元素的位置,最后将数组划分成两部分,一部分小于基准元素,另一部分大于基准元素。

  • 1、首先,选择一个基准元素key(通常是数组中的第一个元素)。
  • 2、使用两个指针,prev指向数组的开头,cur指向prev的后一个位置。
  • 3、判断cur指向的数据是否小于key。若小于,则prev后移一位,cur指向的内容与prev指向的内容交换,然后cur++
  • 4、若cur指向的数据大于key,则cur++
  • 重复步骤3和步骤4,直到cur指针走完(最后一个元素的下一个位置)
  • 最后,将keyprev指向的元素交换。

动图演示

在这里插入图片描述

//前后指针法
int Partition3(int* a, int left, int right)
{int prev = left;int cur = prev + 1;int keyi = left;//cur小于key,交换++prev与cur的位置//将大的位置翻滚时往后挪动,小的位置移动前面while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[cur], &a[prev]);}cur++;}//将key与prev指向的元素交换。Swap(&a[prev], &a[keyi]);return prev;
}//快排(递归版本)
void QuickSort(int* a, int begin, int end)
{//当区间不存在或者只剩一个元素,就回溯if (begin >= end) return;int keyi = Partition3(a, begin, end);//前序遍历//递归基准值左边的区间QuickSort(a, begin, keyi - 1);//递归基准值右边的区间QuickSort(a, keyi + 1, end);
}

快速排序(递归版本)的特性

时间复杂度

选择基准元素影响时间复杂度:若基准元素key偏向于所有元素中的中位数,则时间复杂度处于较好的情况,若基准元素key是所有元素中最小的,或者接近最小值,那么时间复杂度就处于较坏的情况。

  • 平均情况下的时间复杂度: 在平均情况下,快速排序的时间复杂度为 O(n log n)。这是因为在每次分区过程中,数组会被划分成大致相等的两部分。在每次递归中,都会将问题的规模减半,递归的展开图可以看作是一颗满二叉树,所以递归的深度为 O(log n),每层递归的分区操作都需要 O(n) 的时间,因此总的时间复杂度为 O(n*log n)
  • 最坏情况下的时间复杂度: 在最坏情况下,快速排序的时间复杂度为 O(n^2)。这种情况发生在每次划分后,一个子数组为空,另一个子数组包含所有的元素。这样会导致递归树变得很不平衡,每次递归的问题规模只减少一个元素。虽然快速排序通常能够避免这种情况,但在某些情况下(例如已经有序的数组),最坏情况可能出现。

在这里插入图片描述

解决方案

  • 随机数选择基准元素: 在每次划分时,随机选择一个基准元素,这可以减少最坏情况的发生概率。
  • 三数取中法: 在选择基准元素时,不仅考虑第一个和最后一个元素,还考虑数组中间位置的元素,选择其中值大小居中的元素作为基准。

👇这里提供一种三数取中的方法,以hoare版本为例:

//三数取中,返回下标
int GetMidIndex(int* a, int left, int right)
{int mid = (left + right) >> 1;if (a[left] < a[mid]){if (a[mid] < a[right]) return mid;else if (a[left] > a[right]) return left;else return mid;}else //a[left] > a[mid]{if (a[mid] > a[right]) return mid;else if (a[right] > a[left]) return left;else return right;}
}
//hoare版本
int Partition1(int* a, int left, int right)
{//将中位数与数组的第一个元素(基准值)进行交换int midi = GetMidIndex(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;while (left < right){//右边找小while (left < right && a[right] >= a[keyi]){right--;}//左边找大while (left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);return left;
}

后面会更新快排的非递归版本……可到数据结构专栏查看🥰
更多数据结构与算法系列文章👉😉==> 【传送门】

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

ie ajax十分卡,解决jquery .ajax 在IE下卡死问题的解决方法

解决jquery .ajax 在IE下卡死问题的解决方法 解决IE编码问题第一步&#xff1a; dataType:($.browser.msie) ? "text" : "xml" 先这样做让IE 识别返回的是text 还是xml 第二步&#xff1a; 复制代码 代码如下: function parseXml(xml) { //XML IE编码问题…

数学分析:场论

我们之前知道的是里斯表示定理。 这里看到&#xff0c;对于多重线性映射&#xff0c;里斯表示定理会从内积变成混合积。当然我们还是只考虑三维以内的情况。 于是我们可以把不同的1形式和2形式的下标写上&#xff0c;表示他们相当于内积或者混合积对应的那个向量。 然后还差0形…

设计师:设计师之家装材料知识之家装八项(吊顶材料、门窗材料、五金材料、墙面材料、地面材料、胶粘材料、油漆材料、水电材料等)之详细攻略

设计师&#xff1a;设计师之家装材料知识之家装八项(吊顶材料、门窗材料、五金材料、墙面材料、地面材料、胶粘材料、油漆材料、水电材料等)之详细攻略 目录 家装八项 吊顶材料 门窗材料 五金材料 墙面材料 地面材料 胶粘材料 油漆材料 水电材料 参考文章&#xff1a;…

材料封样信息流程指引

材料封样信息流程指引 一、材料封样流程 1、新项目中标后&#xff0c;由设计院根据合同、招标文件、技术要求填写材料送样清单&#xff08;格式按公司标准化标格填写&#xff09;&#xff0c;并正式下发给采购部、工程管理部及项目部安排后续送样确认&#xff1b; 2、幕墙工程…

EyouCMS响应式木材板材公司模板/易优CMS装修材料类企业网站模板

☑️ 编号&#xff1a;ym247 ☑️ 品牌&#xff1a;EyouCMS ☑️ 语言&#xff1a;PHP ☑️ 大小&#xff1a;22.4MB ☑️ 类型&#xff1a;木材板材公司模板 ☑️ 支持&#xff1a;pcwap &#x1f389; 欢迎免费领取&#xff08;注明编号&#xff09; &#x1f389; ✨ 源码介…

2023最新装修材料石膏线品牌加盟类模板源码+织梦内核开发的

正文: 装修材料石膏线品牌加盟类织梦模板&#xff0c;带手机版数据同步。 效果相当的炫酷&#xff0c;相当简洁大气高端。适用于建材网站源码、石英石网站模版&#xff0c;有兴趣的自行去安装体验吧&#xff0c;其它就没什么好介绍的了。 程序: wweohd.lanzouo.com/iRCs80t…

Linux内核学习(十一)—— 进程地址空间(基于Linux 2.6内核)

目录 一、地址空间 二、内存描述符 三、虚拟内存区域 四、操作内存区域 find_vma() mmap() 和 do_mmap()&#xff1a;创建地址区间 五、页表 一、地址空间 进程地址空间由进程可寻址并且允许进程使用的虚拟内存组成&#xff0c; 每个进程都有一个 32 位或 64 位的平坦&…

在云原生环境中构建可扩展的大数据平台:方法和策略

文章目录 1. **选择适当的云提供商&#xff1a;**2. **采用容器化和微服务架构&#xff1a;**3. **分层架构设计&#xff1a;**4. **弹性计算资源&#xff1a;**5. **使用分布式计算框架&#xff1a;**6. **数据分区和分片&#xff1a;**7. **使用列式存储&#xff1a;**8. **缓…

java 高级面试题整理(薄弱技术-2023)

session 和cookie的区别和联系 session1.什么是session Session是另一种记录客户状态的机制&#xff0c;不同的是Cookie保存在客户端浏览器中&#xff0c;而Session保存在服务器上。客户端浏览器访问服务器的时候&#xff0c;服务器把客户端信息以某种形式记录在服务器上。这就…

第一讲:工业网络的“语言”——通讯标准

工业网络的“语言”——通讯标准 a) CC-Link CANopen Modbus等&#xff1b; b) 民用网络&#xff1a;TCP-IP协议 c) 民用网络VS工业网络——网络架构&#xff1a; i. 民用网络架构&#xff1a; ii. 工业网络架构&#xff1a; 从网络架构上来看&#xff…

时间敏感网络(TSN)关键协议的介绍

TSN的概述 为了简洁明了&#xff0c;此笔记不再介绍TSN的背景知识。 由于通信主体的演进&#xff0c;各个业务对于时间敏感程度愈加严格。为了构建一个统一的数据链路层协议&#xff0c;通过标准化使其在不同的领域都可以同构运行&#xff0c;提供实时数据的传输保障。 时间…

Arduino ESP32 最简单直接获取网络时间方法

Arduino ESP32 最简单直接获取网络时间方法 ✨在 ArduinoESP32核心支持库当中已经包含相关的获取时间的库&#xff0c;所有获取网络时间&#xff0c;只需要连接好网络&#xff0c;调用相关的库函数即可实现NTP时间的获取&#xff0c;免去的额外加载扩展库的头文件。 &#x1f9…

TCN-时间卷积网络

目录 一、引言 二、时序卷积神经网络 2.1 因果卷积&#xff08;Causal Convolution&#xff09; 2.2 膨胀卷积&#xff08;Dilated Convolution&#xff09; 2.3 残差链接&#xff08;Residual Connections&#xff09; 三、讨论和总结 1. TCN的优点 2. TCN的缺点 参考…

DBeaver的安装和使用:windows版

DBeaver官网下载地址&#xff1a;https://dbeaver.io/download/ 下载完成后&#xff0c; 进入傻瓜式安装&#xff1a; 这里会进入重复界面&#xff0c;一样点击下一步即可 选择安装目录&#xff0c;尽量不要选C盘&#xff0c; 我的电脑只有c盘&#xff0c; 没办法 等待安装完成…

这款远程桌面软件开源了

相信在七八年前&#xff0c;大部分读者都使用 QQ 远程控制电脑。到后面&#xff0c;才接触到一些好用的远程控制产品&#xff0c;比如 Teamviewer、向日葵等。 最近&#xff0c;自己装的远程控制产品试用期到了&#xff0c;便想到去 GitHub 找找有没有可以替代的开源项目&#…

Modbus转Profinet网关在大型自动化仓储项目应用案例

在自动化仓储项目中&#xff0c;Modbus是一种常见的通信协议&#xff0c;用于连接各种设备&#xff0c;例如传感器、PLC和人机界面。然而&#xff0c;Modbus协议只支持串行通信&#xff0c;并且数据传输速度较慢。为了提高通信效率和整体系统性能&#xff0c;许多大型仓储项目选…

LeetCode-455-分发饼干-贪心算法

题目描述&#xff1a; 假设你是一位很棒的家长&#xff0c;想要给你的孩子们一些小饼干。但是&#xff0c;每个孩子最多只能给一块饼干。 对每个孩子 i&#xff0c;都有一个胃口值 g[i]&#xff0c;这是能让孩子们满足胃口的饼干的最小尺寸&#xff1b;并且每块饼干 j&#xff…

手机怎么解决同ip多账号_游戏工作室如何实现手游多开多窗口多IP

经常能看到的一个画面就是游戏工作室&#xff0c;一台电脑许多个手机游戏窗口同时进行&#xff0c;需求量1台程序运行好几个微端。或是相同应用程序开启好几个窗口。那样做能够节约成本&#xff0c;不用多个设备。 但他们全是公用相同网络ip地扯得&#xff0c;那麼如何来防止由…

【产品文档】团队介绍PPT模板

今天和大家免费分享团队介绍的PPT模板。团队介绍是向他人展示团队的实力、专业性和能力的重要方式。通过一个有力的团队介绍&#xff0c;您可以突出团队的成员、经验、技能和取得的成就&#xff0c;从而增加信任、吸引合作伙伴、客户或投资者的兴趣 【模板预览】 动态演示效果…

【交换机 挑选】什么交换机适合游戏工作室

【交换机 挑选】如何选择合适的交换机&#xff1f;什么交换机适合游戏工作室&#xff1f;交换机作为局域网数据转发的核心设备&#xff0c;其性能及功能决定着局域网的可管理性和数据转发性能&#xff0c;选择交换机时ONV/光网视小编建议可以从以下几方面去考虑&#xff1a;1.端…