(排序6)快速排序(小区间优化,非递归实现)

news/2024/4/19 20:09:33/

TIPS

  1. 快速排序本质上是一个分治递归的一个排序。
  2. 快速排序的时间复杂度是NlogN,这是在理想的情况之下,但是它最坏可以到达N^2。决定快速排序的效率是在单趟排序之后这个key最终落在的位置,越落在中间就越接近二分,越接近2分就越接近满二叉树,越接近二叉树它的深度就更加均匀。深度更加均匀的话,不仅可以防止栈溢出,减少递归的层次,效率上也有提高。
  3. 因此,由此说来,选key是十分关键的。不能一直把数组当中最左边的那个字作为关键值。选key有三数取中与随机数优化版,推荐三数取中。特别是在要排列的那个数组是有序的情况之下,如果用三数取中优化法,那么就可以确保最中间的那个值就是key。
  4. 有了三数取中选key优化,这个快排它的递归深度相对来说都不会特别深。
  5. 之前有关于快排代码回顾:
//交换函数
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//Hoare大佬原始版本
void QuickSort1(int* arr, int left , int right)
{if (left >= right){return;}int begin = left;int end = right;int keyi = left;while (left < right){while (left < right && arr[right] >= arr[keyi]){right--;}while (left < right && arr[left] <= arr[keyi]){left++;}Swap(arr + left, arr + right);}Swap(arr + left, arr + keyi);keyi = left;QuickSort1(arr, begin, keyi - 1);QuickSort1(arr, keyi + 1, end);
}//Hoare大佬原始版本+随机数选key优化
void QuickSort2(int* arr, int left, int right)
{if (left >= right){return;}int begin = left;int end = right;int randi = left + rand() % (right - left);Swap(arr + randi, arr + left);int keyi = left;while (left < right){while (left < right && arr[right] >= arr[keyi]){right--;}while (left < right && arr[left] <= arr[keyi]){left++;}Swap(arr + left, arr + right);}Swap(arr + left, arr + keyi);keyi = left;QuickSort2(arr, begin, keyi - 1);QuickSort2(arr, keyi + 1, end);
}//Hoare大佬原始版本+三数取中选key优化
int GetMidNumi(int* arr, int left, int right)
{int mid = (left + right) / 2;if (arr[mid] < arr[right]){if (arr[left] < arr[mid]){return mid;}else  //arr[left]>arr[mid]{return arr[left] < arr[right] ? left : right;}}else{if (arr[right] > arr[left]){return right;}else{return arr[left] < arr[mid] ? left : mid;}}
}
void QuickSort3(int* arr, int left, int right)
{if (left >= right){return;}int begin = left;int end = right;int midi = GetMidNumi(arr, left, right);Swap(arr + midi, arr + left);int keyi = left;while (left < right){while (left < right && arr[right] >= arr[keyi]){right--;}while (left < right && arr[left] <= arr[keyi]){left++;}Swap(arr + left, arr + right);}Swap(arr + left, arr + keyi);keyi = left;QuickSort3(arr, begin, keyi - 1);QuickSort3(arr, keyi + 1, end);
}//挖坑法+默认三数取中选key优化
void QuickSort4(int* arr, int left, int right)
{if (left >= right){return;}int begin = left;int end = right;int midi = GetMidNumi(arr, left, right);Swap(arr + midi, arr + left);int key = arr[left];int hole = left;while (left < right){while (left < right && arr[right] >= key){right--;}arr[hole] = arr[right];hole = right;while (left < right && arr[left] <= key){left++;}arr[hole] = arr[left];hole = left;}arr[hole] = key;QuickSort4(arr, begin, hole - 1);QuickSort4(arr, hole + 1, end);
}//前后指针法+默认三数取中选key优化
void QuickSort5(int* arr, int left, int right)
{if (left >= right){return;}int begin = left;int end = right;int midi = GetMidNumi(arr, left, right);Swap(arr + midi, arr + left);int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (arr[cur] < arr[keyi]){prev++;Swap(arr + prev, arr + cur);}cur++;}Swap(arr + prev, arr + keyi);keyi = prev;QuickSort5(arr, begin, keyi - 1);QuickSort5(arr, keyi + 1, end);
}

快速排序的小区间优化(假设我原先用前后指针法)

  1. 快速排序实际上还可以继续优化:我们知道快速排序实际上是递归分治这么进行下去的,尤其是当单趟排序完成之后这个key如果一直落在中间的话,那么如果你把每一个递归都给它放出来的话,你会发现它就是一个接近于满二叉树。
  2. 这时候你想象一下,假设我有1万个数,在第一次递归的时候被分成5000与5000,然后再被分成2500,2500。但随着不断的这么进行递归下去,尤其是在最后面末流,比如说递归的区间范围是五个数,然后把五个数这个区间在递归分治分成两个数与两个数,然后对于两个数的区间也在进行递归分治划分,就会发现有点大题小做,还挺麻烦的。你会发现为了让这五个数有序,我们实际上居然递归了六次。
  3. 在每一次分治递归的时候,你这个QuickSort的使命是让left与right这个区间里面的数有序,你用什么方法有序的话都可以,你可以把它继续切分成子问题,然后这么进行下去,让这个区间有序;可以通过直接的方法让他去有序。
  4. 因此也就是说当这个需要排序的区间缩小到一定程度的时候,就可以不再考虑用递归的方式继续分成子问题,然后使得这个区间有序。而是用别的排序方法。
  5. 插入排序是最好的,如果用希尔排序的话,希尔排序针对插入排序的优势主要体现在当数据量很大的时候,这时候我的gap取得很大,就可以让那些大的数尽快的跳到后面。但现在本身的逻辑前提就是说这个区间已经小到一定程度,怎么杀鸡焉用牛刀,根本用不着希尔排序。然后选择排序与冒泡排序的话虽然他们的时间复杂度都与直接插入排序一样N^2,但是之前就有过比较,这两种排序是无法与直接插入排序最终抗衡的。因为对于直接插入排序而言,只要在这个数据段当中,有几部分小段小段是有序的,对于他的优势就非常大。对于堆排也麻烦还要建堆。库函数也是这么优化的。
  6. 然后以理想化的方式来看待,就以一颗满二叉树来看待,如果说把最后一层的递归给他全部消灭掉的话,能够使得总的函数调用次数减少掉一半。
  7. 比如说当整个待排序的数组里面的元素个数(right - left + 1)小于等于十个的时候,这时候就不进行继续递归分治的玩法,还是采用直接插入排序。想一想这样的话就能够减少掉往下面的三层递归(以理想化的满二叉树为例),那么算下来可以减少50%+25%+12.5%即87.5%的递归(以理想化的满二叉树为例),效果贼棒
  8. 然后进行直接插入排序的时候,那个函数传参又是一个很坑的地方。insertSort的第一个参数应该为arr+left
//前后指针法(默认三数取中选key优化)+小区间优化
void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}
}
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}if (right - left + 1 <= 10){InsertSort(arr + left, right - left + 1);return;}int begin = left;int end = right;int midi = GetMidNumi(arr, left, right);Swap(arr + midi, arr + left);int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (arr[cur] < arr[keyi]){prev++;Swap(arr + prev, arr + cur);}cur++;}Swap(arr + prev, arr + keyi);keyi = prev;QuickSort(arr, begin, keyi - 1);QuickSort(arr, keyi + 1, end);
}

快速排序的非递归实现

递归改成非递归有两种方式:1. 直接改成循环。2. 使用栈辅助改循环
在这里插入图片描述

  1. 快排在实际应用当中绝对会有问题,只要是递归,就会有问题。
  2. 递归的真正问题在于:当深度太深的时候,递归是撑不住的。有时候程序本身是没有任何错误与问题的。实际上递归写着好着呢,但是程序就是跑不出来。这时候其实就是一个栈溢出的问题。
  3. 因为递归是有消耗的,这个消耗就是建立函数栈帧。当栈的空间不够你继续去建立函数栈帧,完了栈溢出了。
  4. 递归真正的问题有两个:效率慢一些(有是有,但现阶段影响不大),深度太深会栈溢出。但是release环境下可能会有一定的优化,包括函数栈帧可能变小了等等,release优化非常明显。但是在debug环境下早就撑不住了,但在debug下面不能跑也是个问题啊,我不能调试了啊。
  5. 然后对于快速排序的递归方法进行看待的话,你会发现在一次又一次的递归当中,首先指向数组首元素的那个指针肯定是雷打不动的,当然,数组里面的元素都在不断的发生变化。递归的话主要是那个待处理数组区域的左右区间在不断的发生变化。这一点非常关键。数组的话就这么一个就这么放在内存里面,然后数组里面的那些数字都在不断的发生交换与变化,再进行这么的一个排序。然后递归递归,你仔细去看一看这个递归函数里面记录的到底真正是什么?你会发现就是左右区间。
  6. 然后我现在自己手搓一个栈进行辅助(我不用递归了)。因为我分析出来我已经知道这个递归函数他真正实际上是在记录左右区间,那我就用我自己的一个栈用来记录左右区间。
  7. 当然,就单趟排序而言,与递归函数的单趟排序没有任何的区别。只不过就是说在单趟排序之后,把接下来需要继续处理的数组区间的左右边界(肯定是有左边和右边两组)给他压到栈里面去。
  8. 子区间入栈。根据栈这个数据结构的特性,先进后出,后进先出。然后等会儿要进行下一轮的单趟排序的时候,那我该怎么知道我需要处理哪个数组区域的数据呢?这时候就把栈顶的元素出栈便能够获取到一对左右区间。每次的过程就是:从栈里面取一段区间,单趟排序,将单趟排序后分割的子区间入栈,如果说子区间只有一个值或者不存在就不入栈
  9. 栈的意义就是把区间存起来。
  10. 以前的话单趟排序完成之后就对两个子区间进行分治递归,但现在已经说了分治递归的话,有个潜在的问题就在于可能会发生栈溢出的情况。因此现在当把单趟排序完成之后,就把两个新的子区间给他入栈。然后对于两个新的子区间在入栈之前先进行判断一下,就是说判断这个区间到底值不值得入栈,如果区间不存在或者只有一个值,这段区间我才不要继续对你单趟排序
  11. 虽然说整个过程并不是递归,但是会发现他好像也与递归差不多,因为递归本质上不也在这么干嘛。只是现在不用递归去玩,只是把数据存到栈这个数据结构里面。
  12. 以后但凡就是说递归要改成非递归的话。你就去看一下这个递归函数它的参数到底是什么?参数条件变化的是什么?那么这样的话,栈里面基本上存的就是什么(如果用栈辅助的话)
#include "Stack.h"
void QuickSortNonR(int* arr, int left, int right)
{ST stack;STInit(&stack);STPush(&stack, right);STPush(&stack, left);while (!STEmpty(&stack)){int begin = STTop(&stack);STPop(&stack);int end = STTop(&stack);STPop(&stack);if (begin >= end){continue;}int midi = GetMidNumi(arr, begin, end);Swap(arr + midi, arr + begin);int keyi = begin;int prev = begin;int cur = prev + 1;while (cur <= end){if (arr[cur] < arr[keyi]){prev++;Swap(arr + prev, arr + cur);}cur++;}Swap(arr + keyi, arr + prev);keyi = prev;STPush(&stack, end);STPush(&stack, keyi + 1);STPush(&stack, keyi - 1);STPush(&stack, begin);}STDestroy(&stack);
}

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

相关文章

手写vuex4源码(六)命名空间实现

一、命名空间使用 在子模块对象中添加 namespaced&#xff1a;true&#xff0c;为模块开启命名空间功能&#xff1b; 开启命名空间功能&#xff0c;相当于为每个模块添加独立的作用域&#xff0c;实现模块间状态和事件的隔离&#xff1b; 二、命名空间实现逻辑 在模块注册阶…

【神经网络】tensorflow实验5--数字图像基础

目录 1. 实验目的 2. 实验内容 3. 实验过程 题目一&#xff1a; ① 代码 ② 实验结果 题目二&#xff1a; ① 代码 ② 实验结果 4. 实验小结&讨论题 1. 实验目的 ①了解数字图像基本属性&#xff1b; ②掌握Pillow图像处理库的基本操作。 2. 实验内容 ①使用Pill…

BGP与OSPF混合组网

如图。R1和R2之间是OSPF Area 0,R23和R4之间是OSPF Area 1,R5和R6之间是OSPF Area2。除了R1和R2之间的cost是100,其余链路的cost都是10. AR1/2/3/4/5/6之间通过Loopback口建立IBGP全互联邻居关系,并且都是AS11520,和外部建立EBGP邻居访问100.100.100.1的网络。(不确定图中…

穿戴规范智能识别系统 yolov7

穿戴规范智能识别系统通过yolov7python网络模型AI深度视觉学习算法&#xff0c;穿戴规范智能识别系统对工厂画面中人员穿戴行为自动识别分析&#xff0c;发现现场人员未按照规定穿戴着装&#xff0c;立即抓拍告警。YOLOv7 的发展方向与当前主流的实时目标检测器不同&#xff0c…

(邱维声)高等代数课程笔记:n 元排列

n 元排列 \quad回顾一下&#xff0c;数域 KKK 上的 nnn 元线性方程组解的情况有几种&#xff1f;前面我们通过对增广矩阵作初等行变换化为阶梯形已经解决了这个问题。 \quad但事实上&#xff0c;化完阶梯形后&#xff0c;这个方程组的求解已经完成的差不多了。换言之&#xff0…

Python 小型项目大全 6~10

六、凯撒密码 原文&#xff1a;http://inventwithpython.com/bigbookpython/project6.html 凯撒密码是朱利叶斯凯撒使用的一种古老的加密算法。它通过将字母在字母表中移动一定的位置来加密字母。我们称移位的长度为密钥。比如&#xff0c;如果密钥是 3&#xff0c;那么A变成D&…

关键词数据分析-搜索词和关键词分析工具

要搜索热门关键词获取&#xff0c;可以采用以下几种方法&#xff1a; 使用百度指数&#xff1a;百度指数是一个实用的工具&#xff0c;可用于查看关键词的热度趋势、搜索量等数据。在百度指数中&#xff0c;您可以输入您要搜索的关键词&#xff0c;并查看近期的相关数据。这可以…

【Unity VR开发】结合VRTK4.0:创建一个按钮(Option Button)

语录&#xff1a; 如同天上降魔主&#xff0c;真是人间太岁神。 前言&#xff1a; 选项按钮是一种提供多项选择选项的方法&#xff0c;其中只有一个按钮可以处于激活状态&#xff0c;激活另一个按钮时将确保组中的所有其他按钮都已停用。我们可以使用嵌套在预制件中的预制件来实…

uniapp页面后退时更改页面内容【uniapp如何区分页面是跳转来的还是后退来的】【伸手党福利】

目录应用场景实现目标分析技术难点解决方法另附&#xff1a;自动登录判断跳转页面ps2 这个案例的实际简单的解决方法应用场景 建立一个自动登录的中间页&#xff0c;如果自动登录&#xff0c;则自动跳转到内部应用。如果自动登录失败&#xff0c;则显示用户名密码输入页。 发现…

三、线程状态【3/12】【多线程】

线程的状态3. 线程的状态3.1 观察线程的所有状态3.2 线程状态和状态转移的意义3.3 观察线程的状态和转移3. 线程的状态 3.1 观察线程的所有状态 线程的状态是一个枚举类型 Thread.State public class ThreadState {public static void main(String[] args) {for (Thread.State…

Spring核心概念

一、Spring是什么&#xff1f;如何理解Spring 我们通常所说的Spring,其实也就是Spring Framework &#xff0c;是java圈子里应用非常广泛的一种框架&#xff0c;如果用一句话概括&#xff0c;那就可以说Spring是包含了众多工具方法的IoC容器。 如果需要对这个概述做进一步阐释…

基于神经辐射场NeRF的SLAM方法

随着2020年NeRF[1]的横空出世&#xff0c;神经辐射场方法&#xff08;Neural Radiance Fields&#xff09;如雨后春笋般铺天盖地卷来。NeRF最初用来进行图像渲染&#xff0c;即给定相机视角&#xff0c;渲染出该视角下的图像。NeRF是建立在已有相机位姿的情况下&#xff0c;但在…

Linux kernel中几个文件的作用

apic/vector.c 是 Linux 内核中的一个文件&#xff0c;其中包含用于处理高级可编程中断控制器 (APIC) 上的中断向量的代码。 中断向量是与设备生成的每个中断请求相关联的唯一标识符。 当中断被触发时&#xff0c;CPU使用向量跳转到相应的中断服务程序&#xff08;ISR&#xff…

【数据结构与算法】一、数据结构的基本概念

文章目录一、数据结构的基本概念1.1 数据结构的研究内容1.2 数据类型和抽象数据类型1.3 算法和算法分析1.3.1 算法的时间复杂度1.3.2 算法时间效率的比较1.4 知识回顾一、数据结构的基本概念 1.1 数据结构的研究内容 1.2 数据类型和抽象数据类型 抽象数据类型&#xff08;ADT…

浅谈 如果做微服务了 这个模块怎么去划分?

如果做微服务了 这个模块怎么去划分&#xff1f; 还是高内聚 低耦合的一个思想吧 &#xff0c;单一职责的设计原则&#xff0c;也是一个封装的思想吧&#xff0c; 业务维度&#xff1a; ​ 按照业务的关联程度来决定&#xff0c;关联比较密切的业务适合拆分为一个微服务&…

阿里云linux云服务器 安装指定版本node.js

我们在实例管理中找到自己的服务器 然后点击右侧的 远程连接 接着点击理解登录 进入命令窗口 我们在这上面输入 curl -h阿里云的服务器都还是最好会有 curl的 然后 我们输入 sudo curl -o- https://raw.githubusercontent.com/nvm-sh/nvm/v0.34.0/install.sh | bash下把nv…

CCC 数字钥匙学习笔记 - 车主配对命令

整理了一下CCC组织的汽车数字钥匙Release 3中关于车主配对Owner Paring&#xff0c;过程的APDU指令和数据说明。基本可以算是在车端的角度进行车主配对操作。里面的章节表格编号&#xff0c;都按照CCC数字钥匙Release 3文档中的编号走&#xff0c;方便将来检索对照。 车主配对…

(邱维声)高等代数课程笔记:行列式按一行(列)展开

行列式按一行&#xff08;列&#xff09;展开 例题 1&#xff1a;一般地&#xff0c;设 ∣A∣|A|∣A∣ 是一个三阶行列式&#xff0c;则有 ∣A∣∣a11a12a13a21a22a23a31a32a33∣a11a22a33a12a23a31a13a21a32−a13a22a31−a12a21a33−a11a23a32a11(a22a23−a23a32)−a21(a12a3…

如何在DevOps中进行API生命周期管理?

引言 随着DevOps理念在中国企业当中的普及和发展&#xff0c;中国企业DevOps落地成熟度不断提升&#xff0c;根据中国信通院的数据已有近6成企业向全生命周期管理迈进。而在研发全生命周期管理之中&#xff0c;API管理的地位愈发显得重要。随着API数量的大幅增长&#xff0c;也…

Python的输入与输出

✅作者简介&#xff1a;CSDN内容合伙人、阿里云专家博主、51CTO专家博主、新星计划第三季python赛道Top1&#x1f3c6; &#x1f4c3;个人主页&#xff1a;hacker707的csdn博客 &#x1f525;系列专栏&#xff1a;零基础入门篇 &#x1f4ac;个人格言&#xff1a;不断的翻越一座…