[排序]hoare快速排序

今天我们继续来讲排序部分,顾名思义,快速排序是一种特别高效的排序方法,在C语言中qsort函数,底层便是用快排所实现的,快排适用于各个项目中,特别的实用,下面我们就由浅入深的全面刨析快速排序。事先声明,快速排序有不同的版本,今天我们讲的是hoare的版本

目录

快排的定义

hoare快排的具体实现

快排的时间复杂度

优化快速排序

三数取中

小区间优化

相遇位置比key小的问题


快排的定义

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

hoare快排的具体实现

我们先看一下排序的动态图

快排的思想与其他的排序不同,其他排序的基本思想是将最大或者最小的数找出来,放到某一个位置,而在快排中,是将一个数排到有序的位置,然后将其左右分割。

快排会有key,left,right三个变量,key就是当前排序的数的下标,left就是左端,right就是右端

我们先看一下单趟排序的逻辑

注意:左右寻找比key位置大或小的数时,必须从key的另一侧开始移动不然会出现排序错误的问题,这个问题我们之后会具体讲到

那么我们用代码实现一下单趟排序的逻辑

void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
void quicksort(int a[],int left,int right)
{int key = left;//我们假设key位于left的位置int begin = left;int end = right; //用begin和end记录left和right的位置//我们之后要用left和right的值,进行分割区间递归,所以不能改变其值while (begin < end){//右边找小while (begin<end&&a[end] >= a[key]){end--;}//左边找大while (begin<end&&a[begin] <= a[key]){begin++;}swap(&a[begin], &a[end]);}swap(&a[begin], &a[key]);
}

既然单趟排序的逻辑我们已经清楚了,那么我们下一步就该进行多次单趟排序的逻辑,这样我们就能完成快排的逻辑

我们这里先用递归的思想进行实现,看下面的逻辑图

以上便是快排多次进行单词排序的逻辑,即快速排序的全部实现逻辑

下面我们用代码进行实现

void quicksort(int a[],int left,int right)
{if (left >= right){return;}int key = left;//我们假设key位于left的位置int begin = left;int end = right; //用begin和end记录left和right的位置//我们之后要用left和right的值,进行分割区间递归,所以不能改变其值while (begin < end){//右边找小while (begin<end&&a[end] >= a[key]){end--;}//左边找大while (begin<end&&a[begin] <= a[key]){begin++;}swap(&a[begin], &a[end]);}swap(&a[begin], &a[key]);key = begin;//[left,key-1] key [key+1,right]quicksort(a, left, key - 1);//左区间递归排序quicksort(a, key+1, right);//右区间递归排序
}

这里我们还要理解一下,递归终止条件

left >= right

以上即快速排序的基本实现

快排的时间复杂度

我们都知道判断一个排序效率的方法就是比较其时间复杂度

那么快排的时间复杂度是多少呢?

如果从代码的角度看,这个时间复杂度是非常难以计算的

我们先来看快排的递归层数,我们根据上面的逻辑图,可以大致的发现,快排是将数组类似分为二叉树的结构

因此递归的层数为logN层,而在单趟排序中end和begin从两边开始走直到相遇一共走了N步

从这个角度看快排的时间复杂度为  O(NlogN)

因此快排是和堆排序,希尔排序位于同一赛道的排序算法,都是极其高效的算法

排序十万个数(单位毫秒ms)

排序一百万个数 (单位毫秒ms)

 排序五百万个数 (单位毫秒ms)

可以看到当前的快排,并没有想象中那么快,甚至在数多的情况下和堆排序以及希尔排序,还显得效率较低。
而且在排有序数组的情况下,不要说一百万个数,在十万个数有序数组中,会发生一个大问题

1,效率变低

2.由于递归层次太深,每次递归都要建立新的栈帧,这就会可能导致栈溢出的问题 

我们来分析一下问题,之前在正常情况下,时间复杂度为N*logN的前提是每次都是二分递归,即key位置的数都是接近中间的值,此时当二分递归时,递归的深度就是logN,但如果按上面有序情况下,递归的深度是N,这就是上面问题的来源

因此我们现在的快排还是有明显的缺陷

优化快速排序

那么我们如何解决这个问题呢?

避免有序情况下,效率退化

我们可以改变key的选取,如果我们每次都选取最左侧值为key或者最右侧值为key,就会导致上面递归过深的问题,所以我们不能固定选key。

1.随机选key

随机数选key虽然能够解决问题,但是还是有些不靠谱,毕竟是随机的

2.三数取中

最左边,最右边,中间,选取不是最大的和最小的作key

为了保证代码的逻辑不发生变化,即还从最左端的为key,我们就将三数取中的值与最左边的值进行交换,再执行代码逻辑。

三数取中

三数取中是取大小是中间的值,然后完成最好的情况就是二分的情况,即效率最高的情况

运用分支语句进行两两比较返回中间值,直接放代码,逻辑比较简单,不作解释

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

那么我们的快排中需要将交换left和三数取中mid的位置,即加上两行代码,我们其他的逻辑不发生变化

代码如下

void quicksort(int a[],int left,int right)
{if (left >= right){return;}//三数取中int mid = GetMid(a, left, right);swap(&a[mid], &a[left]);  int key = left;//我们假设key位于left的位置int begin = left;int end = right; //用begin和end记录left和right的位置//我们之后要用left和right的值,进行分割区间递归,所以不能改变其值while (begin < end){//右边找小while (begin<end&&a[end] >= a[key]){end--;}//左边找大while (begin<end&&a[begin] <= a[key]){begin++;}swap(&a[begin], &a[end]);}swap(&a[begin], &a[key]);key = begin;//[left,key-1] key [key+1,right]quicksort(a, left, key - 1);quicksort(a, key+1, right);}

在优化后,我们再来比较一下快排的效率

 可以发现,在三数取中后,快排效率也有了优化,而且避免了在有序情况下,递归过深的问题

小区间优化

我们的快排虽然有了优化,但是还有一点缺陷,描述如下图所示

而我们小区间优化,只需要加一个判断语句,对数据个数进行判断,若小于10就用其他的排序方法,大于10就正常递归排序

那么我们选用其他的排序方法要用哪个比较好呢?

我们有插入,堆排序,选择,冒泡,希尔排序,归并排序

我们可以一一进行比较与排除

希尔排序不适用于小数据的排序,堆排序虽然可以,但是我们想一下,没有必要为10个数再单独进行建堆,不然就得不偿失了;归并也是利用递归,没有必要。

那么我们就剩下了冒泡,选择,插入

而在之前的文章中,我们分析过,冒泡和选择排序是远远不如插入排序的效率的

那么我们就选择插入排序

在快排的底层中,小区间优化也是使用的插入排序,这就是插入排序的实际应用

代码如下

	//小区间优化,不再递归分割排序,减少递归次数if ((right - left + 1) < 10){InsertSort(a + left, right - left - 1);}

以上便是优化快排的全部实现

下面放上优化过快排代码

int GetMid(int* a, int left, int right)
{int mid = (left + right) / 2;//left mid rightif (a[mid] > a[left]){if (a[mid] < a[right])return mid;else if (a[left] > a[right])return left;elsereturn right;}else{if (a[mid] > a[right])return mid;else if (a[right] > a[left])return left;elsereturn right;}
}
void swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
void quicksort(int a[],int left,int right)
{if (left >= right){return;}//小区间优化,不再递归分割排序,减少递归次数if ((right - left + 1) < 10){InsertSort(a + left, right - left - 1);}else{//三数取中int mid = GetMid(a, left, right);swap(&a[mid], &a[left]);  int key = left;//我们假设key位于left的位置int begin = left;int end = right; //用begin和end记录left和right的位置//我们之后要用left和right的值,进行分割区间递归,所以不能改变其值while (begin < end){	//右边找小while (begin<end&&a[end] >= a[key]){end--;}//左边找大while (begin<end&&a[begin] <= a[key]){begin++;}swap(&a[begin], &a[end]);}swap(&a[begin], &a[key]);key = begin;//[left,key-1] key [key+1,right]quicksort(a, left, key - 1);quicksort(a, key+1, right);}
}
int main()
{int a[] = { 6,1,2,7,9,3,4,5,10,8 };int sz = sizeof(a) / sizeof(a[0]);quicksort(a, 0, sz - 1);for (int i = 0; i < sz - 1; i++){printf("%d ", a[i]);}return 0;
}

相遇位置比key小的问题

之前我们遗留了一个小问题,就是怎么保证eft和right相遇位置的值一定比key位置小,这样交换后,会让key的左右两边分为比key大的和比key小的,如果相遇位置比key要大的话,那就让数据排序毁了。

那么如何保证相遇位置比key小呢?

先说结论,就是我们上面所说的

当左边作key时,就让右边先走,可以保证相遇位置比key小

以下即解释:

以上是便是hoare排序相关问题

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

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

相关文章

JVM监控及诊断工具-命令行篇--jcmd命令介绍

JVM监控及诊断工具-命令行篇5-jcmd&#xff1a;多功能命令行 一 基本情况二 基本语法jcmd -ljcmd pid helpjcmd pid 具体命令 一 基本情况 在JDK 1.7以后&#xff0c;新增了一个命令行工具jcmd。它是一个多功能的工具&#xff0c;可以用来实现前面除了jstat之外所有命令的功能…

简历网站分享

作者本人自己编写了一个简历站点&#xff0c;分享给大家。在线链接 &#xff0c; github仓库

从PyTorch官方的一篇教程说开去(3.3 - 贪心法)

您的进步和反馈是我最大的动力&#xff0c;小伙伴来个三连呗&#xff01;共勉。 贪心法&#xff0c;可能是大家在处理陌生问题时候&#xff0c;最容易想到的办法了吧&#xff1f; 还记得小时候&#xff0c;国足请了位洋教练发表了一句到现在还被当成段子的话&#xff1a;“如…

【深入C++】map和set的使用

文章目录 C 中的容器分类1. 顺序容器2. 关联容器3. 无序容器4. 容器适配器5. 字符串容器6. 特殊容器 set1.构造函数2.迭代器3.容量相关的成员函数4.修改器类的成员函数5.容器相关操作的成员函数 multiset1.equal_range map1.初始化相关的函数2.迭代器3.容量相关的成员函数4.访问…

58. 不理解竞态问题

内容 竞态问题可能程序员面临的最困难和最隐蔽的错误之一。作为 Go 开发者&#xff0c;必须理解数据竞争和竞态条件等关键方面&#xff0c;包括它们可能产生的影响以及如何避免。接下来将首先讨论数据竞争与竞态条件的区别&#xff0c;然后研究 Go 内存模型及其重要性。 数据…

SpringBoot常用功能实现

1. 配置文件多环境配置 1.1 创建不同环境配置文件 文件名前缀和后缀为标准固定格式&#xff0c;不可以改变。 1.2 pom中加入文件配置 可以使用<activation>标签设置默认环境。 <profiles><profile><id>dev</id><activation><active…

Typora 1.5.8 版本安装下载教程 (轻量级 Markdown 编辑器),图文步骤详解,免费领取(软件可激活使用)

文章目录 软件介绍软件下载安装步骤激活步骤 软件介绍 Typora是一款基于Markdown语法的轻量级文本编辑器&#xff0c;它的主要目标是为用户提供一个简洁、高效的写作环境。以下是Typora的一些主要特点和功能&#xff1a; 实时预览&#xff1a;Typora支持实时预览功能&#xff0…

在 CentOS 7 上安装 Docker 并安装和部署 .NET Core 3.1

1. 安装 Docker 步骤 1.1&#xff1a;更新包索引并安装依赖包 先安装yum的扩展&#xff0c;yum-utils提供了一些额外的工具&#xff0c;这些工具可以执行比基本yum命令更复杂的任务 sudo yum install -y yum-utils sudo yum update -y #更新系统上已安装的所有软件包到最新…

【spring boot】初学者项目快速练手

项目视频&#xff1a;一小时带你从0到1实现一个SpringBoot项目开发_哔哩哔哩_bilibili 注解视频&#xff1a;10、Java高级技术&#xff1a;注解&#xff1a;认识注解_哔哩哔哩_bilibili 一、基础知识 1.注解Annotation &#xff08;1&#xff09;定义 注解是Java代码里的特…

Golang | Leetcode Golang题解之第257题二叉树的所有路径

题目&#xff1a; 题解&#xff1a; func binaryTreePaths(root *TreeNode) []string {paths : []string{}if root nil {return paths}nodeQueue : []*TreeNode{}pathQueue : []string{}nodeQueue append(nodeQueue, root)pathQueue append(pathQueue, strconv.Itoa(root.V…

干货-并发编程提高——线程切换基础(一)

现在的时分&#xff08;time-sharing&#xff09;多任务&#xff08;multi-task&#xff09;操作系统架构通常都是用所谓的“时间分片&#xff08;time quantum or time slice&#xff09;”方式进行抢占式&#xff08;preemptive&#xff09;轮转调度&#xff08;round-robin式…

HydraRPC: RPC in the CXL Era——论文阅读

ATC 2024 Paper CXL论文阅读笔记整理 问题 远程过程调用&#xff08;RPC&#xff09;是分布式系统中的一项基本技术&#xff0c;它允许函数在远程服务器上通过本地调用执行来促进网络通信&#xff0c;隐藏底层通信过程的复杂性简化了客户端/服务器交互[15]。RPC已成为数据中心…

【iOS】内存五大分区

目录 堆&#xff08;Heap&#xff09;是什么五大分区栈区堆区全局/静态区常量区&#xff08;即.rodata&#xff09;代码区&#xff08;.text&#xff09; 函数栈堆和栈的区别和联系图解 OC语言是C语言的超集&#xff0c;所以先了解C语言的内存模型的内存管理会有很大帮助。C语言…

PHP接入consul,注册服务和发现服务【学习笔记】

PHP接入consul,注册服务和发现服务 consul安装 链接: consul安装 启动consul C:\Users\14684>consul agent -dev安装TP5 composer create-project topthink/think5.0.* tp5_pro --prefer-dist配置consul 创建tp5_pro/application/service/Consul.php <?php /*****…

《昇思25天学习打卡营第25天|文本解码原理--以MindNLP为例》

文本解码是自然语言处理&#xff08;NLP&#xff09;中的一个关键步骤&#xff0c;用于将模型生成的向量表示转化为可读的文本。 文本解码的基本原理 在 NLP 中&#xff0c;解码过程通常从模型输出的概率分布或嵌入向量开始&#xff0c;通过某种策略将这些概率或嵌入转化为…

html改写vue日志

本人最近学了vue&#xff0c;想着练手的方法就是改写之前在公司开发的小系统前端&#xff0c;将前端的AJAXJSThymeleaf改为axiosvue。 改写html 将<html>中的<head>和<body>结构移除&#xff0c;将css部分移入<style>&#xff0c; 重新定义了全局的&…

《昇思25天学习打卡营第21天|Pix2Pix实现图像转换》

Pix2Pix 是一种图像转换模型&#xff0c;使用条件生成对抗网络&#xff08;Conditional Generative Adversarial Networks&#xff0c;cGANs&#xff09;实现图像到图像的转换。它主要由生成器&#xff08;Generator&#xff09;和判别器&#xff08;Discriminator&#xff09;…

【Linux】深入探索`cp`命令:文件复制的全面指南

文章目录 一、cp命令概述二、cp命令的基本用法1. 复制单个文件2. 复制多个文件到目录 三、cp命令的常用选项1. -i&#xff1a;交互式复制&#xff08;interactive&#xff09;2. -r或-R&#xff1a;递归复制目录&#xff08;recursive&#xff09;3. -v&#xff1a;详细模式&am…

DAY05 CSS

文章目录 1 CSS选择器(Selectors)8. 后代(包含)选择器9. 直接子代选择器10. 兄弟选择器11. 相邻兄弟选择器12. 属性选择器 2 伪元素3 CSS样式优先级1. 相同选择器不同样式2. 相同选择器相同样式3. 继承现象4. 选择器不同权值的计算 4 CSS中的值和单位1. 颜色表示法2. 尺寸表示法…

2024.7.22 作业

1.将双向链表和循环链表自己实现一遍&#xff0c;至少要实现创建、增、删、改、查、销毁工作 循环链表 looplinklist.h #ifndef LOOPLINKLIST_H #define LOOPLINKLIST_H#include <myhead.h>typedef int datatype;typedef struct Node {union {int len;datatype data;}…