当前位置: 首页 > news >正文

[排序]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排序相关问题

相关文章:

[排序]hoare快速排序

今天我们继续来讲排序部分&#xff0c;顾名思义&#xff0c;快速排序是一种特别高效的排序方法&#xff0c;在C语言中qsort函数&#xff0c;底层便是用快排所实现的&#xff0c;快排适用于各个项目中&#xff0c;特别的实用&#xff0c;下面我们就由浅入深的全面刨析快速排序。…...

freertos的学习cubemx版

HAL 库的freertos 1 实时 2 任务->线程 3 移植 CMSIS_V2 V1版本 NVIC配置全部是抢占优先级 第四组 抢占级别有 0-15 编码规则&#xff0c; 变量名 &#xff1a;类型前缀&#xff0c; c - char S - int16_t L - int32_t U - unsigned Uc - uint8_t Us - uint…...

PyQt 信号与槽功能

PyQt 信号与槽功能 基本概念&#xff1a;在 PyQt 中&#xff0c;信号&#xff08;Signal&#xff09;与槽&#xff08;Slot&#xff09;是一种用于对象之间通信的机制。信号可以由一个对象发出&#xff0c;而槽是用于接收信号并执行相应操作的函数。 信号 信号是在 PyQt 的类…...

navicat premium安装和破解

https://blog.csdn.net/qq1031893936/article/details/90264688 提示信息 - 吾爱破解 - LCG - LSG |安卓破解|病毒分析|www.52pojie.cn...

OSI七层模型

OSI&#xff08;Open System Interconnect&#xff09;&#xff0c;即开放式系统互连。 该体系结构标准定义了网络互连的七层框架&#xff08;物理层、数据链路层、网络层、传输层、会话层、表示层和应用层 &#xff09;&#xff0c;即OSI开放系统互连参考模型。 应用层 为用…...

Qt自定义MessageToast

效果&#xff1a; 文字长度自适应&#xff0c;自动居中到parent&#xff0c;会透明渐变消失。 CustomToast::MessageToast(QS("最多添加50张图片"),this);1. CustomToast.h #pragma once#include <QFrame>class CustomToast : public QFrame {Q_OBJECT pub…...

自动化测试 pytest 中 scope 限制 fixture使用范围!

导读 fixture 是 pytest 中一个非常重要的模块&#xff0c;可以让代码更加简洁。 fixture 的 autouse 为 True 可以自动化加载 fixture。 如果不想每条用例执行前都运行初始化方法(可能多个fixture)怎么办&#xff1f;可不可以只运行一次初始化方法&#xff1f; 答&#xf…...

软件-vscode-plantUML-drawio

文章目录 vscode基础命令 实操1. vscode实现springboot项目搭建 &#xff08;包括spring data jpa和sqlLite连接&#xff09; PlantUMLDrawio基础实操 vscode 基础 命令 启动mysql命令 docker run --name mysql-container -e MYSQL_ROOT_PASSWORD123456 -p 3306:3306 -d my…...

Python爬虫实战案例(爬取图片)

爬取图片的信息 爬取图片与爬取文本内容相似&#xff0c;只是需要加上图片的url&#xff0c;并且在查找图片位置的时候需要带上图片的属性。 这里选取了一个4K高清的壁纸网站&#xff08;彼岸壁纸https://pic.netbian.com&#xff09;进行爬取。 具体步骤如下&#xff1a; …...

智慧工地视频汇聚管理平台:打造现代化工程管理的全新视界

一、方案背景 科技高速发展的今天&#xff0c;工地施工已发生翻天覆地的变化&#xff0c;传统工地管理模式很容易造成工地管理混乱、安全事故、数据延迟等问题&#xff0c;人力资源的不足也进一步加剧了监管不到位的局面&#xff0c;严重影响了施工进度质量和安全。 视频监控…...

ASP.NET中的六大对象有哪些?以及各自的功能以及使用方式

在ASP.NET Web Forms中&#xff0c;并没有严格意义上的“六大对象”&#xff0c;但通常我们指的是与HTTP请求和响应处理紧密相关的几个内置对象。以下是这些对象及其功能、使用方式以及简单的实现源码示例&#xff1a; Response对象 功能&#xff1a;用于向客户端发送HTTP响应…...

Elastic 及阿里云 AI 搜索 Tech Day 将于 7 月 27 日在上海举办

活动主题 面向开发者的 AI 搜索相关技术分享&#xff0c;如 RAG、多模态搜索、向量检索等。 活动介绍 参加 Elastic 原厂与阿里云联合举办的 Generative AI 技术交流分享日。借助 The Elastic Search AI Platform&#xff0c; 使用开放且灵活的企业解决方案&#xff0c;以前所…...

基于ssm+vue医院住院管理系统源码数据库

摘 要 随着时代的发展&#xff0c;医疗设备愈来愈完善&#xff0c;医院也变成人们生活中必不可少的场所。如今&#xff0c;已经2021年了&#xff0c;虽然医院的数量和设备愈加完善&#xff0c;但是老龄人口也越来越多。在如此大的人口压力下&#xff0c;医院住院就变成了一个…...

【在排序数组中查找元素的第一个和最后一个位置】python刷题记录

R2-分治 有点easy的感觉&#xff0c;感觉能用哈希表 class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:nlen(nums)dictdefaultdict(list)#初始赋值哈希表&#xff0c;记录出现次数for num in nums:if not dict[num]:dict[num]1else:dict[…...

Pytorch基础:Tensor的squeeze和unsqueeze方法

相关阅读 Pytorch基础https://blog.csdn.net/weixin_45791458/category_12457644.html?spm1001.2014.3001.5482 在Pytorch中&#xff0c;squeeze和unsqueeze是Tensor的一个重要方法&#xff0c;同时它们也是torch模块中的一个函数&#xff0c;它们的语法如下所示。 Tensor.…...

PHP压缩打包,下载目录或者文件,解压zip文件

函数 /*** 压缩整个文件夹为zip文件* 本地需要绝对路径&#xff0c;服务器需要相对路径*/function makeZipFile($zip_path , $folder_path ) {$rootPath realpath($folder_path);$zip new ZipArchive(); // $zip->open($zip_path, ZipArchive::CREATE | ZipArchi…...

后端面试题日常练-day08 【Java基础】

题目 希望这些选择题能够帮助您进行后端面试的准备&#xff0c;答案在文末 Java中的静态变量和实例变量有何区别&#xff1f; a) 静态变量属于类&#xff0c;实例变量属于对象 b) 静态变量只能在静态方法中访问&#xff0c;实例变量只能在实例方法中访问 c) 静态变量在类加载时…...

Linux:core文件无法生成排查步骤

1、进程的RLIMIT_CORE或RLIMIT_SIZE被设置为0。使用getrlimit和ulimit检查修改。 使用ulimit -a 命令检查是否开启core文件生成限制 如果发现-c后面的结果是0&#xff0c;就临时添加环境变量ulimit -c unlimited&#xff0c;之后在启动程序观察是否有core生成&#xff0c;如果…...

大模型学习资源

上一篇扯了一堆废话&#xff0c;关于大模型&#xff0c;提供一下建议 说实话&#xff0c;大模型更新太快&#xff0c;以我30岁的高龄实在不适合再去研究技术。偶然发现&#xff0c;国内的大模型厂家在做推广的培训。比如上海人工智能实验室&#xff0c;阿里&#xff0c;百度。…...

约定(模拟赛2 T3)

题目描述 小A在你的帮助下成功打开了山洞中的机关&#xff0c;虽然他并没有找到五维空间&#xff0c;但他在山洞中发现了无尽的宝藏&#xff0c;这个消息很快就传了出去。人们为了争夺洞中的宝藏相互陷害&#xff0c;甚至引发了战争&#xff0c;世界都快要毁灭了。小A非常地难…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能

指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...

书籍“之“字形打印矩阵(8)0609

题目 给定一个矩阵matrix&#xff0c;按照"之"字形的方式打印这个矩阵&#xff0c;例如&#xff1a; 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为&#xff1a;1&#xff0c;…...