【排序】快速排序(递归和非递归)

news/2024/4/24 20:07:13/

快速排序

    • 前言
    • 图解
    • 大致思路
      • 对于hoare版本
      • 对于挖坑法
      • 对于前后指针法
    • 实现方法
      • 递归
      • 非递归
    • 快排的优化(基于递归的优化)
      • 三数取中法
      • 小区间优化
    • 时间复杂度和空间复杂度

在这里插入图片描述

前言

快速排序,听名字就比较霸道,效率根名字一样,非常的快,但也还是O(N * logN)级别的。

我所学到的快排有三个版本:

  1. 原始版本hoare版本,也就是hoare这个人发明的
  2. 基于hoare版本改进的版本,挖坑法(还有别的叫法,我这里就说成挖坑法了)。
  3. 是跟上面两种方法不一样的方法,前后指针法。

这里讲之前跟我前面的博客一样,先给图解。

图解

首先hoare版本的:
在这里插入图片描述

挖坑法
在这里插入图片描述

前后指针法
在这里插入图片描述

大致思路

首先,快排讲的是一个分治的思想,什么叫分治呢,根二叉树的前序遍历一样,先处理根,再处理左树和右树。那么快排也就是这样,先处理当前的(定关键字key的位置),然后再处理左半边的,后右半边的。

那这里的关键字key是什么呢?其实就是每趟排序的时候,首先选出来的一个数(一般选择最左端或者最右端),这个数决定了你是从左往右排还是从右往左排,什么意思呢?

对于hoare版本

当你的key选取在最左端时,就先让R(right)先走,R找小,找到了之后再让L(L找大)走。

当你的key选取在最右端时,就先让L(left)先走,L找大,找到了之后再让R(R找小)走。

这样能够保证L能和R相遇

下面以key在最左端为例
此时会出现以下情况:

当R找到小的了,L也找到大的了,就让两个位置上的数交换。再让R走,找小,找到了停,L找大,重复上述步骤。

当R和L相遇时,就将key位置上的数与相遇位置的数交换位置。本趟排序结束。

然后就开始递归,递归排序相遇位置的左边和相遇位置的右边。

对于挖坑法

当你的key选取在最左端时,就先让R(right)先走,R找小

当你的key选取在最右端时,就先让L(left)先走,L找大

此时key位置就是坑的位置
这样能够保证L能和R相遇,根hoare版本一样

下面以key在最左端为例
此时会出现以下情况:

当R找到小的了,就直接把R的值放到原坑中,R位置作为新的坑,再让L先走,找大,找到大的,将L的值放到原坑中,L位置作为新坑,不断重复上述步骤。

当R和L相遇,相遇位置的数放到原坑中,相遇位置作为新坑,将key的值放到新坑中。本趟排序结束

然后就开始递归,递归排序相遇位置的左边和相遇位置的右边。根hoare相似。

对于前后指针法

当你的key选取在最左端时,就让cur从左往右走

当你的key选取在最右端时,就让cur从右往左走

下面以key在最左端为例
此时会出现以下情况:

当cur位置上的数小于key时,prev++,交换cur和prev上的数,cur++

当cur位置上的数大于等于key时,prev什么也不做,cur++
直至cur越界,再交换key和prev位置上的数。本趟排序结束。

记下cur越界时prev的位置。
然后就开始递归,递归排序该位置的左和该位置的右。

实现方法

递归

hoare版本的单趟

//hoare版本
int PartSort1(int* a, int left, int right)
{int keyi = left;while (left < right){//right找小				等于的时候也得走,不然程序会崩掉,这里是个易错点while (left < right && a[right] >= a[keyi]){right--;}//left找大				等于的时候也得走,不然程序会崩掉,这里是个易错点while (left < right && a[left] <= a[keyi]){left++;}//找到了就交换,或者二者相遇,同一个位置交换不交换都是一样的swap(&a[left], &a[right]);}//相遇swap(&a[left], &a[keyi]);keyi = left;//返回相遇的位置,keyi、left和right都可以return keyi;
}

挖坑法的单趟

//挖坑法
int PartSort2(int* a, int left, int right)
{int key = a[left];while (left < right){//right找小while (left < right && a[right] >= key){right--;}//找到了把数放到原坑,right做新坑,相遇的时候也不影响a[left] = a[right];//left找大while (left < right && a[left] <= key){left++;}//找到了把数放到原坑,left做新坑,相遇的时候也不影响a[right] = a[left];}//相遇的位置放keya[left] = key;//返回相遇的位置return left;
}

前后指针法的单趟

//前后指针法
int PartSort3(int* a, int left, int right)
{int keyi = left;int previ = left;int curi = previ + 1;while (curi <= right){//小了并且previ+1不等于curi再交换if (a[curi] < a[keyi] && ++prev != curi))swap(&a[previ], &a[curi]);curi++;}swap(&a[previ], &a[keyi]);return previ;
}

全趟排序
上面三个的代码只是单趟的排序,还要放到整体的排序中:

//快排
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;//hoare//int keyi = PartSort1(a, begin, end);//挖坑法//int keyi = PartSort2(a, begin, end);//前后指针法int keyi = PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

上面的就是三种方法的代码了。

非递归

非递归的话,得要用到栈。

图解:
在这里插入图片描述

代码实现:

//快排非递归
//快排非递归
void QuickSortNonR(int* a, int begin, int end)
{Stack st;StackInit(&st);//初始情况下就入左右两端//先入右边再入左边StackPush(&st, end);StackPush(&st, begin);//栈不为空才继续循环while (!StackEmpty(&st)){//取左int lefti = StackTop(&st);StackPop(&st);//取右int righti = StackTop(&st);StackPop(&st);//得关键字位置int keyi = PartSort3(a, lefti, righti);//区间存在才入栈if (lefti < keyi - 1){//先入右边再入左边StackPush(&st, keyi - 1);StackPush(&st, lefti);}//区间存在才入栈if (righti > keyi + 1){//先入右边再入左边StackPush(&st, righti);StackPush(&st, keyi + 1);}}}

快排的优化(基于递归的优化)

三数取中法

上面递归的三个单趟排序其实是可以再优化一下的(以升序为例),因为当数组有序的时候每次选择key时,选出来的都是最小值,这时候key最终放的位置就是最左端,而递归的时候需要把key的左端和key的右端继续排,然而此时key处于最左端,那么递归排别的段的时候就只能排key的右端了,这个时候就相当于是排一次去处一个数,那么就变成了N,N-1,N-2,…2,1,时间复杂度就会变成O(N^2),就相当于是冒泡排序了。这样的话快排就排的不快了。
在这里插入图片描述

但我们所希望的是这样的:
在这里插入图片描述

怎么做呢?
虽然我们不能取到所有有序的数中最中间的数,但是我们可以取到所有无序的数中位于最中间的数,每次排序前把这个数和左右两端的数比较以下,求出值为三者中不大也不小的那个数,然后再把这个数放到最前面,就可以实现类似于图二的方法,虽然做不到完全二分,但是也比图一强。

三数取中

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

然后把这个函数放在每一个单趟排序函数的最前面就行。

hoare版本的优化

//hoare版本
int PartSort1(int* a, int left, int right)
{//三数取中优化int mid = GetMid(a, left, right);swap(&a[left], &a[mid]);int keyi = left;while (left < right){//right找小				等于的时候也得走,不然程序会崩掉,这里是个易错点while (left < right && a[right] >= a[keyi]){right--;}//left找大				等于的时候也得走,不然程序会崩掉,这里是个易错点while (left < right && a[left] <= a[keyi]){left++;}//找到了就交换,或者二者相遇,同一个位置交换不交换都是一样的swap(&a[left], &a[right]);}//相遇swap(&a[left], &a[keyi]);keyi = left;//返回相遇的位置,keyi、left和right都可以return keyi;
}

挖坑法的优化

//挖坑法
int PartSort2(int* a, int left, int right)
{//三数取中优化int mid = GetMid(a, left, right);swap(&a[left], &a[mid]);int key = a[left];while (left < right){//right找小while (left < right && a[right] >= key){right--;}//找到了把数放到原坑,right做新坑,相遇的时候也不影响a[left] = a[right];//left找大while (left < right && a[left] <= key){left++;}//找到了把数放到原坑,left做新坑,相遇的时候也不影响a[right] = a[left];}//相遇的位置放keya[left] = key;//返回相遇的位置return left;
}

前后指针法的优化

//前后指针法
int PartSort3(int* a, int left, int right)
{//三数取中优化int mid = GetMid(a, left, right);swap(&a[left], &a[mid]);int keyi = left;int previ = left;int curi = previ + 1;while (curi <= right){//小了并且previ+1不等于curi再交换if (a[curi] < a[keyi] && ((previ + 1) != curi))swap(&a[previ], &a[curi]);curi++;}swap(&a[previ], &a[keyi]);return previ;
}

小区间优化

小区间优化的作用在于当数据量比较大时,递归可能会导致栈溢出。

而快排递归的时候是类似于二叉树的,所以最后一层递归所开辟的空间基本上要占用总空间的一半(完全二分的情况下),这个时候如果我们控制一下最后一层,不让这一层的数递归排序,就可以很好地避免栈溢出的问题。

怎么做呢。很简单,判断一下当递归某一区间段的时候(右端下标 - 左端下标 < X(X可取10~20之间的数)),这时候就可以用一下别的排序,而10~20的数据量还是很小的,所以不需要用比较复杂的排序,用一个N^2级别的排序就可以了,而N^2级别的排序中插入排序就是最好的,所以这时候替换成插入排序就可以了。

小区间优化

//快排
void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}else if (end - begin + 1 <= 10){//小区间优化InsertSort(a + begin, end - begin + 1);}else{//int keyi = PartSort1(a, begin, end);//int keyi = PartSort2(a, begin, end);int keyi = PartSort3(a, begin, end);QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}}

时间复杂度和空间复杂度

我这里之说优化之后的。

时间复杂度就是O(N* logN),空间复杂度是O(logN)。

就说一下空间复杂度,因为快排是基于分治思想的,而且递归排序的过程类似于二叉树的前序遍历,所以在栈上开辟空间时就要不断的堆栈,然后当函数递归达到最大深度(二叉树的最下面一层)的时候,也就是logN,函数返回,最深层的函数系统就会自动回收空间,这时候就不会再开辟更大的空间了,而且开辟的空间是慢慢的缩小再增大,再减少,再增大。。。直到排序结束。所以空间开辟的时候最大也就开辟logN大小的空间。

到此结束。。。


http://www.ppmy.cn/news/46934.html

相关文章

理解C语言中的空指针和野指针

在C语言中&#xff0c;指针是一个非常重要的概念&#xff0c;可以用于操作变量和数据结构。但是&#xff0c;指针也是很容易出错的地方。其中包括两种可能的错误&#xff1a;空指针和野指针。 空指针 空指针指代无效的地址&#xff0c;表示指针不指向内存中的任何一个合法对象…

深入剖析:如何优化Android应用的性能和内存管理

深入剖析&#xff1a;如何优化Android应用的性能和内存管理 性能和内存管理的重要性 在今天的移动应用开发中&#xff0c;用户对于应用的性能和体验要求越来越高。一款性能卓越的Android应用能够提供流畅的操作体验、快速的响应速度以及较低的资源消耗&#xff0c;从而提高用户…

Android 11.0 设置默认DNS

1.前言 在11.0的系统rom产品定制化开发中,由于是wifi产品的定制,需要对wifi功能要求比较高,所以在wifi需求方面要求设置默认的dns功能,这就需要分析网络通讯 流程,然后在联网之后,设置默认的dns,来实现功能要求 2.设置默认DNS的核心类 frameworks\base\core\java\andr…

深入探索 Qt6 web模块 WebEngineCore:从基础原理到高级应用与技巧

深入探索 Qt WebEngineCore&#xff1a;从基础原理到高级应用与技巧 Diving into Qt WebEngineCore: From Basic Principles to Advanced Applications and Techniques 一、Qt WebEngineCore 模块简介及原理 (Introduction and Principles of Qt WebEngineCore Module)Qt WebEn…

使用layui组件库制作进度条

使用layui组件库制作进度条 html代码 <!DOCTYPE html> <html> <head><meta charset"UTF-8"><title>Example</title><!-- 引入 layui 的 CSS 文件 --><link rel"stylesheet" href"https://cdn.staticfil…

WordPress图片水印插件 Easy Watermark

1、概述 WordPress图片水印插件Easy Watermark 是一款实现上传图片自动添加水印LOGO功能的高效插件。当我们在WordPress网站后台上传图片文件到媒体库时&#xff0c;或者在发布文章上传图片时&#xff0c;Easy Watermark 都能为图片自动添加水印&#xff0c;同时&#xff0c;还…

查询练习:连接查询

准备用于测试连接查询的数据&#xff1a; CREATE DATABASE testJoin;CREATE TABLE person (id INT,name VARCHAR(20),cardId INT );CREATE TABLE card (id INT,name VARCHAR(20) );INSERT INTO card VALUES (1, 饭卡), (2, 建行卡), (3, 农行卡), (4, 工商卡), (5, 邮政卡); S…

杨志丰:一文详解,什么是单机分布式一体化?

欢迎访问 OceanBase 官网获取更多信息&#xff1a;https://www.oceanbase.com/ 3 月 25 日&#xff0c;第一届 OceanBase 开发者大会在北京举行&#xff0c;OceanBase 首席架构师杨志丰&#xff08;花名&#xff1a;竹翁&#xff09;带来了 《OceanBase 的单机分布式一体化》 的…

IPSEC VPN动态配置(示例)

用的锐捷设备。 ipsec加密图用于对外接口上。 IPsec 使用IPSec对本部到各分部的数据流进行加密。要求使用动态隧道主模式&#xff0c;安全协议采用esp协议&#xff0c;加密算法采用3des&#xff0c;认证算法采用md5&#xff0c;以IKE方式建立IPsec SA。在R1上配置ipsec加密转…

神器集合!这12个免费工具可以让您的工作更高效

好的工具&#xff0c;能够帮助我们更高效地完成工作&#xff0c;节省时间和精力; 节省出更多的摸鱼时间&#xff01; 本文将介绍 12 款绝佳的免费效率工具&#xff0c;这些工具可以让你事半功倍&#xff0c;提高工作效率。无论你是一名程序员、设计师、学生还是白领&#xff0c…

插件化换肤原理—— 布局加载过程、View创建流程、Resources 浅析

作者&#xff1a;孙先森Blog 本文主要分析了 Android 布局加载流程 分析 一般的换肤功能大概是这样的&#xff1a;在 App 的皮肤商城内下载“皮肤包”&#xff0c;下载完成后点击更换界面上的 View 相关资源&#xff08;颜色、样式、图片、背景等&#xff09;发生改变&#xf…

2023年全国最新道路运输从业人员精选真题及答案59

百分百题库提供道路运输安全员考试试题、道路运输从业人员考试预测题、道路安全员考试真题、道路运输从业人员证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 79.道路交通事故自发生之日起&#xff08;&#xff09;日内&…

Linux实战学习

文章目录 一、Linux权限信息权限控制信息chmodifconfigpingnmap netstatps killzip unzip常用快捷键 二、搭建Java环境yumJDKTomcatMysql 三、部署Web项目到服务器 一、Linux权限信息 Linux中&#xff0c;拥有最大权限的账户为: root(超级管理员)&#xff0c;而普通用户在很多…

【产品设计】Android 和 IOS 的交互设计对垒

在手机操作系统百花齐放的年代&#xff0c;也是产品经理最头疼的年代&#xff0c;因为需要根据不同的操作系统做出不同的设计。而如今&#xff0c;手机操作系统基本只剩下安卓和IOS两大阵营&#xff0c;只需处理好安卓和IOS交互上的差异部分就可以做好产品设计了。 手机操作系统…

微信小程序登录注册页面

// login.js // 获取应用实例 var app getApp() var api require("../../utils/api.js")Page({data: {motto: zhenbei V1.0.0,userInfo: {},hasUserInfo: false,disabled: true,btnstate: default,username: ,password: ,canIUse: wx.canIUse(button.open-type.get…

EMQX vs Mosquitto | 2023 MQTT Broker 对比

引言 物联网开发者需要为自己的物联网项目选择合适的 MQTT 消息产品或服务&#xff0c;从而构建可靠高效的基础数据层&#xff0c;保障上层物联网业务。目前市面上有很多开源的 MQTT 产品&#xff0c;在性能功能等方面各有优点。本文将选取目前最为流行的两个开源 MQTT Broker…

Python入门教程+项目实战-9.5节: 程序实战-模式匹配算法

目录 9.5.1 何为模式匹配&#xff1f; 9.5.2 朴素模式匹配算法 9.5.3 系统学习python 9.5.1 何为模式匹配&#xff1f; 模式匹配是数据结构中字符串的一种基本运算: 给定一个子串&#xff0c;要求在主串中找出与该子串相同的所有子串&#xff0c;这就是模式匹配。举个简单的…

1. 大端法和小端法

int32_t num 0x01020304;一个int32_t是4个字节&#xff0c;在内存中的存储是高位字节在低地址&#xff0c;低位字节在高地址。 &#xff08;数字&#xff09;前者的高低是数字位数的高低&#xff0c;左边是高位数&#xff0c;右边是低位数&#xff1b; &#xff08;地址&…

凌恩生物美文分享|好看又实用,多组学联合分析项目大揭秘!

基因层面的功能潜能有没有真的实现表达&#xff0c;表达量是高是低&#xff1f;下游合成的蛋白质行使了什么样得功能&#xff0c;代谢产物通过体循环到达靶器官&#xff0c;又是如何影响靶器官的工作运行的&#xff1f; 一个完整的生物学故事&#xff0c;中心法则贯穿始终&…

PS学习记录-基础操作与快捷键

1、复制图层 在【移动工具】状态下&#xff0c;配合【alt】按键拖动图像&#xff0c;可以进行复制图层 当然&#xff0c;PS里复制图层的方式很多&#xff0c;比如&#xff1a;选中图层&#xff0c;按【ctrlJ】&#xff0c;也是复制图层 2、多选图层 2.1同上&#xff0c;也是…