【数据结构】交换排序——冒泡排序 和 快速排序

交换排序——冒泡排序 和 快速排序

  • 一、冒泡排序
  • 二、快速排序
    • 2.1 不同版本的快速排序
      • <1>霍尔版本
        • **1> 开闭区间**
        • **2> key 的取值**
        • **3> 单次循环的筛选条件**
        • **4> 为什么要先右边后左边**
        • **5> 递归停止条件**
      • <2>挖坑版本
      • <3>前后指针版本
    • 2.2 快速排序的优化
      • <1> 三数取中
      • <2> 小区间优化
      • <3> 三路划分
  • 三、总结

一、冒泡排序

冒泡排序是我们初学 c 语言绕不开的排序
假设我们要排一个升序的数组
冒泡排序的原理是
前一个数与后一个数比较
将大的数与小的数交换
然后再往后面进行比较,遍历整个数组

动图演示:
在这里插入图片描述

代码整体:

//冒泡排序
void BubbleSort(int* a, int n)
{for (int j = n - 1; j > 0; j--){//单次排序for (int i = 0; i < j; i++){if (a[i] > a[i + 1]){Swap(&a[i], &a[i + 1]);}}}
}

冒泡排序的最坏情况
整个数组为降序
时间复杂度:O(N ^ 2)

冒泡排序的最好情况
整个数组为升序
时间复杂度:O(N)

二、快速排序

2.1 不同版本的快速排序

<1>霍尔版本

先看下面的动图:
在这里插入图片描述

目标:
选取一个值做 key
key 的左边为 key 的数
key 的右边为 key 的数

实现:

让右边先走,右边找小
再让左边走,左边找大
再让左右两边进行交换

当左右两边相遇时
key 插入到左右两边相遇的位置

下面是代码:

开区间:

//快速排序1(霍尔版本)
void hQuickSort1(int* a, int left, int right)
{//判断递归条件if (left > (right - 1)){return;}//先确定 key 的值int key = left;//进行单次循环int begin = left;int end = right - 1;while (begin < end){//让右边先找小while (begin < end && a[end] >= a[key]){end--;}//左边找大while (begin < end && a[begin] <= a[key]){begin++;}//将 begin 和 end 进行交换Swap(&a[begin], &a[end]);}//将 key 位置的数与两数相遇位置的数交换Swap(&a[key], &a[begin]);key = begin;//将剩余部分一分为二,进行递归//[left, key) key [key + 1, right)hQuickSort1(a, left, key);hQuickSort1(a, key + 1, right);
}

闭区间:

//快速排序2(霍尔版本)
void hQuickSort2(int* a, int left, int right)
{//判断递归条件if (left > right){return;}//先确定 key 的位置int key = left;//进行单次循环int begin = left;int end = right;while (begin < end){//让右边先找小while (begin < end && a[end] >= a[key]){end--;}//左边找大while (begin < end && a[begin] <= a[key]){begin++;}//将 begin 和 end 进行交换Swap(&a[begin], &a[end]);}//将 key 位置的数与两数相遇位置的数交换Swap(&a[key], &a[begin]);key = begin;//将剩余部分一分为二,进行递归//[left, key - 1] key [key + 1, right]hQuickSort2(a, left, key - 1);hQuickSort2(a, key + 1, right);
}
1> 开闭区间

这里面开闭区间的意思是,我们输入端输入时候的数据是开区间还是闭区间
在这里插入图片描述
size 的值是数组元素的个数
因为数组下标是从 0 开始的
当 right = size - 1 时就是闭区间
当 right = size 时就是开区间
所以我们输入端是开区间还是闭区间就是影响递归时的区间取值
为了后面的代码方便我都将取闭区间

2> key 的取值

在这里我们的 key 取值可以是第一个,也可以是最后一个
但是最后都要移到第一个的位置
key的取值最好是整个数组数字的中间值
这样数组的时间复杂度就是完美的 O(N * logN)
所以 key 的取值可以优化,后面会讲到
后面的方法都是先默认取第一个

3> 单次循环的筛选条件

在这里插入图片描述
先说 >=
这样取的目的是跳过与 a[key] 相同的值
因为我们的目的是将数组分为两部分
左边是比 a[key] 小的数
右边是比 a[key] 大的数

但是这样就会造成相同的数它的顺序改变了
那数字 6 举例
就是前面的 6 可能会因为我们最后一步插入
而插入到原先在它后面 6 的后面
在这里插入图片描述
我们说这样的排序是不稳定

再说 begin < end
如果不加上这个条件
就是造成最后 begin 的位置会向后移一位
因为我们是右边先走
当右边停下时就是比 a[key] 小的数
而左边停下条件时找比 a[key] 大的数
所以 begin 还会向后一位
在这里插入图片描述

4> 为什么要先右边后左边

先从右边能保证每次都是右边先找到整个数组小值
然后再左边找大值
若找到了就交换
若没找到就会和右边相遇停止循环
保证每次停止的位置都比 a[key] 小

那我们要想排一个降序数组
我们就可以左边先走找大值,右边再走找小值
或者右边先走找小值,左边再走找大值
这个是很灵活的

5> 递归停止条件

在这里插入图片描述

为什么不是 == ,而是 >
在这里插入图片描述
假设递归到这种程度
此时 key = 1
那么递归后 left = 2 而 right = 1

<2>挖坑版本

先看下面动图:

在这里插入图片描述
挖坑法顾名思义
我们先将 key 位置的数作为一个坑位
右边先走遇到比 keyi 小的就入坑
然后右边就形成了新的坑位
然后左边再走,找比 keyi 大的入坑
如此往复当左边与右边相遇时就将 keyi 入坑

当然在代码实现过程不会真的挖空,会将值直接覆盖``
代码如下:

//快速排序3(挖坑版本)
void wQuickSort(int* a, int left, int right)
{//判断递归条件if (left > right){return;}//确定 key 位置int key = left;//进行单次排序int begin = left;int end = right;//将 key 位置数保存起来//将 key 位置先当作一个坑位int keyi = a[key];while (begin < end){//右边找小,找到小的填到坑位中while (begin < end && a[end] >= keyi){end--;}a[begin] = a[end];//左边找大,找到大的值填到坑位中while (begin < end && a[begin] <= keyi){begin++;}a[end] = a[begin];}//将 keyi 值填入坑位中a[begin] = keyi;key = begin;//将剩余位置进行递归//[left, key - 1] key [key + 1, right]wQuickSort(a, left, key - 1);wQuickSort(a, key + 1, right);
}

与上面霍尔方法有很多相同,而且效率也一样
这个方法是后来人根据霍尔的方法改进来的
但是这个方法的优点是不容易出错
好实现没有那么多弯弯绕绕

<3>前后指针版本

在这里插入图片描述
这个方法有点不好理解
这个方法的运行原理:
在初始化时 pcur 是 prev 的前面一个
然后进行判断若 pcur 下是比 key 小的数
就将 prev++
并且将 pcur++
再将 prev 与 pcur 交换
当相等时我们可以设定条件不让两者交换
然后当 pcur 下是比 key 大的值
将 pcur++
最后当 pcur 超出数组大小时
将 key 与 prev 进行交换

代码实现:

//快速排序4(前后指针版本)
void pQuickSort(int* a, int left, int right)
{//判断递归条件if (left > right){return;}//确定key的位置int key = left;//进行单次排序int prev = left;int pcur = prev + 1;//保存 key 的值int keyi = a[key];while (pcur <= right){if (a[pcur] < a[key] && ++prev != pcur)Swap(&a[pcur], &a[prev]);pcur++;}//将 key 位置的数与两数相遇位置的数交换Swap(&a[key], &a[prev]);key = prev;//将剩余部分一分为二,进行递归//[left, key - 1] key [key + 1, right]pQuickSort(a, left, key - 1);pQuickSort(a, key + 1, right);
}

这个方法也是后人从霍尔那边改进的
优点是代码简洁,代码量少
但其实时间复杂度一样

2.2 快速排序的优化

<1> 三数取中

我们假设一种情况
原数组已经是升序排列好的数组
那每次递归的左边都不存在,右边为剩下的数
这种情况比较极端
但这时的时间复杂度就到惊人的 O(N ^ 2)

当然这种情况就不可能有
更多的情况是我们取到的是数组中较大的数或者较小的数
这时 key 的位置并不是靠近中间
递归时就会降低效率

这是我们可以采用三数取中的方式
我们将左右下标的数与数组中间的数进行比较
我们选出那个中间值
这样可以尽可能避免取到极端值的机率
当然也有可能正好三个都为最大值,那就没办法
但这种机率很小

三数取中的目的就是将取到极端值的概率降低

代码如下:

int The_Mid(int* a, int left, int right)
{int mid = (right + left) / 2;if (a[left] < a[mid]){if (a[left] > a[right]){return left;}else if (a[mid] < a[right]){return mid;}else{return right;}}if (a[left] > a[mid]){if (a[mid] > a[right]){return mid;}else if (a[right] > a[left]){return right;}else{return left;}}
}

在这里插入图片描述
我们同时处理一千万个数进行比较:
在这里插入图片描述
在这里插入图片描述
可以看到优化还是相当明显的

<2> 小区间优化

我们这个快速排序时需要递归的
递归是要在栈开辟空间的
而递归深度太深有栈溢出的风险

而且如果只有几个数就要递归好几次实在是有些不值当
所以我们可以加入别的排序
在递归到只有几个数的时候就切换,提高效率

选择的是直接插入排序
直接插入排序讲解

//先确定 key 的位置
int key = The_Mid(a, left, right);
Swap(&a[key], &a[left]);
key = left;//小区间优化
if ((right - left + 1) < 10)
{//插入排序InsertSort(a + left, (right - left + 1));return;
}

我们加上小区间优化后,也排一千万个数

在这里插入图片描述
这个优化也很多了,除了最后一次可能重复的数太多导致有点慢

<3> 三路划分

上面那些代码对于 key 相同的数我们采取的是不处理
不管他们是在左边还是右边
若是重复的数少还好
但如果重复的数据多时就会影响效率

int a1[] = { 2,3,2,2,3,2,2,3 };
int a2[] = { 6,6,6,6,6,7,8,9,6};

如果我们极端一些,整个数组都是相同的数

int a3[] = { 2,2,2,2,2,2,2,2 };

以前后指针法为例
当遇见相同的数时
pcur 就会一直向后走
直到遇到 right 时就停止
在这里插入图片描述
如上面动图,如果重复的数很多
每次递归时传递的左右区间
会出现左边没有,右边是原区间减一
效率很低
就比如我们统计我国人民的年龄
并进行排序时
十三亿人几乎都在 0 - 100 岁区间
那如果还按照上面那样排就很慢

所以我们用三路划分的方法
所谓三路划分就是将数据分为
比 key 小,与 key 相等,比 key 大三个区间
具体操作先看下面动图:
在这里插入图片描述
来说一下这个排序的过程
begin = left
end = right
cur = left + 1

当 cur 的数比 keyi 小时
将 cur 与 begin 交换,cur++ , begin++

当 cur 的数比 keyi 大时
将 cur 与 begin 交换,end - -

当 cur 与 keyi 相等时
cur++

当 cur > end 时结束

代码如下:

//快速排序(三路划分)
void QuickSort3(int* a, int left, int right)
{//判断递归条件if (left > right){return;}/*int key = left;*///先确定 key 的位置int key = The_Mid(a, left, right);Swap(&a[key], &a[left]);key = left;//小区间优化if ((right - left + 1) < 10){//插入排序InsertSort(a + left, (right - left + 1));return;}//保存 key 的值int keyi = a[key];//保存区间int begin = left;int end = right;int cur = left + 1;//单次排序while (cur <= end){if (a[cur] < keyi){Swap(&a[cur], &a[begin]);cur++;begin++;}else if(a[cur] > keyi){Swap(&a[cur], &a[end]);end--;}else{cur++;}}//将剩余部分一分为二,进行递归//[left, begin - 1] [begin, end] [end + 1, right]QuickSort3(a, left, begin - 1);QuickSort3(a, end + 1, right);
}

但这样排序在重复数不多时效率会低一些

下面是我们生成随机数的方式
rand 生成的随机数是有限的
所以会生成一些重复的数
当我们将 rand + i 就可以降低重复数的量
在这里插入图片描述
我们同样生成一千万个数
(1)重复数多时,有三路划分和无三路划分

在这里插入图片描述
在这里插入图片描述
(1)重复数不多多时,有三路划分和无三路划分
在这里插入图片描述
在这里插入图片描述
可以看到当重复数据多时,三路划分的方法是很快的
但是当重复数据不多时,三路划分就慢了很多
所以在不同的情况,我们要用不同的方法

三、总结

其实经过学习,快速排序其实在发明之初并不是最快的
但是经过多轮改进快速排序已经被存在了 c 语言库中
就是 qsort 这是 c 语言库中的快排

对于快排人们进行了很多研究
当我们要递归的深度过深时
我们可以用自己实现的栈来模拟栈中递归
【数据结构】快速排序——非递归实现快速排序

当然在 c 语言的函数库中不可能搞非递归的方式
于是有人研究出了自省排序
那什么是自省排序呢?
就是它会检查函数递归的深度
当递归的深度到一定程度时,就会转变为别的排序
如堆排,希尔排序
因为假如我们遇到数组中重复数据较多时
上面动图也模拟了
递归会变成一边没有或者很少,一边很多的情况
那么这时我们就将程序转变为堆排,或者希尔排序
当然肯定不如三路划分
但是重在稳定,打造六边形战士,哪种情况都不会很慢

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

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

相关文章

C++模板特化实战:在使用开源库boost::geometry::index::rtree时,用特化来让其支持自己的数据类型

用自己定义的数据结构作为rtree的key。 // rTree的key struct OverlapKey {using BDPoint boost::geometry::model::point<double, 3, boost::geometry::cs::cartesian>; //双精度的点using MyRTree boost::geometry::index::rtree<OverlapKey, boost::geometry::in…

Redis - 集群(Cluster)

一、基本概念 上述的哨兵模式,提⾼了系统的可⽤性.但是真正⽤来存储数据的还是master和slave节点.所有的数 据都需要存储在单个master和slave节点中. 如果数据量很⼤,接近超出了master/slave所在机器的物理内存,就可能出现严重问题了. 如何获取更⼤的空间?加机器即可!所谓&q…

【专题】计算机网络之网络层

1. 网络层的几个重要概念 1.1 网络层提供的两种服务 (1) 让网络负责可靠交付 计算机网络模仿电信网络&#xff0c;使用面向连接的通信方式。 通信之前先建立虚电路 VC (Virtual Circuit) (即连接)&#xff0c;以保证双方通信所需的一切网络资源。 如果再使用可靠传输的网络…

Jmeter性能测试 -3数据驱动实战

软件测试资料领取&#xff1a;[内部资源] 想拿年薪40W的软件测试人员&#xff0c;这份资料必须领取~ 软件测试面试刷题工具&#xff1a;软件测试面试刷题【800道面试题答案免费刷】 什么是数据驱动&#xff1f; 从数据文件中读取测试数据&#xff0c;驱动测试过程的一种测试…

INQUIRE:一个包含五百万张自然世界图像,涵盖10,000个不同物种的专为专家级文本到图像检索任务设计的新型基准数据集。

2024-11-05 &#xff0c;由麻省理工学院、伦敦大学学院等联合创建了Inquire数据集&#xff0c;这是一个包含五百万自然世界图像的文本到图像检索基准测试&#xff0c;目的是挑战多模态视觉-语言模型在专家级查询上的表现。这个数据集的创建&#xff0c;不仅填补了现有数据集在专…

DevOps工程技术价值流:加速业务价值流的落地实践与深度赋能

DevOps的兴起&#xff0c;得益于敏捷软件开发的普及与IT基础设施代码化管理的革新。敏捷宣言虽已解决了研发流程中的诸多挑战&#xff0c;但代码开发仅是漫长价值链的一环&#xff0c;开发前后的诸多问题仍亟待解决。与此同时&#xff0c;虚拟化和云计算技术的飞跃&#xff0c;…

4.4 软件设计:UML顺序图

UML顺序图 1、 UML2、 UML顺序图2.1 顺序图组成对象生命线消息 2.2 顺序图和用例登录用例 2.3 顺序图建模顺序图建模参考策略建立顺序图的步骤建立顺序图的示例 3、面对对象的设计原则3.1 特点3.2 层次3.3 注意点类设计需要强内聚&#xff0c;弱耦合可重用性框架 1、 UML 统一…

除了 Mock.js,前端还有更方便的 Mock 数据工具吗?

在前端开发中&#xff0c;模拟数据&#xff08;Mock Data&#xff09;是不可或缺的一部分&#xff0c;它能够帮助开发者在后端接口未完成前进行界面和逻辑的测试。而 Mock.js 是一个广泛使用的库&#xff0c;它通过简洁的语法和强大的功能&#xff0c;让前端开发者可以轻松地创…

继承和多态(上)

目录 一.继承 1.何为继承 2.继承的语法 3.子类访问父类 (1)子类访问父类的成员变量 (2)子类访问的父类方法 二.super关键字 1.super用于调用父类的构造方法 2.super用于调用父类的实例方法 3.super用于访问父类的实例变量 三.子父类构造方法 和代码块的执行优先顺序…

【练习案例】30个 CSS Javascript 加载器动画效果

本文分享一些 Loader CSS、Javascript 示例&#xff0c;这些示例均来源于Codepen网站上&#xff0c;里面有案例的源码与显示效果&#xff0c;您可以用于练习&#xff0c;也可以将您认为有趣的动画&#xff0c;添加到您的项目中&#xff0c;以帮助您创建更加有趣的等待页面加载动…

45.第二阶段x86游戏实战2-hook监控实时抓取游戏lua

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 本次游戏没法给 内容参考于&#xff1a;微尘网络安全 本人写的内容纯属胡编乱造&#xff0c;全都是合成造假&#xff0c;仅仅只是为了娱乐&#xff0c;请不要…

限流算法(令牌通漏桶计数器)

限流算法&#xff08;令牌桶&漏桶&计数器 &#xff09; 什么是限流&#xff1f; 限流是为保护自身系统和下游系统不被高并发流量冲垮&#xff0c;导致系统雪崩等问题 限流在很多场景中用来限制并发请求量&#xff0c;比如说秒杀抢购、双11高并发流量等 在保证系统可…

❤React-React 组件基础(类组件)

❤React-React 组件基础 1、组件化开发介绍 组件化开发思想&#xff1a;分而治之 React的组件按照不同的方式可以分成类组件&#xff1a; 划分方式一&#xff08;按照组件的定义方式&#xff09; 函数组件(Functional Component )和类组件(Class Component)&#xff1b; …

2024/11/13 英语每日一段

The new policy has drawn many critics. Data and privacy experts said the Metropolitan Transit Authority’s new initiative doesn’t address the underlying problem that causes fare evasion, which is related to poverty and access. Instead, the program tries “…

MySQL重难点(一)索引

目录 一、引子&#xff1a;MySQL与磁盘间的交互基本单元&#xff1a;Page 1、重要问题&#xff1a;为什么 MySQL 每次与磁盘交互&#xff0c;都要以 16KB 为基本单元&#xff1f;为什么不用多少加载多少&#xff1f; 2、有关MySQL的一些共识 3、如何管理 Page 3.1 单个 P…

【软件工程】一篇入门UML建模图(类图)

&#x1f308; 个人主页&#xff1a;十二月的猫-CSDN博客 &#x1f525; 系列专栏&#xff1a; &#x1f3c0;软件开发必练内功_十二月的猫的博客-CSDN博客 &#x1f4aa;&#x1f3fb; 十二月的寒冬阻挡不了春天的脚步&#xff0c;十二点的黑夜遮蔽不住黎明的曙光 目录 1. 前…

vue2+ element ui 集成pdfjs-dist

目录 1. 下载Pdf.js1.1 下载1.2 修改配置1.2.1 将pdfjs-3.8.162-dist复制到项目中1.2.2 解决跨域问题1.2.3 将pdf.worker.js文件复制到public目录下1.2.4 安装 pdfjs-dist1.2.5 前端vue代码(示例) 3. 参考资料 1. 下载Pdf.js 1.1 下载 下载链接&#xff08;官方&#xff09;需…

蓝桥杯每日真题 - 第7天

题目&#xff1a;&#xff08;爬山&#xff09; 题目描述&#xff08;X届 C&C B组X题&#xff09; 解题思路&#xff1a; 前缀和构造&#xff1a;为了高效地计算子数组的和&#xff0c;我们可以先构造前缀和数组 a&#xff0c;其中 a[i] 表示从第 1 个元素到第 i 个元素的…

大语言模型:解锁自然语言处理的无限可能

0.引言 在当今的科技时代&#xff0c;自然语言处理技术正以前所未有的速度发展&#xff0c;语言大模型作为其中的核心力量&#xff0c;对各个领域产生了深远的影响。本文旨在探讨语言大模型的发展历程、核心技术以及广泛的应用场景&#xff0c;以帮助读者更好地理解这一前沿技…

【vue2.0入门】vue基本语法

目录 引言一、页面动态插值1. 一般用法 二、计算属性computed三、动态class、style绑定四、条件渲染与列表渲染五、事件处理六、表单输入绑定七、总结 引言 本系列教程旨在帮助一些零基础的玩家快速上手前端开发。基于我自学的经验会删减部分使用频率不高的内容&#xff0c;并不…