【数据结构】排序——快速排序

前言

本篇博客我们继续介绍一种排序——快速排序,让我们看看快速排序是怎么实现的

💓 个人主页:小张同学zkf

⏩ 文章专栏:数据结构

若有问题 评论区见📝

🎉欢迎大家点赞👍收藏⭐文章 ​

目录

1.快速排序(hoare方法)

2.快速排序(挖坑法)

3.快速排序(前后指针法)

 4.快速排序(非递归法)

5.快速排序特性


 

1.快速排序(hoare方法)

快速排序是 Hoare 1962 年提出的一种二叉树结构的交换排序方法,其基本思想为: 任取待排序元素序列中 的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右 子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止
// 假设按照升序对 array 数组中 [left, right) 区间中的元素进行排序
void QuickSort ( int array [], int left , int right )
{
if ( right - left <= 1 )
return ;
// 按照基准值对 array 数组的 [left, right) 区间中的元素进行划分
int div = partion ( array , left , right );
// 划分成功后以 div 为边界形成了左右两部分 [left, div) [div+1, right)
// 递归排 [left, div)
QuickSort ( array , left , div );
// 递归排 [div+1, right)
QuickSort ( array , div + 1 , right );
}

 我们先看看快速排序的动图

整体思想,以左面的数据为key,然后先让right指针向右走,找比key位置上的值小的值,找到之后,停止移动,然后left指针向左移动找比key大的值,找到之后,交换left和right位置上的值,然后右指针继续找小,左指针继续找大,找到之后继续交换,重归此过程,直到左指针与右指针相遇,相遇的位置与key位置上的值交换,再把key赋值成相遇的位置。这是单趟排序。再将以key为中心分成两个左右区间再次递归到这个函数中,不断递归,直到最后的区间为1,或不存在区间。递归返回。

代码如下

但如果我们想让快排效率高,我们得考虑些极端情况,比如如果右边指针一直没找到比最左边的数大的,左右指针直接在key位置上相遇了。 递归只有一个区间一直递归,就会大大降低了快排的效率,特别是在有序的情况下,所以,只有每次递归,key都在中间位置时,效率才最快,所以我们可以定义一个三数取中的函数,函数的返回值与left位置上的值交换就ok了。

那三数取中么写,其实很简单,就是比较最左边最右边以及最中间的值,谁是第二大的,返回第二大的就行。

三数取中代码如下

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

有了三数取中,快排效率就明显提高,但是还是有人觉得快排不够快,确实,随着递归的深入,效率会越来越慢,所以为了加快效率,我们可以进行小区间优化

 

我们由图分析可知最后一次递归耗费次数最多,所以我们可以对最后几次小区间下手,用其他排序替换快排,从而让效率提高,我们可以在最后几个区间时用插入排序来进行

void charupaixu(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}

ok,到这里我们的代码就写完了,我们想一个问题,为什么我们要选key,并且选的key在左边时,一定要右边指针先走才行,为什么这么规定那。如下图分析

 

这样快速排序(hoare方法)就初步得成,所有代码如下

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void swap(int* as, int* ak)
{int tmp = *as;*as = *ak;*ak = tmp;
}
void charupaixu(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tmp;}
}
int sanshuquzhong(int* a,int left, int right)
{int mid = (left + right) / 2;if (a[left] >a [mid]){if (a[mid]>a[right]){return mid;}else{if (a[right] > a[left]){return left;}else{return right;}}}else{if (a[mid] < a[right]){return mid;}else{if (a[right] > a[left]){return right;}else{return left;}}}
}
void kuaisupaixu(int* arr, int left,int right)
{if (right <= left){return;}if (right - left + 1 < 10)//小区间排序{charupaixu(arr + left, right -left+ 1);}int mid = sanshuquzhong(arr,left, right);//三数取中swap(&arr[mid], &arr[left]);int key = left;int begin = left;int end = right;while (begin<end){while (begin<end&&arr[end] >=arr[key]){end--;}while (begin<end&&arr[begin] <= arr[key]){begin++;}swap(&arr[end], &arr[begin]);}swap(&arr[begin], &arr[key]);key = begin;kuaisupaixu(arr,left,key-1);kuaisupaixu(arr,key+1,right);
}

 


2.快速排序(挖坑法)

随着快排的不断发展,人们优化了hoare方法,用挖坑法,虽然这种方法没有效率的提升,不过方便了人们对代码的理解再也不用考虑为什么要右边先走的问题

我们看一下这个方法的动图

 

其实就是把交换换成填补,定义一个临时变量为坑,最后把Key自然放进坑位就行,这个方法更方便我们理解

就是在hoare方法代码中微调一下就行

代码如下

// 快速排序挖坑法
void PartSort2(int* a, int left, int right)
{if (left >= right){return;}if (right - left + 1 < 10){charu(a+left, right - left + 1);}else{int mid = sanshuquzhong(a, left, right);swap(&a[mid], &a[left]);int key = a[left];int begin = left;int end = right;int keng = left;while (begin < end){while (begin < end && a[end] >= key){end--;}a[keng] = a[end];keng = end;while (begin < end && a[begin] <= key){begin++;}a[keng] = a[begin];keng = begin;}a[begin] = key;PartSort2(a, left, begin- 1);PartSort2(a, begin + 1, right);}}

3.快速排序(前后指针法)

快速排序还有另一种方法,也是最容易记住的,我们可以通过定义两个指针,刚开始一个指向key,一个指向key的下一个数,让前面那个指针一直向前走找比key小的数,第二个若找到比key小的数,那么前后指针之间的数就是比key大的数,++后指针再交换俩指针指向的数,前指针继续向前找,直到超过边界停止,最后key与此时后指针指向的书交换,并且key赋值于后指针的位置,递归key前key后空间

动图如下

我们可以画图分析一下 

 

 

代码如下

// 快速排序前后指针法
void PartSort3(int* a, int left, int right)
{if (left >= right){return;}if (right - left + 1 < 10){charu(a + left, right - left + 1);}else{int mid = sanshuquzhong(a, left, right);swap(&a[mid], &a[left]);int key = left;int man = left;int kuai = left + 1;while (kuai <= right){if (a[kuai] < a[key] && ++man != kuai){swap(&a[man], &a[kuai]);}kuai++;}swap(&a[key], &a[man]);key = man;PartSort3(a, left, key - 1);PartSort3(a, key + 1, right);}
}

 4.快速排序(非递归法)

前三种方法都是递归法,若不用递归我们该怎么弄,不用递归,我们就得需要栈这个结构,代码整体不变,把最后递归的部分改成把key左右两个区间全入栈,先右区间入栈再左区间入栈,因为栈是后进先出原则,出栈就是左区间先出栈,直到栈空,入栈的条件左指针小于Key-1,右指针大于key+1。

画图看一下

 

区间边界值入栈,来替代了递归 

代码如下

#include "stack.h"
int yici(int* a,int left,int right)
{int mid = sanshuquzhong(a, left, right);swap(&a[mid], &a[left]);int key = left;int begin = left;int end = 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[key], &a[begin]);key = begin;return key;
}
void QuickSortNonR(int* a, int left, int right)
{if (right - left + 1 < 10){charu(a + left, right - left + 1);}else{Stack as;StackInit(&as);StackPush(&as, right);StackPush(&as, left);while (!StackEmpty(&as)){int begin1 = StackTop(&as);StackPop(&as);int end1 = StackTop(&as);StackPop(&as);int key = yici(a, begin1, end1);if (key + 1 < end1){StackPush(&as, end1);StackPush(&as, key + 1);}if (key - 1 > begin1){StackPush(&as, key - 1);StackPush(&as, begin1);}}StackDestroy(&as);}
}

5.快速排序特性

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

3. 空间复杂度: O(logN)
4. 稳定性:不稳定

结束语 

快排有关知识就总结完了,我认为快速排序这个排序还是蛮重要的,大家要对这个排序更加重视,最后一个排序就是归并排序了,留在下篇博客说

0K,本篇博客结束!!!

 

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

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

相关文章

LinK3D: Linear Keypoints Representation for 3D LiDAR Point Cloud【翻译与解读】

LinK3D: Linear Keypoints Representation for 3D LiDAR Point Cloud 摘要 特征提取和匹配是许多机器人视觉任务的基本组成部分&#xff0c;如 2D 或 3D 目标检测、识别和配准。2D 特征提取和匹配已取得巨大成功。然而&#xff0c;在 3D 领域&#xff0c;当前方法由于描述性差…

Python-找客户软件

软件功能 请求代码&#xff1a; 填充表格&#xff1a; 可以search全国各个区县的所有企业信息&#xff0c;过滤手机号、查看是否续存/在业状态。方便找客户。 支持定-制-其他引-留-阮*件&#xff08;XHSS&#xff0c;DYY&#xff0c;KS&#xff0c;Bi-li*Bi-li&#xff09; V*…

HTML 标签简写和全称及其对应的中文说明和实例

<!DOCTYPE html> <html lang"zh-CN"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>HTML 标签简写及全称</title><style>…

【web前端HTML+CSS+JS】--- CSS学习笔记02

一、CSS&#xff08;层叠样式表&#xff09;介绍 1.优势 2.定义解释 如果有多个选择器共同作用的话&#xff0c;只有优先级最高那层样式决定最终的效果 二、无语义化标签 div和span&#xff1a;只起到描述的作用&#xff0c;不带任何样式 三、标签选择器 1.标签/元素选择器…

2.4G芯片开发的遥控玩具方案介绍 东莞酷得

玩具从早期的简单功能&#xff0c;到现如今各种各样的智能操作&#xff0c;发展的速度也是飞速的。随着玩具市场的逐步完善与推进&#xff0c;中国的智能玩具市场也出现了很多远程遥控玩具。遥控玩具也是从最初的有线到现在的无线&#xff0c;从地上跑的到天上飞的&#xff0c;…

N6 word2vec文本分类

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊# 前言 前言 上周学习了训练word2vec模型&#xff0c;这周进行相关实战 1. 导入所需库和设备配置 import torch import torch.nn as nn import torchvision …

3,区块链加密(react+区块链实战)

3&#xff0c;区块链加密&#xff08;react区块链实战&#xff09; 3.1 哈希3.2 pow-pos-dpos3.3非对称加密&#xff08;1&#xff09;对称加密AES&#xff08;2&#xff09;非对称加密RSA 3.4 拜占庭将军3.5 P2P网络3.6 区块链 3.1 哈希 密码学&#xff0c;区块链的技术名词 …

四川赤橙宏海商务信息咨询有限公司抖音电商服务靠谱吗?

在数字化浪潮席卷全球的今天&#xff0c;电商行业蓬勃发展&#xff0c;各种新兴电商平台层出不穷。其中&#xff0c;抖音电商以其独特的社交属性和庞大的用户基础&#xff0c;迅速崛起为行业新星。四川赤橙宏海商务信息咨询有限公司&#xff0c;作为专注于抖音电商服务的佼佼者…

[Linux]五种IO模型(图文讲解+故事讲解)

目录 一、对IO的理解&#xff1a;等拷贝 等 拷贝 二、五种IO模型&#xff08;解释其概念&#xff09; 1.阻塞IO 2.非阻塞IO 3.信号驱动IO 4.IO多路复用 5.异步IO IO速度比较 三、一个故事让你了解五种IO模型 四、同步VS异步 阻塞VS非阻塞 同步VS异步 阻塞VS非阻…

2023 年 GitHub 上最受欢迎的编程语言

JavaScript 仍然是使用最多的编程语言&#xff0c;在 Web 开发中占据重要地位。 被广泛用于 Web 应用程序开发&#xff0c;框架如 React 和 Angular 促进了单页应用程序的开发。 Node.js 的出现使其在后端编程中同样重要。 Python 由于其简单性和广泛的库&#xff0c;Pyth…

07-7.5.1 散列表的基本概念

&#x1f44b; Hi, I’m Beast Cheng &#x1f440; I’m interested in photography, hiking, landscape… &#x1f331; I’m currently learning python, javascript, kotlin… &#x1f4eb; How to reach me --> 458290771qq.com 喜欢《数据结构》部分笔记的小伙伴可以…

【测试开发】--安全渗透测试

1. 安全渗透 1.1 分类 web数据库安全web应用服务器安全&#xff08;文件上传漏洞、文件包含漏洞&#xff09;web客户端安全&#xff08;XSS跨站攻击&#xff09; 2. sql注入 2.1 sql注入介绍 sql注入在安全问题中排行榜首sql注入攻击是输入参数未经过滤&#xff0c;然后直…

MySQL的约束键多表查询

约束 概念 概念&#xff1a;约束是作用于表中字段上的规则&#xff0c;用于限制存储在表中的数据。目的&#xff1a;保证数据中数据的正确、有效性和完整性。 外键约束 概念 ​ 外键用来让两张表的数据之间建立连接&#xff0c;从而保证数据的一致性和完整性。 注意&#x…

最优化(10):牛顿类、拟牛顿类算法

4.4 牛顿类算法——介绍了经典牛顿法及其收敛性&#xff0c;并介绍了修正牛顿法和非精确牛顿法&#xff1b; 4.5 拟牛顿类算法——引入割线方程&#xff0c;介绍拟牛顿算法以及拟牛顿矩阵更新方式&#xff0c;然后给出了拟牛顿法的全局收敛性&#xff0c;最后介绍了有限内存BFG…

202-509SF 同轴连接器

型号简介 202-509SF是Southwest Microwave的连接器。这款连接器机身和法兰由不锈钢合金 UNS-30300 制成&#xff0c;螺纹接头则采用 5C360 黄铜合金。接触点采用 BeCu 合金&#xff0c;并经过镀金处理&#xff0c;以提供优异的导电性和耐腐蚀性。绝缘体则由 PTFE 氟碳或 ULTEM …

Backend - C# 的日志Lognet4

目录 一、安装 log4net 插件 &#xff08;一&#xff09;作用 &#xff08;二&#xff09;操作 &#xff08;三&#xff09;注意 二、配置 &#xff08;一&#xff09;配置AssemblyInfo.cs &#xff08;二&#xff09;配置log4net.config 1. 创建log4net.config文件&#xff08…

3.动态规划.基础

3.动态规划.基础 基础理论背包基础理论01背包完全背包多重背包 题目1.斐波那契数2.爬楼梯3.使用最小花费爬楼梯4.不同路径5.不同路径2 基础理论 动态规划&#xff0c;英文&#xff1a;Dynamic Programming&#xff0c;简称DP&#xff0c;如果某一问题有很多重叠子问题&#xf…

【Linux】常见指令收官权限理解

tar指令 上一篇博客已经介绍了zip/unzip指令&#xff0c;接下来我们来看一下另一个关于压缩和解压的指令&#xff1a;tar指令tar指令&#xff1a;打包/解包&#xff0c;不打开它&#xff0c;直接看内容 关于tar的指令有太多了&#xff1a; tar [-cxtzjvf] 文件与目录 ...…

VSCode升级后不能打开在MacOS系统上

VSCode 在MacOS无法打开 版本 VSCode version: 1.91.0 (x64) 错误信息&#xff1a; MacBook-Pro ~ % /Users/mac/Downloads/FirefoxDownloads/Visual\ Studio\ Code.app/Contents/MacOS/Electron ; exit; [0710/142747.971951:ERROR:crash_report_database_mac.mm(753)] op…

RFID技术革新养猪业,构建智能化养殖场

RFID技术作为无线射频识别技术的一种&#xff0c;凭借着非接触、高效识别的特性&#xff0c;在养殖业行业中得到了广泛的应用&#xff0c;为构建智能化、高效化的养殖场提供了强大的技术支持&#xff0c;给传统养殖业带来了一场前所未有的技术变革。以下是RFID技术在养猪行业不…