【C语言】快速排序
文章目录
- 一、hoare版本
- 二、挖坑法
- 三、前后指针法
- 四、非递归快排
- 五、快速排序优化
- 1、三数取中选key值
- 2、小区间优化
- 六、代码测试

一、hoare版本
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
算法思想:
- 定义一个keyi存入随机一个数key的下标换到数组首元素,这里先直接默认key为数组首元素
- 定义一个left和一个right,分别存入数组首元素和尾元素的下标,用来移动交换
- 排升序我们让右边right先向左移动,找到比key的值小的元素则停下来换到left移动
- left向右移动,找到比key的值大的元素则停下
- 交换下标为left和right的元素
- 重复以上操作直到left与right相遇(相等)
- 交换key和下标为left的元素
- 此时key的左边都是比它小的数,右边都是比它大的数
- 再分别对左右序列进行以上的单趟排序,反复操作直到左右序列只有一个或者没有元素时停止操作,数列即可有序
hoare版本单趟排序图示:
hoare版本代码:
//交换
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
//hoare版本
void QuickSort1(int* a, int begin, int end)
{//递归结束条件if (begin >= end){return;}int keyi = begin;int left = begin;int right = end;//每趟排序直到左右相遇while (left < right){//右边先走,找到比key值小的while (left < right && a[right] >= a[keyi]){right--;}//right找到比key值小的之后换到left走,找到比key值大的while (left < right && a[left] <= a[keyi]){left++;}//交换Swap(&a[left], &a[right]);}//将key值换到中间Swap(&a[keyi], &a[left]);//更新keykeyi = left;//对左右序列继续排序QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi + 1, end);
}
整体流程图:
二、挖坑法
挖坑法思想:
- 先将第一个数据存在变量key中,将此处作为最开始的坑位,用下标hole记录
- 然后right开始向前走,找到比key值小的元素后停下,将此元素放进坑里(下标为hole处),然后此处变为坑,hole变为此时的right
- 然后left开始向后移动,找到比key值大的元素后停下,将此元素放进坑里(下标为hole处),然后此处变为坑,hole变为此时的left
- 然后又换回right移动,如此反复直到left与right相遇(left与right相遇的地方一定是坑)
- 然后将key放入left与right相遇的位置,也就是坑的位置,此时hole左边都是小于等于它的,右边都是大于等于它的
- 如此单趟排序便结束,然后继续对hole左右序列继续反复执行以上操作,直到左右序列只有一个或者没有元素时停止操作,数列即可有序
挖坑法单趟排序图示:
挖坑法代码:
//挖坑法
void QuickSort2(int* a, int begin, int end)
{//递归结束条件if (begin >= end){return;}int left = begin;int right = end;int key = a[left];//坑最初与left一样在开始位置int hole = left;//每趟排序直到左右相遇while (left < right){//右边先走,找到比key值小的while (left < right && a[right] >= key){right--;}//将right找到的比key小的元素放进坑中a[hole] = a[right];//更新坑的位置hole = right;//然后左边走找到比key值大的元素停下来while (left < right && a[left] <= key){left++;}//将left找到的比key大的元素放进坑中a[hole] = a[left];//更新坑的位置hole = left;}//将key放入坑中a[hole] = key;//对左右序列继续排序QuickSort2(a, begin, hole - 1);QuickSort2(a, hole+1, end);
}
三、前后指针法
前后指针法思想:
- 定义一个keyi存入随机一个数key的下标换到数组首元素,这里先直接默认key为数组首元素
- 定义一个prev为开头元素的下标,定义一个cur为prev下一个元素的下标
- cur下标处的值与key比较,直到cur找到比key小的值则停下来
- prev下标后移一位然后与cur下标处的值交换,然后cur后移一位(prev相当于前面比key小的那些数的最后一个的下标,所以要先后移一位再交换)
- cur继续寻找比key小的值,反复执行直到cur的值大于n
- 将key与prev下标处的值交换,此时key左边都是小于等于它的,右边都是大于等于它的
- 如此单趟排序便结束,然后继续对key左右序列继续反复执行以上操作,直到左右序列只有一个或者没有元素时停止操作,数列即可有序
前后指针法单趟排序图示:
前后指针法代码:
//交换
void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
//前后指针
void QuickSort3(int* a, int begin, int end)
{//递归结束条件if (begin >= end){return;}int keyi = begin;int prev = begin;int cur = begin + 1;//每趟排序直到cur下标大于endwhile (cur <= end){//cur找比key小的值if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[cur], &a[prev]);}cur++;}//将key换到中间Swap(&a[keyi], &a[prev]);//更新key的下标keyi = prev;//对左右序列继续排序QuickSort3(a, begin, keyi - 1);QuickSort3(a, keyi + 1, end);
}
快速排序是一种不稳定的排序,它的时间复杂度为O(N*logN),但最坏可以达到O(N2) ,它的空间复杂度为O(logN)
四、非递归快排
以上三种方法都是采用了分治法递归实现的快排,其实快速排序也可以非递归实现,非递归实现快排需要利用栈来实现
思路:
将数组首尾下标存入栈中,在循环中依次取出作为left和right对数组进行排序,然后对得到的key的左右两边序列也进行相同的操作,其中左边为left到keyi-1,右边为keyi+1到right,这些下标的入栈顺序需要看取出的顺序,如下面代码中是先取出后面元素下标的,所以入栈时要先入后面的,因为栈的特点是先入后出。
非递归快排代码:
(该代码中用到的栈需自己实现,C语言实现栈可参考:栈的实现)
//非递归快速排序
void QuickSortNonR(int* a, int begin, int end)
{//创建一个栈ST st;//初始化栈STInit(&st);//插入尾元素下标STPush(&st, end);//插入首元素下标STPush(&st, begin);//栈为空停下while (!STEmpty(&st)){//取出栈顶元素作为leftint left = STTop(&st);//取出后在栈中删除STPop(&st);//取出栈顶元素作为rightint right = STTop(&st);//取出后在栈中删除STPop(&st);int keyi = begin;//每趟排序直到左右相遇while (left < right){//右边先走,找到比key值小的while (left < right && a[right] >= a[keyi]){right--;}//right找到比key值小的之后换到left走,找到比key值大的while (left < right && a[left] <= a[keyi]){left++;}//交换Swap(&a[left], &a[right]);}//将key值换到中间Swap(&a[keyi], &a[left]);//更新key的下标keyi = left;// 当前数组下标样子 [left,keyi-1] keyi [keyi+1, right]//右边还有元素,按顺序插入right和keyi+1if (keyi + 1 < right){STPush(&st, right);STPush(&st, keyi + 1);}//左边还有元素,按顺序插入keyi-1和leftif (left < keyi - 1){STPush(&st, keyi - 1);STPush(&st, left);}}STDestroy(&st);
}
五、快速排序优化
1、三数取中选key值
前面三种快速排序的方法起初都要随机选取一个值作为key,我们之前是直接默认为数组首元素的,这样不够随机,容易出现最坏的情况,使得它的时间复杂度接近O(N2),所以我们可以写一个函数来选取这个key,使得它比较随机,而不是直接为首元素。
三数取中:
在一个数组最前面、最后面,中间这三个位置的数中选出大小处于中间的数
// 三数取中
int GetMidi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] > a[right]){if (a[right] > a[mid]){return right;}else if(a[mid]>a[right]&&a[mid]<a[left]){return mid;}else{return left;}}else{if (a[left] > a[mid]){return left;}else if (a[mid] > a[left] && a[mid] < a[right]){return mid;}else{return right;}}
}
在快排时用三数取中法选取key值再将它换到数组开头,可以有效避免出现最坏的情况,大大提升算法效率
2、小区间优化
当递归到数据较小时可以使用插入排序,使得小区间不再递归分割,降低递归次数
六、代码测试
//打印数组
void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void TestQuickSort1()
{int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };QuickSort1(a, 0, sizeof(a) / sizeof(int) - 1);printf("hoare版本快速排序:\n");PrintArray(a, sizeof(a) / sizeof(int));
}
void TestQuickSort2()
{int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };QuickSort2(a, 0, sizeof(a) / sizeof(int) - 1);printf("挖坑法快速排序:\n");PrintArray(a, sizeof(a) / sizeof(int));
}
void TestQuickSort3()
{int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };QuickSort3(a, 0, sizeof(a) / sizeof(int) - 1);printf("前后指针法快速排序:\n");PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{TestQuickSort1();TestQuickSort2();TestQuickSort3();return 0;
}
相关文章:

【C语言】快速排序
文章目录 一、hoare版本二、挖坑法三、前后指针法四、非递归快排五、快速排序优化1、三数取中选key值2、小区间优化 六、代码测试 一、hoare版本 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素…...

Java列表查询Long(id)到前端转换出错
Java列表查询Long到前端转换出错 问题描述排查思路思路一:SQL问题思路二:Long类型转换出错 解决方法 问题描述 做了一个列表查询功能,本来不应该有啥大问题的,但是往往事与愿违。 诶,你越觉得不可能出问题,…...

react import爆红
如上所示,会标红, 解决办法:在vscode内部SHiftCtrlP 输入Reload window, 如上的第一个,选中后回车,标红就没了,非常好用。...

ThreeJS-3D教学三:平移缩放+物体沿轨迹运动
我们在项目中会有一些这样的需求,我们可视化一个场景,需要俯视、平移、缩放,方便观察场景中的数据或者模型,之所以把这个案例拿出来 1、这是个很实用的需求,我相信很多人会用到 2、我自己认为在实际案例中我们可以学习…...

玩玩“小藤”开发者套件 Atlas 200I DK A2 之VSCode远程连接
玩玩“小藤”开发者套件 Atlas 200I DK A2 之VSCode远程连接 0. 背景1. VSCode 安装 Remote - SSH 插件2. 安装 OpenSSH 组件3. VSCode SSH 连接 Atlas 200I DK A24. 打开远程文件夹 0. 背景 总所周知,英伟达的GPU供不应求,还各种限制。华为推出了升腾A…...
安装python中tensorflow和keras==2.2.0的路程
1.python中安装Keras2.3.0 你可以使用pip来安装特定版本的Keras。在命令行中运行以下命令: pip install keras2.3.0这将会下载并安装Keras的2.3.0版本及其相应的依赖项。请确保你的Python环境已经配置好,并且有足够的权限来安装软件包。2.python 中安装…...
Linux命令历史记录管理:使用history命令提高工作效率
文章目录 引言1.1 关于history命令1.2 history命令的作用和用途 基本用法2.1 查看历史命令列表2.2 执行历史命令2.3 使用历史命令编号 历史命令记录和保存3.1 历史命令的存储位置3.2 修改历史命令记录数量3.3 清除历史命令记录 搜索历史命令4.1 使用关键字搜索4.2 按日期和时间…...
Armv9 Cortex-A720的L1 memory system 和 L1 Cache
思考: L1 System memory和L1 Cache是什么关系?L1指令cache禁用时,指令cache就真的不会缓存了吗?此时还会出现缓存不一致的情况吗?L1 data cache禁用时,L1 data cache就真的不会缓存了吗?此时还会出现缓存不一致的情况吗?在下电的时候,cache有什么自动的行为?有没有in…...

使用超声波清洗机洗眼镜有哪些注意事项、高颜值超声波清洗机推荐
眼镜,对于许多人来说,不仅仅是矫正视力的工具,更是日常生活的重要伴侣。但是,眼镜的清洁问题却常常让人感到困扰。镜片上的污渍、指纹、甚至小划痕,都让眼镜的使用体验大打折扣。幸运的是,随着科技的进步&a…...

23种设计模式汇总详解
设计原则 中文名称英文名称含义解释单一职责原则Single Responsibility Principle(SRP)任何一个软件模块都应该只对某一类行为者负责一个类只干一件事,实现类要单一开闭原则Open-Close Principle(OCP)软件实体(类、模块、函数等)应该是可以扩…...
stream流的filter和map过滤
详情页面 // 过滤出身高大于 170 的记录 personList.stream().filter((item)->item.getHeight() > 170).forEach(System.out::println);//从对象中提取age。并过滤年龄 List<Integer> nameListstudentList.stream().map(StudentInfo::getAge).filter(f->f>…...

Linux 环境下使用 Docker 部署 Seata 1.7.1 (图文教程)
目录 前言环境准备创建数据库安装 Seata下载镜像自定义配置文件自定义配置启动 Seata 开源项目微服务商城项目 前后端分离项目联系我 前言 本篇参考 Seata 官方部署文档 在 Linux 环境通过 Docker 部署 Seata 1.7.1 版本,以及为 youlai-mall 开源商城版本的升级做…...
Aruba CX交换机 VSF配置
目前 Aruba CX 交换机中的 6300F 和 6300M 支持 VSF 功能,要求同型号堆叠。 6300 交换机仅仅最后 4 个 SFP56 端口支持 VSF link 6200F : all uplink ports with 10G speed can be configured as VSF link 6200F: VSF allows stacks to be formed using any combin…...

使用ElementUI结合Vue完善主页的导航菜单和书籍管理以及后台数据分页查询
目录 动态树 数据表 案列 书籍管理 动态树 动态树(Dynamic tree)是一种数据结构,它可以在树中动态地插入、删除和修改节点。与静态树不同,静态树的节点是固定的,一旦构建完成就无法再进行修改。而动态树可以在运行时…...

子序列问题集合
子序列问题 删除一次得到的最大和最大子数组和最长公共子序列:最长上升子序列(要输出序列,和最大长度)1.dp2.贪心二分 导弹拦截 (最长上升/下降子序列长度) 删除一次得到的最大和 class Solution { public:…...

idea中提示:error has occurred, please check your installation and try again
目录 报错原因解决总结 报错 idea中提示:error has occurred, please check your installation and try again 原因 1.起初我是把一个运行正常的java程序,放到了src下,新建的一个包(包名为java.first)中,…...

MySQL - 关于约束类型和作用的介绍
约束的概念:约束是作用于表中字段上的规则,用于限制存储在表中的数据。 约束的作用:用于保证数据库中数据的正确性、完整性和一致性。 约束分类: 约束类型作用关键字非空约束限制该字段的数据不能为nullnot null唯一约束保证该…...

【2023集创赛】芯原杯一等奖作品:基于芯原DSP核的智能语音SoC设计
本文为2023年第七届全国大学生集成电路创新创业大赛(“集创赛”)芯原杯一等奖作品分享,参加极术社区的【有奖征集】分享你的2023集创赛作品,秀出作品风采,分享2023集创赛作品扩大影响力,更有丰富电子礼品等…...
代理IP与Socks5代理在跨界电商、爬虫、游戏和网络安全中的应用
在数字化时代,网络工程师们需要不断应对各种技术挑战,以满足跨界电商、爬虫、游戏和网络安全领域的需求。本文将聚焦于代理IP和Socks5代理,探讨它们在这些领域中的重要应用和影响。 1. 代理IP:跨越地域的电商战略 跨界电商已经成…...

DDS信号发生器Verilog波形发生器FPGA
名称:DDS信号发生器Verilog波形发生器 软件:Quartus 语言:Verilog 要求: 1.可产生正弦波,锯齿波,三角波,方波4种波形,频率可调 2.具有波形选择、起动、停止功能。 代码下载&…...

【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...

HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战
“🤖手搓TuyaAI语音指令 😍秒变表情包大师,让萌系Otto机器人🔥玩出智能新花样!开整!” 🤖 Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制(TuyaAI…...

多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
动态 Web 开发技术入门篇
一、HTTP 协议核心 1.1 HTTP 基础 协议全称 :HyperText Transfer Protocol(超文本传输协议) 默认端口 :HTTP 使用 80 端口,HTTPS 使用 443 端口。 请求方法 : GET :用于获取资源,…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...