排序算法 —— 快速排序（理论+代码）

目录

1.快速排序的思想

2.快速排序的实现

hoare版

挖坑法

前后指针法

快排代码汇总

3.快速排序的优化

三数取中

小区间优化

三路划分

4.快速排序的非递归版本

5.快速排序总结

1.快速排序的思想

快速排序是一种类似于二叉树结构的排序方法。其基本思想为从待排序序列中任取一个元素作为基准值，按照该基准值将待排序序列分割成两个子序列，左子序列中所有元素的值均小于基准值，右子序列中所有元素的值均大于基准值，左右子序列重复该过程，直到待排序序列有序。

2.快速排序的实现

前面说过，快速排序是一种类似于二叉树结构的排序方式，也就说明，快速排序可以通过递归来实现，从上面的图片可以看出，递归实现快速排序可以使用二叉树的前序遍历的方式。

于是，我们可以这样实现快速排序：

  • 说明一下，下面代码只是见一见快排的样子，还没有完全实现。
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]QuickSort2(a, begin, keyi - 1);QuickSort2(a, keyi + 1, end);
}
  • begin > end的时候，说明区间不存在；begin == end的时候，说明待排序序列中只有一个值；此时，都可以直接返回。
  • PartSort函数根据基准值完成左右子序列的划分，并将基准值存放在正确的位置上。
  • 然后递归左子序列，再递归右子序列，完成同样的功能。

那么，实现快速排序的重点就放在这个PartSort函数上面了，也就是如何根据基准值将区间划分成左右子区间。

基准值的选取一般为待排序区间的最左侧元素。

左右子区间的划分常见的有这三种方式：hoare版、挖坑法、前后指针法。

hoare版

hoare版步骤如下：

  1. 选取待排序序列的最左侧为基准值。
  2. 从右边开始找小于基准值的元素。
  3. 从左边找大于基准值的元素。
  4. 找到这两个元素之后，交换这两个元素的值。
  5. 当left和right相遇的时候，交换相遇位置和基准值所在位置的值，并返回基准值。

代码如下：

int PartSort1(int* a, int left, int right)
{// 选取待排序序列的最左侧为基准值 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]);}// 将left和right相遇位置的元素和基准值交换 Swap(&a[keyi], &a[left]);// 返回left和right相遇的位置 return left;
}

挖坑法

挖坑法步骤如下：

  1. 选取待排序序列最左侧的元素为基准值，保存基准值，此时基准值所在位置形成坑。
  2. 从右侧开始找小于基准值的元素，找到之后，将该值放入坑中，该位置形成新的坑。
  3. 从左侧找大于基准值的元素，找到之后，将该值放入坑中，该位置形参新的坑。
  4. 重复2、3过程，直到 left 和 right 相遇。
  5. 相遇之后， 将保存的基准值放入相遇位置，并返回相遇位置。

挖坑法代码如下：

int PartSort2(int* a, int left, int right)
{// 保存key值以后，左边形成第一个坑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;
}

前后指针法

前后指针法步骤如下：

  1. 选定最左侧元素为基准值并保存，将prev设置为left，cur设置为left+1。
  2. cur去寻找当前区间内比基准值小的元素
  3. 如果没找到，说明基准值右侧的元素都是大于基准值的，不需要其他操作，直接跳出循环即可。
  4. 如果找到了先++prev，再将prev和cur位置的元素交换，然后++cur。
  5. 等到cur越界之后，说明遍历完序列中的所有元素了，将基准值位置的元素和prev位置的元素交换。
  6. 最后返回prev即可。

前后指针法能够保证 left+1 ~ prev 的所有元素都是小于基准值的，prev+1 ~ right 的所有元素都是大于基准值的。

前后指针法代码如下：

// 前后指针法
int PartSort3(int* arr, int left, int right)
{int prev = left; int cur = prev+1;    // cur找小，找到小的就交换 int tmp = arr[left];while(cur <= right){// cur找到比基准值tmp小的元素or越界才停下来 while(cur <= right && arr[cur] >= tmp){cur++;}if(cur > right) // 找不到小的 {break;}else            // 找到小的 {prev++;swap(&arr[prev], &arr[cur]);cur++;}}	swap(&arr[left], &arr[prev]);return prev;
}

快排代码汇总

当我们实现了三个版本的划分左右子区间的代码之后，我们的快速排序就可以这样写了。

void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort1(a, begin, end);//int keyi = PartSort2(a, begin, end);//int keyi = PartSort3(a, begin, end);QuickSort2(a, begin, keyi - 1);QuickSort2(a, keyi + 1, end);
}

当我们想使用不同的划分区间的方法时，只需要放开对应的函数即可。

3.快速排序的优化

三数取中

在前面的代码中，我们都是选取待排序序列的最左侧元素为基准值，这种选取基准值的方法存在缺陷，比如：待排序的序列为有序or接近有序时，在这种情况下，我们每次选取最左侧元素为基准值之后，然后从右侧开始寻找小于基准值的元素，需要一直遍历到基准值的左侧，这个时候的时间复杂度就是O(N^2)了。所以，我们需要改变获取基准值的方式。

这个时候就有人提出三数取中，解决待排序序列为有序or接近有序的情况下，快排效率退化成O(N^2)的缺陷。

// 三数取中
int GetMidi(int* a, int left, int right)
{int mid = (left + right) / 2;// left mid rightif (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right])  // mid是最大值{return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]) // mid是最小{return left;}else{return right;}}
}

问题来了，那我们的快排代码是不是要重新写呢？这是不需要的，我们只需要修改即可，也就是在三个版本的划分左右子序列函数中最开始添加这两行代码即可。

int midi = GetMidi(a, left, right);
Swap(&a[left], &a[midi]);

以hoare版为例：

  • 三数取中指的是待排序序列最左侧元素、中间元素、最右侧元素三个元素取中间值。
  • 取到中间值之后，将中间值和最左侧元素交换，所以我们选取的还是最左侧元素为基准值，但是本质已经发生变化了。
int PartSort1(int* a, int left, int right)
{int midi = GetMidi(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]);}// 将left和right相遇位置的元素和基准值交换 Swap(&a[keyi], &a[left]);// 返回left和right相遇的位置 return left;
}

小区间优化

前面我们讨论过，递归版的快速排序是类似于二叉树结构的。快速排序的实现在理想情况下是一颗完全二叉树结构，完全二叉树有一个特点是最后一层的结点个数占了整棵树的一半左右，这就意味着，在最后一层我们需要进行的递归次数占了整个排序过程的一半左右。 

况且，经过前面的多次递归划分左右子序列并排序，待排序的序列已经变得比较有序了，这个时候我们可以考虑换一种排序方式。

我们都知道，插入排序在待排序序列为有序or接近有序的情况下，排序的时间复杂度为O(N)，所以，当待排序序列的区间比较小的时候，我们可以考虑使用插入排序，减少递归的次数。

void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;// 小区间优化，小区间不再递归分割排序，降低递归次数if ((end - begin + 1) > 20){int keyi = PartSort3(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi + 1, end);}else{InsertSort(a + begin, end - begin + 1);}
}

三路划分

上面，我们已经使用三数取中来解决了待排序序列在有序or接近有序的情况下时间复杂度退化成O(N^2)的问题；但是，三数取中还有一种不能解决的情况，就是待排序序列全部为重复一样的值or接近全部重复一样，在这种情况下，三数取中每次取出的值和原来待排序序列最左侧的值是一样的，或者说，不管用不用三数取中，每次取出的基准值都有非常大的概率和待排序序列最左侧元素相同。

在这种情况下，将一个待排序序列划分为左右子序列的时间复杂度为O(N)，并且在这种情况下right会一直减小到和left相遇，此时，划分出的左区间待排序元素个数为0，划分出的右区间待排序元素个数为 n-1，比上一层待排序序列个数减少一个，再次进行划分左右子序列的时候，依然会是上面这种情况。

  •  在这种情况下，我们可以计算出大概的基本操作的次数是一个等差数列，1+2+3+……+n == (1+n)*n / 2，使用大O表示法表示出来为O(N^2)。

针对这种情况，有人提出了三路划分来解决。

三路划分的步骤如下：

  • 选取待排序序列的最左侧为基准值，当然，我们可以使用三数取中来选取基准值。
  • L指向最左侧的元素，R指向最右侧的元素，C指向L的后一个元素。
  • 然后让C遍历待排序序列，此时会出现以下几种情况：
  1. C位置的值小于基准值，交换C和L位置的值，然后++C，++L。
  2. C位置的值等于基准值，++C。
  3. C位置的值大于基准值，交换C和R位置的值，然后--R。

举个例子：

  • 假如有n个元素，可以看出：[0，L-1]之间的元素都是小于基准值的，[L+1，R]之间的元素都是等于基准值的，[R+1，n-1] 之间的元素都是大于基准值的。

采用三路划分优化之后的代码如下：

void QuickSort(int *a, int left, int right)
{if(left >= right){return;}int begin = left;int end = right;//三数取中 int midi = GetMidi(a,left,right);swap(&a[left],&a[midi]);int cur = left+1;int key = a[left];//三路划分while(cur <= right){if(a[cur] < key){swap(&a[cur], &a[left]);++left;++cur;}else if(a[cur] > key){swap(&a[right], &a[cur]);right--; }else{++cur;}}// [begin, left-1][left,right][right+1,end] QuickSort(a,begin,left-1);QuickSort(a,right+1,end);
}

有了三路划分之后，面对全部重复元素的时候，遍历一次之后，划分不出左右子区间，排序自然就结束了，避免了大量无效判断。

4.快速排序的非递归版本

快排非递归步骤如下：

  1. 实现快速排序的非递归版本需要借助栈来实现，先将 end 和 begin 入栈，然后从栈中取两个元素，取出的分别是begin和end，也就是待排序区间。
  2. 排完之后，根据返回值划分左右子序列，左边的子序列区间为 left ~ keyi-1，右边的子序列区间为 keyi+1 ~ right。
  3. 然后先将右边的子序列的区间入栈，再将左边的子序列的区间入栈；入的时候先入区间的右边界，再入区间的左边界。
  4. 每次从栈中取出元素的时候，就能模拟递归的过程来实现快速排序。

快排非递归代码如下：

void QuickSortNonR(int* a, int begin, int end)
{ST st;STInit(&st);// 先入end再入begin，取的时候就是先取begin再取end。 STPush(&st, end);STPush(&st, begin);while (!STEmpty(&st)){int left = STTop(&st);STPop(&st);int right = STTop(&st);STPop(&st);int keyi = PartSort1(a, left, right);// [lefy,keyi-1] keyi [keyi+1, right]if (keyi+1 < right){STPush(&st, right);STPush(&st, keyi+1);}if (left < keyi-1){STPush(&st, keyi-1);STPush(&st, left);}}STDestroy(&st);
}

5.快速排序总结

  • 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序。
  • 时间复杂度：O(N*logN)。每一层遍历n次，最多logN层。

  • 空间复杂度：O(logN)。因为，每一层递归需要开辟栈区的空间，最多开辟logN层。
  • 稳定性：不稳定，如下图所示。

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

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

相关文章

【前端】如何制作一个自己的网页（15）

【前端】如何制作一个自己的网页（15）

有关后代选择器的具体解释&#xff1a; 后代选择器 后代选择器使用时&#xff0c;需要以空格将多个选择器间隔开。 比如&#xff0c;这里p span&#xff0c;表示只设置p元素内&#xff0c;span元素的样式。 <style> /* 使用后代选择器设置样式 */ p span { …
阅读更多...
给EXE添加网络验证激活码(卡密)

给EXE添加网络验证激活码(卡密)

介绍 网络验证可以理解为给EXE文件添加一个激活码, 用户在打开EXE文件时, 需要输入激活码, 输入后, 通过网络验证激活码, 如果激活码有效用户便可以继续使用软件. 网络验证可以生成静态激活码(也就是卡密), 再需要使用的时候直接发给用户即可, 无需像离线一机一码加密那样需要…
阅读更多...
漏洞挖掘 | 基于mssql数据库的sql注入

漏洞挖掘 | 基于mssql数据库的sql注入

前记 今天挖edu随意点开个站&#xff0c;发现存在mssql数据库的sql注入&#xff0c;在此分享下整个挖掘过程 目录 0x1 判断网站数据库类型 0x2 了解mssql数据库的主要三大系统表 0x3 了解mssql的主要函数 0x4 判断注入点及其注入类型 0x5 联合查询之判断列数 0x6 联合查询之…
阅读更多...
spring源码拓展点3之addBeanPostProcesser

spring源码拓展点3之addBeanPostProcesser

概述 在refresh方法中的prepareBeanFactory方法中&#xff0c;有一个拓展点&#xff1a;addBeanPostProcessor。即通过注入Aware对象从而将容器中的某些值设置到某个bean中。 beanFactory.addBeanPostProcessor(new ApplicationContextAwareProcessor(this));aware接口调用 …
阅读更多...
华为配置 之 Console线路配置

华为配置 之 Console线路配置

目录 简介&#xff1a; 知识点&#xff1a; 配置Console线路密码 1.密码认证模式 2.AAA认证模式 知识点&#xff1a; 总结&#xff1a; 简介&#xff1a; 使用PC模拟器与路由器相连&#xff08;与交换机相连原理一样&#xff09;&#xff0c;在关机状态下&#xff0c;使用…
阅读更多...
手机玩黑色沙漠？GameViewer远程玩黑色沙漠教程

手机玩黑色沙漠？GameViewer远程玩黑色沙漠教程

黑色沙漠的国服即将在10月24日迎来公测&#xff01;这是一款玩法多元的大型多人在线角色扮演游戏&#xff0c;你可以享受激烈的战斗&#xff0c;也可以感受惬意的生活&#xff0c;在这个游戏里你能体验到一个不一样的冒险故事。不管你是老玩家还是新玩家&#xff0c;只要你想玩…
阅读更多...
鸿蒙开发：实现一个超简单的网格拖拽

鸿蒙开发：实现一个超简单的网格拖拽

前言 网格拖拽&#xff0c;此功能很是常见&#xff0c;一般用于频道的编辑或者条目顺序的排列&#xff0c;在鸿蒙的开发中&#xff0c;针对网格的编辑&#xff0c;系统也给出了相关的Api&#xff0c;通过onItemDragStart和在onItemDrop即可轻松实现&#xff0c;onItemDragStart…
阅读更多...
Linux LVS详解

Linux LVS详解

LVS&#xff08;Linux Virtual Server&#xff09;即Linux虚拟服务器&#xff0c;是一个基于Linux操作系统的高性能、可扩展的负载均衡器。以下是对LVS的详细介绍&#xff1a; 一、简介 LVS项目由章文嵩博士在1998年5月发起&#xff0c;是中国国内最早出现的自由软件项目之一…
阅读更多...
Flutter Container容器组件实战案例

Flutter Container容器组件实战案例

The Container widget is your design toolkit. It’s like the master builder that helps you structure and style your UI elements with precision. Whether you’re creating simple designs or complex layouts, the Container is your trusty tool for the job. “容器…
阅读更多...
如何在算家云搭建GPT-SOVITS（语音转换）

如何在算家云搭建GPT-SOVITS（语音转换）

一、模型介绍 GPT-SOVITS是一款强大的小样本语音转换和文本转语音 WebUI工具。它集成了声音伴奏分离、自动训练集分割、中文ASR和文本标注等辅助工具。 具有以下特征&#xff1a; 零样本 TTS&#xff1a; 输入 5 秒的声音样本并体验即时文本到语音的转换。少量样本 TTS&…
阅读更多...
ESC服务器被暴力破解如何解决

ESC服务器被暴力破解如何解决

使用fail2ban解决 黑客怎么暴力破解的?安装教程一些命令 黑客怎么暴力破解的? 他们一般是用脚本扫描公网上的ip地址, 一个个ping, 如果ping通了, 就开始以这个公网ip尝试连接服务器, 比如使用ssh, 接下来就输入密码了, 暴力破解他们一般都有密码表的, 一个个试, 密码简单很容…
阅读更多...
【赵渝强老师】Oracle的参数文件与告警日志文件

【赵渝强老师】Oracle的参数文件与告警日志文件

一、Oracle的参数文件 在Oracle数据库中&#xff0c;参数文件在通常情况下指的就是初始化参数文件&#xff08;Initialization Parameter File)。在参数文件中包括了初始化参数文件和服务器端参数文件。在Oracle数据库启动的时候就会读取参数文件&#xff0c;然后根据参数文件…
阅读更多...
C++ 进阶：类相关特性的深入探讨

C++ 进阶：类相关特性的深入探讨

⭐在对C 中类的6个默认成员函数有了初步了解之后&#xff0c;现在我们进行对类相关特性的深入探讨&#xff01; &#x1f525;&#x1f525;&#x1f525;【C】类的默认成员函数&#xff1a;深入剖析与应用&#xff08;上&#xff09; 【C】类的默认成员函数&#xff1a;深入剖…
阅读更多...
python实战项目46：selenium爬取百度新闻

python实战项目46：selenium爬取百度新闻

python实战项目46：selenium爬取百度新闻 一、项目简介二、完整代码一、项目简介 思路是首先使用selenium打开百度新闻页面，然后实现翻页操作，获取每条新闻的标题和链接。接下来的问题是，在遍历标题和链接，对每一个链接发送请求时，发现会弹出百度安全验证，本文的思路是使…
阅读更多...
浪潮云启操作系统（InLinux）bcache缓存实践：理解OpenStack环境下虚拟机卷、Ceph OSD、bcache设备之间的映射关系

浪潮云启操作系统（InLinux）bcache缓存实践：理解OpenStack环境下虚拟机卷、Ceph OSD、bcache设备之间的映射关系

前言 在OpenStack平台上&#xff0c;采用bcache加速ceph分布式存储的方案被广泛用于企业和云环境。一方面&#xff0c;Ceph作为分布式存储系统&#xff0c;与虚拟机存储卷紧密结合&#xff0c;可以提供高可用和高性能的存储服务。另一方面&#xff0c;bcache作为混合存储方案&…
阅读更多...
新版idea菜单栏展开与合并

新版idea菜单栏展开与合并

新版idea把菜单栏合并了看着很是不习惯&#xff0c;找了半天原来在这里展开 ① 点击文件 -> 设置 ② 点击外观与行为 -> 外观 -> 合并主菜单和窗口标题 然后确定&#xff0c;重启即可
阅读更多...
HTML作业

HTML作业

作业 复现下面的图片 复现结果 代码 <!DOCTYPE html> <html><head><meta charset"utf-8"><title></title></head><body><form action"#"method"get"enctype"text/plain"><…
阅读更多...
演示：基于WPF的DrawingVisual开发的高刷新率示波器

演示：基于WPF的DrawingVisual开发的高刷新率示波器

一、目的&#xff1a;分享一个基于WPF的DrawingVisual开发的高刷新率示波器 二、效果演示 特此说明&#xff1a;由于Gif录制工具帧率不够&#xff0c;渲染60帧用了4.6秒&#xff0c;平均帧率在12Hz左右&#xff0c;所以展示效果不好&#xff0c;想要看好些的效果可以看文章下面…
阅读更多...
【目标检测2024】DetCLIP

【目标检测2024】DetCLIP

算法介绍 CLIP&#xff08;Contrastive Language-Image Pre-Training&#xff09;模型是一种多模态预训练神经网络&#xff0c;由OpenAI在2021年发布&#xff0c;是从自然语言监督中学习的一种有效且可扩展的方法。CLIP在预训练期间学习执行广泛的任务&#xff0c;包括OCR&…
阅读更多...
DORA 机器人中间件学习教程（6）——激光点云预处理

DORA 机器人中间件学习教程（6）——激光点云预处理

文章目录 1 移植思路2 代码输入输出说明3 编写CmakeList.txt文件4 编写yml文件5 编译并启动节点参考资料 在DORA中通过驱动获取激光雷达数据后&#xff0c;激光点云预处理部分代码是参考了autoware官方代码并对其进行裁剪得到的&#xff0c;点云预处理主要包含三个节点&#xf…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023