C语言实现多种快速排序

目录

1.概念

2.快速排序hoare版本

2.1基本思想

2.2解释相遇处的值为何一定小于key 

2.3hoare版本快速排序的实现

3.快速排序挖坑法 

3.1基本思想

3.2挖坑法快速排序的实现

4. 快速排序前后指针版本

4.1基本思想

4.2快速排序前后指针版本实现 

 5.快速排序非递归版本

5.1基本思想

5.2快速排序非递归版本实现

6.快速排序的优化

6.1三数取中

6.1.2三数取中代码实现

6.2小区间优化

6.3优化后的代码

7.快速排序的特性总结


1.概念

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

        接下来介绍三种最基本的快速排序版本、非递归版本以及两种对快速排序的优化。

2.快速排序hoare版本

2.1基本思想

        选择最左边的元素作为key,用一个left指针指向最左边,用一个right指针指向最右边。right从最右边开始往左边走,找到比key小的元素保持不动,left从最左边开始往右边走,找到比key大的元素保持不动,然后交换left和right指向的元素,再重复上述过程,直到left和right相遇,将相遇处(相遇处的值一定小于key)的值和key交换,这样就可以将小于key的值放到左边,大于key的值放到右边,然后左右子序列重复该过程,直到所以元素都排列在相应位置上为止。

2.2解释相遇处的值为何一定小于key 

        left和right相遇只有两种情况:(1)left遇上right。(2)right遇上left。

情况1:left遇上right

        如果是该情况,表面right是保持不动的,就说明right现在找到的这个元素是小于key的,然后当left遇到right时,则是将right指向的这个元素和key交换。

情况2:right遇上left

        如果是right遇上left,是right在走动,left已经在上一轮完成了交换,现在的left指向的元素,是上一轮right找到的小于key的元素,当right遇上left时,则是将right指向的这个小于key的元素和key交换。

        注:如果确定左边的值为key,一定要从右边先开始找,不然就会出错。

2.3hoare版本快速排序的实现

void QuickSort1(int* a, int left, int right)
{if (left >= right){return;}//单趟int begin = left; int end = right;int keyi = left;while (begin < end){while (begin < end && a[end] >= a[keyi])    //=防止找到与key相同的值进入死循环{end--;}while (begin < end && a[begin] <= a[keyi]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[end]);keyi = end;//[left, keyi - 1] keyi [keyi + 1, right]QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi + 1, right);
}

3.快速排序挖坑法 

3.1基本思想

        选择最左边的元素作为key,用一个临时变量tmp将key存储起来,用一个left指针指向最左边,用一个right指针指向最右边。right从右往左走找到小于key的值将它放到left处,然后left从左往右走找到大于key的值将它放到right处。重复上述过程,直到left和right相遇,将tmp中保存的key值放到相遇处。然后左右子序列重复上述过程,直到全部元素排好序为止。

        该方法就很自然的在左边挖坑,从右边开始走,不用考虑选择key值从哪边开始走的问题。

3.2挖坑法快速排序的实现

void QuickSort2(int* a, int left, int right)
{if (left >= right){return;}int keyi = left;int tmp = a[keyi];int begin = left;int end = right;while (begin < end){if (begin < end && a[end] >= tmp){end--;}a[begin] = a[end];if (begin < end && a[begin] <= tmp){begin++;}a[end] = a[begin];}a[begin] = tmp;keyi = begin;QuickSort2(a, left, keyi - 1);QuickSort2(a, keyi + 1, right);
}

4. 快速排序前后指针版本

4.1基本思想

4.2快速排序前后指针版本实现 

void QuickSort3(int* a, int left, int right)
{if (left >= right){return;}//cur指针找小,找到小于key的,++prev,然后交换int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)	//判断条件的后半部分是防止自身进行交换{Swap(&a[prev], &a[cur]);}cur++;	//交换完cur++,a[cur] >= a[keyi] cur也要++,故写在外面合成一句}Swap(&a[prev], &a[keyi]);keyi = prev;QuickSort3(a, left, keyi - 1);QuickSort3(a, keyi + 1, right);
}

 5.快速排序非递归版本

5.1基本思想

        为什么要实现快速排序的非递归版本,是因为有时可能递归深度太深,会造成栈溢出的风险,用非递归的方式可以有效的避免该风险。在这里我们用栈的方式来实现快速排序的非递归版本。

        对于递归版本来说,如何能够确定递归子序列的范围,是用子序列的left指针和right指针来确定的,所以对于非递归版本,只要我们能确定子序列的left和right就能确定需要进行递归的子序列范围。所以我们用栈来存储子序列的left和right指针。

        首先,将原数组中left和right存入栈中,然后取出,再依次将右子序列的right,left和左子序列的right和left存入栈中,重复上述操作,对每个子序列进行排序,当栈为空时,结束排序,则此时的数组已被排好序了。

        该方法中使用到栈的接口可以参考C语言实现栈。

5.2快速排序非递归版本实现

        因为非递归版本内部实现的逻辑和递归版本是一样的,不同的只是用栈来存储区间,所以在这我将内部的逻辑写成一个子函数的形式。

        该代码是hoare版本的子函数形式,返回值为上一次单趟之后的keyi。

int PartSort1(int* a, int left, int right)
{int keyi = left;int begin = left;int end = right;while (begin < end){//右边找小while (begin < end && a[end] >= a[keyi])	//加等于方式找到与key相同的数进入死循环{end--;}//左边找大while (begin < end && a[begin] <= a[keyi]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[end], &a[keyi]);return begin;
}
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!(STEmpty(&st))){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = PartSort1(a, begin, end);if (keyi + 1 < end) //区间里的值大于1个{STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}

6.快速排序的优化

6.1三数取中

        当key值每次都为数组中的最大值或者最小值的话,则要递归n次,快速排数的时间复杂度就会退化为O(N^2)。为了避免取到的key为最大值或者最小值,对取key进行了一个优化,取数组中left,right以及中间mid指向的元素中,三个元素大小为中间的那个元素,与left交换。

6.1.2三数取中代码实现

//三数取中
int GetMidi(int* a, int left, int right)
{int midi = (left + right) / 2;if (a[midi] > a[left]){if (a[midi] < a[right]){return midi;}else{if (a[left] > a[right]){return left;}else{return right;}}}else{if (a[midi] > a[right]){return midi;}else{if (a[right] < a[left]){return right;}else{return left;}}}
}

6.2小区间优化

         对于快速排序的递归来说,当在递归到最后一层时,递归的次数是整个递归的一般,递归创建栈帧和销毁栈帧也会有一定的消耗,并且在元素少的时候,时间复杂度为O(NlogN)的快速排序算法和时间复杂度为O(N^2)的插入排序的消耗差不多,所以在小区间的时候,我们选择用插入排序来代替快速排序,以此来减少递归栈帧的创建和销毁,提高程序性能。

	if ((right - left + 1) < 20){InsertSort(a + left, right - left + 1);}

        上述代码表示,区间元素的个数小于20个时,采用插入排序进行排序。

6.3优化后的代码

        首先,我先把上述介绍的三种快速排序的版本写成子程序的版本:

// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{//三数取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int begin = left;int end = right;while (begin < end){//右边找小while (begin < end && a[end] >= a[keyi])	//加等于方式找到与key相同的数进入死循环{end--;}//左边找大while (begin < end && a[begin] <= a[keyi]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[end], &a[keyi]);return begin;
}
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{//三数取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int tmp = a[keyi];int begin = left;int end = right;while (begin < end){if (begin < end && a[end] >= tmp){end--;}a[begin] = a[end];if (begin < end && a[begin] <= tmp){begin++;}a[end] = a[begin];}a[begin] = tmp;return begin;
}
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{//三数取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);//cur指针找小,找到小于key的,++prev,然后交换int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur) //判断条件的后半部分是防止自身进行交换{Swap(&a[prev], &a[cur]);}++cur; //交换完cur++,a[cur] >= a[keyi] cur也要++,故写在外面合成一句}Swap(&a[prev], &a[keyi]);return prev;
}

        然后写一个快速排序的程序来调用上述三个版本并加上优化:

void QuickSort(int* a, int left, int right)
{if (left >= right) //一个值的区间和不存在的区间都是结束条件{return;}//小区间优化if ((right - left + 1) < 20){InsertSort(a + left, right - left + 1);}else{int keyi = PartSort1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}
}

        如果要修改调用的子程序,将PartSort1修改为PartSort2或者PartSort3即可。

优化后的性能比较:

7.快速排序的特性总结

(1)  快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫 快速 排序
(2)  时间复杂度: O(N*logN).
(3). 空间复杂度: O(logN).
(4). 稳定性:不稳定.

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

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

相关文章

苹果笔记本电脑可以玩steam游戏吗 MacBook支持玩steam游戏吗 在Steam上玩黑神话悟空3A大作 苹果Mac怎么下载steam

游戏是生活的润滑剂&#xff0c;越来越多的用户开始关注Mac平台上可玩的游戏。幸运的是&#xff0c;Steam作为最大的数字发行平台之一&#xff0c;提供了大量适用于Mac操作系统的游戏。无论你是喜欢策略、冒险还是射击类游戏&#xff0c;都能在Steam上找到适合自己Mac设备玩耍的…

从0开始搭建vue + flask 旅游景点数据分析系统(九):旅游景点管理之增删改查

这一期来做旅游景点数据的增删改查 先看下我们做好的效果是这样的&#xff1a; ## 1 后台接口 这里的接口已经考虑到了分页的情况&#xff0c;因为前端的表格是带有分页的&#xff0c;接受的前端传过来的get参数为 title 、page、 limit &#xff0c;titie是查询的关键词&…

Matlab绘制像素风字母颜色及透明度随机变化动画

本文是使用 Matlab 绘制像素风字母颜色及透明度随机变化动画的教程 实现效果 实现代码 如果需要更改为其他字母组合&#xff0c;在下面代码的基础上简单修改就可以使用。 步骤&#xff1a;(1) 定义字母形状&#xff1b;(2) 给出字母组合顺序&#xff1b;(3) 重新运行程序&#…

iPhone 16 机模视频曝光,五种颜色各有千秋

科技博主的最新视频分享了苹果 iPhone 16 标准版的机模上手体验。 视频中展示了五种颜色的 iPhone 16&#xff1a;深邃的蓝色、柔和的粉色、纯净的白色、经典的黑色和生机勃勃的绿色。 与 iPhone 15 相比&#xff0c;iPhone 16 弃用了黄色&#xff0c;新增了白色&#xff0c;…

地质灾害评估和治理工程勘查设计资质乙级资质办理标准

地质灾害评估和治理工程勘查设计资质乙级资质的办理标准主要包括单位条件、专业技术人员条件、仪器设备要求以及申请材料等方面。以下是详细的办理标准&#xff1a; 一、单位条件 **1、法人资格&#xff1a;**申请单位应具有企业法人或者事业单位法人资格。 **2、管理体系&a…

奥运内容碎片化传播下,品牌营销开始要讲究“性价比”

8月12日凌晨&#xff0c;随着孙颖莎和其他代表各洲的运动员们一起熄灭了圣火&#xff0c;巴黎奥运会终于落下帷幕。 本届奥运会上&#xff0c;中国体育代表团表现出色&#xff0c;共获得40枚金牌&#xff0c;金牌总数位居全球榜首&#xff0c;创下了中国在境外奥运会上的最佳成…

人工智能领域颠覆性技术创新,数字人泛化AI时代来临

是先有鸡还是先有蛋&#xff0c;这个问题人类还没有搞清楚&#xff0c;这次又有一个新的问题产生了&#xff0c;是算法进化了AI&#xff0c;还是AI进化了算法。我们知道直播平台都是利用算法对数字人直播进行斟别&#xff0c;但这一次被数字人泛化技术颠覆了&#xff0c;AI回复…

报错解决——苹果电脑mac装windows10,总是提示“启动转换”安装失败:拷贝Windows安装文件时出错

报错原因&#xff1a; 所安装的镜像文件大于4GB。 解决办法一&#xff1a; 使用小于4GB的镜像文件。 参考文章&#xff1a; 安装小于4GB的windows系统镜像 小于4GB的windows10镜像下载&#xff1a; 系统库官网 解决办法二&#xff1a; 参考文章&#xff1a; Mac air装…

VS实用调试技巧(程序员的必备技能)

调试的重要性 在我们写代码的时候&#xff0c;如果程序出现了bug&#xff0c;那么下一步就是找到bug并修复bug!而这个找问题的过程就被称为调试&#xff08;英文叫debug&#xff0c;消灭bug的意思&#xff09;。 调试能观察到程序内部执行的细节&#xff0c;可以增加程序员对…

Kafka系列之:Kafka Connect深入探讨 - 错误处理和死信队列

Kafka系列之&#xff1a;Kafka Connect深入探讨 - 错误处理和死信队列 一、快速失败二、YOLO&#xff1a;默默忽略坏消息三、如果一条消息掉在树林里&#xff0c;会发出声音吗&#xff1f;四、将消息路由到死信队列五、记录消息失败原因&#xff1a;消息头六、记录消息失败原因…

什么是数据仓库ODS层?为什么需要ODS层?

在大数据时代&#xff0c;数据仓库的重要性不言而喻。它不仅是企业数据存储与管理的核心&#xff0c;更是数据分析与决策支持的重要基础。而在数据仓库的各个层次中&#xff0c;ODS层&#xff08;Operational Data Store&#xff0c;操作型数据存储&#xff09;作为关键一环&am…

【6大设计原则】代码的艺术:深入探索单一职责原则

1. 引言&#xff1a;理解软件设计的艺术 软件设计&#xff0c;如同艺术创作&#xff0c;需要遵循一定的原则和规则。设计模式六大原则&#xff0c;是软件设计中不可或缺的指导方针。它们为软件开发者提供了一种思考问题的方法&#xff0c;帮助我们编写出更加优雅、高效和可维护…

Rocky系统部署k8s1.28.2单节点集群(Containerd)+Kuboard

目录 Kubernetes介绍 Kubernetes具备的功能 Kubernetes集群角色 Master管理节点组件 Node工作节点组件 非必须的集群插件 Kubernetes集群类型 Kubernetes集群规划 集群前期环境准备 开启Bridge网桥过滤 关闭SWAP交换分区 安装Containerd软件包 K8s集群部署方式 集…

Type-C接口取电芯片-LDR6500

取电芯片&#xff0c;特别是针对Type-C接口的取电芯片&#xff0c;如LDR6328系列&#xff0c;是近年来电子设备领域的一个重要技术组件。这些芯片通过智能协议控制&#xff0c;实现高效、安全的充电过程&#xff0c;并广泛应用于智能手机、平板电脑、笔记本电脑、小家电等各类需…

骗水技巧!怎么让猫咪多喝水?热门补水猫罐头推荐

我家一开始喂的是猫粮&#xff0c;买的还是进口牌子。然后发现团团有很多眼屎&#xff0c;泪痕也很重&#xff0c;我一度怀疑是这个牌子的猫粮不太好&#xff0c;后来就换成了国产的&#xff0c;价格确实少了一半&#xff0c;但是问题还是没有改善&#xff0c;而且吃完以后&…

HarmonyOS应用二之代办事项案例

目录&#xff1a; 1、代码分析2、ArkTS的基本组成3、重点扩展 1、代码分析 1.1代码&#xff1a; 在鸿蒙&#xff08;‌HarmonyOS&#xff09;‌的ArkTS框架中&#xff0c;‌aboutToAppear() 是一个自定义组件的生命周期函数&#xff0c;‌它在组件即将显示时被系统自动调用1。…

多条折线图修改图例以及自定义tooltip

在图例后面添加所有数据之和修改之后 series 中的name之后导致tooltip也加上了重新自定义tooltip&#xff0c;去掉总量统计 核心代码 监听数据改变计算总量修改name字段自定义 tooltip // 计算每条线的总和 const sum1 this.VALUE1.reduce((acc, val) > acc val, 0); co…

应急响应:Linux 入侵排查思路.

什么是应急响应. 一个组织为了 应对 各种网络安全 意外事件 的发生 所做的准备 以及在 事件发生后 所采取的措施 。说白了就是别人攻击你了&#xff0c;你怎么把这个攻击还原&#xff0c;看看别人是怎么攻击的&#xff0c;然后你如何去处理&#xff0c;这就是应急响应。 目录&…

Python OpenCV 影像处理:边缘检测

►前言 上篇介绍使用OpenCV Python findContours() 函数用于在二值化影像中寻找连通的白色区域&#xff0c;并返回一系列点的集合来表示找到的轮廓。本篇将介绍基于计算影像的梯度&#xff0c;通过在影像中找到梯度值的变化来识别边缘&#xff0c;边缘检测通常用于预处理步骤&…

【区块链+食品安全】湖南省食品行业联合会:溯链中国—基于区块链的食品安全可信追溯平台 | FISCO BCOS应用案例

食品安全追溯体系的建设&#xff0c;能够切实加强食品安全监管&#xff0c;确保人民群众饮食安全和身体健康&#xff0c;是创建食品安全城市必不可少的一部分。然而&#xff0c;中心化存储、信息孤岛、窜货是传统溯源行业最大痛点。区块链技术的快速发展&#xff0c; 使得防伪溯…