快速排序详解及优化方式

ops/2024/10/20 15:47:19/

目录

1.快速排序的核心思想

2.快速排序的两个重要方法

Hoare法

quickHoare函数（想办法把基准放到数组正确排序好的位置）

代码：

挖坑法

逻辑：

翻译成代码：

3.快速排序的时间/空间复杂度分析

最好情况

最坏情况

总结：

空间复杂度分析

4.基于减少递归的优化方法

三数取中

末尾换用直接插入排序

快速排序的稳定性：

下面都以升序为例进行讲解：

1.快速排序的核心思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：

1.在数组中任取一个元素作为基准（基准一般选取最左边的元素），

想办法排列数组，让所有小于基准的元素都放到基准的左边，所有大于基准的元素都放到基准的右边，完成后，基准元素就排列好了。

2.采用分而治之的思想，分别对基准左区间的元素和基准右区间的元素进行1中的操作，从而完成排序。

2.快速排序的两个重要方法

Hoare法

传入的数组作为唯一的接口，对quickSortHoare方法进行实现：

public static void quickSortHoare(int[] arr){quickHoare(arr,0,arr.length-1);}

核心思想中提到了分治，所以大概率我们是要递归定义这个quickHoare方法的：

    private static void quickHoare(int[] arr,int left,int right){if(left>=right)return;//已经没有排序区间了，直接返回即可//下面这个partionHoare方法可以把基准放到排序好的位置，然后返回基准排好后的下标位置int mid=partitonHoare(arr,left,right);//left和right一定是合法有效的quickHoare(arr,left,mid-1);//递归基准左侧区间quickHoare(arr,mid+1,right);//递归基准右侧区间}

先不关心quickHoare函数的具体实现和细节，把总体思路捋一遍，以上的代码就是核心思路了，只要把quickHoare实现函数，快速排序就搞定了。

quickHoare函数（想办法把基准放到数组正确排序好的位置）

默认最左边的元素为基准(stand)

left下标和right下标分别指向最左和最右

{1 3 4 5 6 7 9}--》这是排序好的数组，下面看看quickHoare函数，怎么把没排好序的数组中6放到4的位置的：

1.先让right往前走，只要arr[right]>=stand，right就减减:

2.然后再让left往下走，只要arr[left]<=3，left就加加:

3.到了这里，right和left都不能走了，所以接下来arr[left]和arr[right]两个元素进行交换:

4.在重复上述right和left的移动逻辑，直到，left与right相遇（一定会相遇）：

5.遇到上面这个情况实际上就是循环终止条件，直接把arr[left]（当然arr[right]也是可以的）和6进行交换即可：

此时，元素“6”的位置已经排好，在对1 3 4 5和7 9进行分治采用相同的方法即可达到排序目的。

代码：

 private static int partitonHoare(int[] arr,int left,int right){//返回排序好元素的下标int i=left;int stand=arr[left];//基准默认是最左边的元素while(left<right){//此条件防止下标越界//先右边下标走while(left<right&&arr[right]>=stand){right--;}while(left<right&&arr[left]<=stand){left++;}//程序到达这里时：arr[right]<stand 而arr[left]>standswap(arr,right,left);            //交换arr[right]和arr[left]}//当程序到达这里，right==left了，此时这两个下标所指的位置，就是arr[i]有序时，因该在的位置swap(arr,i,left);return left;//返回right也是一样的}

Hoare方法的整体代码：

class TestSort{private static void swap(int[] arr,int a,int b){int t=2;t=arr[a];arr[a]=arr[b];arr[b]=t;}public static void quickSortHoare(int[] arr){quickHoare(arr,0,arr.length-1);}private static void quickHoare(int[] arr,int left,int right){if(left>=right)return;//已经没有排序区间了，直接返回即可//下面这个partionHoare方法可以把基准放到排序好的位置，然后返回基准排好后的下标位置int mid=partitonHoare(arr,left,right);//left和right一定是合法有效的quickHoare(arr,left,mid-1);//递归基准左侧区间quickHoare(arr,mid+1,right);//递归基准右侧区间}private static int partitonHoare(int[] arr,int left,int right){//返回排序好元素的下标int i=left;int stand=arr[left];//基准默认是最左边的元素while(left<right){//先右边下标走while(left<right&&arr[right]>=stand){right--;}while(left<right&&arr[left]<=stand){left++;}//程序到达这里时：arr[right]<stand 而arr[left]>standswap(arr,right,left);            //交换arr[right]和arr[left]}//当程序到达这里，right==left了，此时这两个下标所指的位置，就是arr[i]有序时，因该在的位置swap(arr,i,left);return left;//返回right也是一样的}

不知道小伙伴们有没有这样的困惑：

1、能让left先走，然后right再走吗？

2、为什么arr[left]<=stand arr[right]>=stand 小于或者等于不可以吗？

首先第一个问题，我们：还是用前面那个数组作为样例

让left先走，然后是right,其他逻辑不变：

交换：

left先走:

哦豁，按照这样，6因该放到7的位置，显然是错的

根据1 3 4 5 6 7 9，因该放到4的位置（倒数第三个位置）。

这就是为什么要让right先走，然后left再走的原因的原因。
其次，第二个问题，left>=stand或者right<=stand就停下，以这个数组为例

{ 1 ，1， 1， 1， 1}

如果是这种重复的数组，那么left和right就不可能相遇了，会死循环的。

挖坑法

逻辑：

顾名思义就是挖坑，举个例子：

此时的3，就被挖走了，放到了tmp中（当然这是抽象的理解，实际上3还在数组的原来位置）。

接下来的逻辑就和hoare法差不多，先让right走，但是因为arr[right]=2<3所以，right就不走了，然后把arr[right]“挖走”，填到arr[left]中，然后再让left++：

此时arr[right]形成了新的坑（当然也是抽象理解，实际装的还是2）

我们继续尝试让left前进，但是arr[left]=7>3了，所以left停下，

挖走arr[left]填给arr[right]，然后right往上移动：

循环上面的逻辑：

right移动到1的位置停止：

挖走arr[right]填到arr[left]，然后left往下移动：

此时left==right，退出循环，把tmp填进坑：

如图，3已经在升序的正确位置了。

翻译成代码：

private static int partitionPit(int[] arr,int left,int right){//左右，都是有效的闭区间下标int tmp=arr[left];//先挖一个坑(在left的位置)，把土放进tmpwhile(left<right){while(left<right&&arr[right]>=tmp){right--;}arr[left]=arr[right];//填坑，然后arr[right]成了新的坑while(left<right&&arr[left]<=tmp){left++;}arr[right]=arr[left];//填坑，在挖坑}arr[left]=tmp;//把最后一个坑填上return left;}

3.快速排序的时间复杂度分析

快速排序的时间复杂度比较特殊，它不是很稳定，最坏情况和最好情况我们都要了解。

最好情况

假设有N个元素，且恰好定义的基准，排序好的位置在数组的中间：

        

一共有logN+1层

每一层都有N个元素要被right和left走完，

所以每一层都要执行N此，因此时间复杂度是：

O（fast）=N*(logN+1)=N*logN+N

取最高阶：O（fast）=N*logN

和堆排序的时间复杂度是一样的，不过快速排序实际上要比堆排序快一些，在最好情况下。

最坏情况

什么是最坏情况？

我们可以分离变量，来理解一下，首先对于一个数组进行快速排序，那么他的执行次数至少是N次，因为left=0，right=数组长度-1，即使递归子树，但是每层的子树之和次数也是N

所以每一层的执行次数，永远是N次，那我们只用考虑，啥时候层数是最多的就可以了

我来举个最坏情况的例子：

像这种基准永远都在最最左侧的情况下，是没有右树的，程序会递归N次，每次left，right走的总次数是一个公差为-1，首项为N的等比数列，所以时间复杂度就是有N项，首项为N，公差为-1的等差数列，自然时间复杂度是：

O（slow）=N^2

这种最坏情况可以说就是一个冒泡排序了

总结：

快速排序的时间复杂度是O(n log n)，其中n为待排序数组的长度。快速排序的每次划分操作需要O(n)的时间复杂度，而递归调用的次数为O(log n)，因此总的时间复杂度为O(n log n)。在最坏的情况下，即数组已经有序的情况下，快速排序的时间复杂度为O(n^2)。

空间复杂度分析

实际上快速排序的这三个方法：

定义的变量都是常量级的，是O(1)我们不用管。重要的是，quickHoare方法需要递归，递归要开辟栈帧，所以快速排序的空间复杂度和递归的深度有关。

最优情况时间复杂度为：O(logN)-->每次均等分割

最差情况时间复杂度为：O(N)

如图与时间复杂度最坏情况类似：

4.基于减少递归的优化方法

想要优化快速排序，从时间复杂度分析中，我们直到，关键就 在于如果减少递归次数。

三数取中

核心思路就是，选取三个数中中间大的那个数字，作为key（基准），尽量从中间分割数组，从而减少递归次数。

方式也很简单，写一个getMid方法，返回一个靠中间的元素的下标即可：

private static int getMid(int[] arr,int left,int right){//一定是有效的闭区间int mid=(left+right)/2;//arr[left] arr[right] arr[mid]三个数组返回中间大的}
}

实际上就只有三大种情况：

依据mid的位置来写，就不容易乱了：

    private static int getMid(int[] arr,int left,int right){//一定是有效的闭区间int mid=(left+right)/2;if(arr[left]<arr[right]){if(arr[left]>arr[mid])return left;else if(arr[right]<arr[mid])return right;else return mid;//mid不小于left，也不大于right，那么就返回mid啊}else{//下面的写法逻辑和上面是一模一样的(arr[left])>arr[right]的情况)--》如果有有元素相同，返回任意一个，所以可以不关心“=”的情况if(arr[mid]<arr[right])return right;else if(arr[mid]>arr[left])return left;else return mid;}}

在使用，hoare方法的时候调用getMid方法，来获取基准即可：

private static int partitionHoare(int[] arr,int left,int right){//返回排序好元素的下标int i=left;int mid=getMid(arr,left,right);swap(arr,mid,left);//把获得的基准和最左侧交换，这样好管理，也好理解int stand=arr[left];//基准默认是最左边的元素

/*
下面就和之前的代码一模一样了*/
}

末尾换用直接插入排序

先来将两个引子：

第一个，我们先来看一下这颗树：

一共有7个节点，最后一层就占据了4个，是总结点数的一般还多，如果总结点数更大，这个占比可能更大。

第二个，学过直接插入排序，我们都知道，当一个数组趋近于有序，他的排序速度会很快（时间复杂度是O(n)）

学习了上面的直接快速排序，我们都知道，快排需要像二叉树一样递归进行，也会和第一个引子类似，在最后几层，递归次数非常大，而我们使用的又是递归，在测试用例很大的情况下，很可能出现栈溢出。

所以，能不能这样：

在最后几层我们就不递归了，改用，直接插入排序来代替，虽然直接插入排序最坏情况下，时间复杂度是O(O^2)，但是，实际上在最后几层，整个数组，已经被快速排序排列的差不多了，所以这个思路没有问题。

    private static void _insert(int[] arr,int left,int right){//把直接插入排序中，对0，和数组长度length的限制改成left,right的就可以了for (int i = left+1; i <=right ; i++) {int tmp=arr[i];int j=i-1;for ( ; j >=left ; j--) {if(arr[j]>tmp)arr[j+1]=arr[j];//一直和tmp比较啊啊啊啊啊，只要tmp小，就一直往前找到合适为止else break;//如果arr[j]<=arr[j+1]，那么数组已经“有序了”}arr[j+1]=tmp;//填好以后一个元素}}

如果直接插入排序还没有学的小伙伴可以看一下这个篇博客，有详细介绍：直接插入排序与希尔排序的详解及对比

只要把_insert方法，放到递归的方法中，设置一个条件来调用即可：

 private static void quickHoare(int[] arr,int left,int right){if(left>=right)return;//已经没有排序区间了，直接返回即可if(right-left<6){//如果递归区间小于某一个值，就直接插入排序，对于值的设置，没有严格要求，不要太大就可以_insert(arr,left,right);return;//记得返回，不然还会继续进行下面的程序，去递归}//下面代码，和之前一样，就不展示了
。。。。。。}

优化后快速排序的整体代码：

class TestSort{private static void swap(int[] arr,int a,int b){int t=2;t=arr[a];arr[a]=arr[b];arr[b]=t;}public static void quickSortHoare(int[] arr){quickHoare(arr,0,arr.length-1);}private static void quickHoare(int[] arr,int left,int right){if(left>=right)return;//已经没有排序区间了，直接返回即可if(right-left<6){_insert(arr,left,right);return;//记得返回，不然还会继续进行下面的程序，去递归}//下面这个partionHoare方法可以把基准放到排序好的位置，然后返回基准排好后的下标位置int mid=partitionHoare(arr,left,right);//left和right一定是合法有效的quickHoare(arr,left,mid-1);//递归基准左侧区间quickHoare(arr,mid+1,right);//递归基准右侧区间}private static int partitionHoare(int[] arr,int left,int right){//返回排序好元素的下标int i=left;int mid=getMid(arr,left,right);swap(arr,mid,left);//把获得的基准和最左侧交换，这样好管理，也好理解int stand=arr[left];//基准默认是最左边的元素while(left<right){//先右边下标走while(left<right&&arr[right]>=stand){right--;}while(left<right&&arr[left]<=stand){left++;}//程序到达这里时：arr[right]<stand 而arr[left]>standswap(arr,right,left);            //交换arr[right]和arr[left]}//当程序到达这里，right==left了，此时这两个下标所指的位置，就是arr[i]有序时，因该在的位置swap(arr,i,left);return left;//返回right也是一样的}private static int partitionPit(int[] arr,int left,int right){//左右，都是有效的闭区间下标int tmp=arr[left];//先挖一个坑(在left的位置)，把土放进tmpwhile(left<right){while(left<right&&arr[right]>=tmp){right--;}arr[left]=arr[right];//填坑，然后arr[right]成了新的坑while(left<right&&arr[left]<=tmp){left++;}arr[right]=arr[left];//填坑，在挖坑}arr[left]=tmp;//把最后一个坑填上return left;}private static int getMid(int[] arr,int left,int right){//一定是有效的闭区间int mid=(left+right)/2;if(arr[left]<arr[right]){if(arr[left]>arr[mid])return left;else if(arr[right]<arr[mid])return right;else return mid;//mid不小于left，也不大于right，那么就返回mid啊}else{//下面的写法逻辑和上面是一模一样的(arr[left])>arr[right]的情况)--》如果有有元素相同，返回任意一个，所以可以不关心“=”的情况if(arr[mid]<arr[right])return right;else if(arr[mid]>arr[left])return left;else return mid;}}private static void _insert(int[] arr,int left,int right){//把直接插入排序中，对0，和数组长度length的限制改成left,right的就可以了for (int i = left+1; i <=right ; i++) {int tmp=arr[i];int j=i-1;for ( ; j >=left ; j--) {if(arr[j]>tmp)arr[j+1]=arr[j];//一直和tmp比较啊啊啊啊啊，只要tmp小，就一直往前找到合适为止else break;//如果arr[j]<=arr[j+1]，那么数组已经“有序了”}arr[j+1]=tmp;//填好以后一个元素}}
}

快速排序的稳定性：

不稳定


http://www.ppmy.cn/ops/27253.html

相关文章

操作DOM：性能优化之道

操作DOM：性能优化之道

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…
阅读更多...
Hi3519AV100 处理器⾼速全局快⻔相机

Hi3519AV100 处理器⾼速全局快⻔相机

⾼速全局快⻔相机采⽤ 1英⼨全局快⻔ Sensor&#xff0c;⽀持 H.264/H.265 编码&#xff0c;8 百万 分辨率模式下最⾼帧率可达 50 帧/秒&#xff0c;1080P 模式下最⾼帧率可达 120 帧/秒。主控采⽤ Hi3519AV100 处理器&#xff0c;集成 2 Tops AI 算⼒ NPU &#xff0c;⽀持⼤…
阅读更多...
MobileNetV4 论文学习

MobileNetV4 论文学习

论文地址&#xff1a;https://arxiv.org/abs/2404.10518 代码地址&#xff1a;https://github.com/tensorflow/models/blob/master/official/vision/modeling/backbones/mobilenet.py 解决了什么问题&#xff1f; 边端设备的高效神经网络不仅能带来实时交互的体验&#xff0c…
阅读更多...
LVGL移植

LVGL移植

Lvgl介绍 LVGL是一个开源的图形库&#xff0c;专为嵌入式系统设计。它提供了丰富的图形元素和功能&#xff0c;可以帮助开发者快速构建现代化的用户界面。LVGL具有跨平台的特性&#xff0c;支持多种操作系统和硬件平台&#xff0c;包括ARM Cortex-M&#xff0c;ESP32&#xff…
阅读更多...
Spring 处理 HTTP 请求参数注解

Spring 处理 HTTP 请求参数注解

RequestParam、RequestBody、RequestPart 对比 请求体格式&#xff1a; RequestParam&#xff1a;application/x-www-form-urlencodedRequestBody&#xff1a;application/json、application/xmlRequestPart&#xff1a;multipart/form-data 入参类型&#xff1a; RequestP…
阅读更多...
【yolov8yolov5驾驶员抽烟-打电话-喝水-吃东西检测】

【yolov8yolov5驾驶员抽烟-打电话-喝水-吃东西检测】

YOLO算法DMS驾驶员抽烟-打电话-喝水-吃东西检测数据集 YOLOv8和YOLOv5是深度学习中用于目标检测的先进算法&#xff0c;它们在实时性和准确性方面表现出色&#xff0c;适用于各种视频监控和图像处理应用&#xff0c;包括驾驶员行为监测。这些算法通过单次前向传播即可预测图像…
阅读更多...
探索潜力：中心化交易所平台币的对比分析

探索潜力：中心化交易所平台币的对比分析

核心观点 平台币在过去一年里表现差异显著&#xff1a; 在过去的一年里&#xff0c;只有少数几个平台币如BMX、BGB和MX的涨幅超过了100%。相比之下&#xff0c;由于市值较高&#xff0c;BNB和OKB的涨幅相对较低。 回购和销毁机制在平台币价值中起决定性作用&#xff1a; 像M…
阅读更多...
使用Nuxt3框架搭建基础项目

使用Nuxt3框架搭建基础项目

Nuxt3安装 基础配置: Node.js** - v18.0.0版本以上 , 可以结合fnm工具切换node版本 安装nuxt3命令 打开vscode或者控制台去到项目文件夹输入: npx nuxi@latest init <project-name> 国内执行这行代码，即使科学上网也会有问题 ⚠️ 安装Nuxt3报错 安装过程的报错 Fa…
阅读更多...
最新文章

Copyright @ 2022~2023