快排三种递归及其优化,非递归和三路划分

个人主页:Lei宝啊 

愿所有美好如期而遇


目录

快排简介:

快排的三种递归实现:

Hoare:

挖坑:

双指针:

小区间优化:

三数取中优化:

快排非递归实现:

快排的三路划分实现:


快排简介:

快速排序,参见: qsort详解及其模拟实现


快排的三种递归实现:

Hoare:

此法乃Hoare大佬所创,我等一个不注意便就掉入陷阱,大坑于代码处自有注释,诸君慢品:

//Hoare版本  right传数组下标
void QuickSort_Binary(int* arr, int left, int right)
{if (left >= right)return;//选定一个数keyi,最好是不大也不小,上面加个三数取中int keyi = left;//快排开始的区间,都是闭区间int begin = left;int end = right;while (begin < end){//一坑在=,若无此,循环不止//二坑在begin < end,若无此,有越界之忧,end或减减不止//三坑在要从右先行,以此保证begin与end相遇时//					二者所指处值小于keyi所指值while (begin < end && arr[end] >= arr[keyi]){end--;}while (begin < end && arr[begin] <= arr[keyi]){begin++;}Swap(&arr[end], &arr[begin]);}Swap(&arr[begin], &arr[keyi]);QuickSort_Binary(arr, left, begin - 1);QuickSort_Binary(arr, begin + 1, right);}

挖坑:

此法则无关左右矣

//挖坑法  传数组下标
void QuickSort_Binary(int* arr, int left, int right)
{if (left >= right)return;int hole = left;int temp = arr[left];//定义这两变量主要是为了区分后面递归时的区间int begin = left;int end = right;while(begin < end){while(begin < end && arr[end] >= temp){end--;}//交换爽啊,赋值的话循环结束后,还要把temp的值赋给hole位置Swap(&arr[hole], &arr[end]);hole = end;while (begin < end && arr[begin] <= temp){begin++;}Swap(&arr[hole], &arr[begin]);hole = begin;}QuickSort_Binary(arr, left, begin - 1);QuickSort_Binary(arr, begin + 1, right);
}

双指针:

//双指针法 传数组下标
void QuickSort_Binary(int* arr, int left, int right)
{if (left >= right)return;int temp = arr[left];int prev = left;int cur = left;while (cur <= right){while (arr[cur] < temp  && ++prev != cur){Swap(&arr[prev], &arr[cur]);}cur++;}//想法大致都是keyi位置的值不动,从下一个位置开始,最后交换keyi位置和停止位置//停止位置的值一定比keyi位置的值要小Swap(&arr[left], &arr[prev]);QuickSort_Binary(arr, left, prev - 1);QuickSort_Binary(arr, prev + 1, right);}

小区间优化:

我们可以发现的是,递归像一座金字塔,越是到下面,递归次数越多,而我们通过计算得知,一颗满二叉树节点数为2^n-1,最后一层节点数为2^(n-1),也就是说,最后三层节点数占到总数的近87.5%,

也就是说,剩余的节点小于15就不要递归了,可以使用插入排序,这个还是比较好的,插入排序参见:插入排序与希尔排序

以Hoare大佬的排序为例:

//Hoare版本  right传数组下标
void QuickSort_Binary(int* arr, int left, int right)
{if (left >= right)return;if(right-left+1 >= 15){//选定一个数keyi,最好是不大也不小,上面加个三数取中int keyi = left;//快排开始的区间,都是闭区间int begin = left;int end = right;while (begin < end){//一坑在=,若无此,循环不止//二坑在begin < end,若无此,有越界之忧,end或减减不止//三坑在要从右先行,以此保证begin与end相遇时//					二者所指处值小于keyi所指值while (begin < end && arr[end] >= arr[keyi]){end--;}while (begin < end && arr[begin] <= arr[keyi]){begin++;}Swap(&arr[end], &arr[begin]);}Swap(&arr[begin], &arr[keyi]);QuickSort_Binary(arr, left, begin - 1);QuickSort_Binary(arr, begin + 1, right);}else{InsertSort(arr,right-left+1);}
}

三数取中优化:

再一个,如果说一个序列已然有序,我们再使用快排就很难受,此时时间复杂度直达O(N^2),所以如果我们加上三数取中,就不会出现最坏情况,但是力扣老贼针对快排,快排的三数取中我们仍要修改,改为随机数取中。

int GetMidNum(int* a, int left, int right)
{int mid = left + (rand() % (right - left));if (a[left] > a[mid]){if (a[mid] > a[right]){return mid;}else if (a[left] > a[right]){return right;}else{return left;}}else{if (a[left] > a[right]){return left;}else if (a[mid] > a[right]){return right;}else{return mid;}}
}

这样我们返回这个中间值坐标后,这样做:

int mid = GetMidNum(arr, left, right);
Swap(&arr[left], &arr[mid]);

 

快排非递归实现:

快排掌握递归并不够,虽然说他的空间复杂度不高,尽管我们有了上述优化,但是仍然难以保证他不会爆栈,所以掌握非递归还是很有必要的。

快速排序的非递归类似于二叉树的前序遍历,我们在这里需要借助于栈,当然队列也可,但是这样的话就类似于二叉树的层序遍历了。

栈和队列参考:栈和队列的实现

二叉树的前序遍历参考:二叉树的几个递归问题

二叉树的层序参考:二叉树的层序遍历及判断完全二叉树

void QuickSortNonR(int* a, int left, int right)
{Stack stack;Init(&stack);Push(&stack, right - 1);Push(&stack, left);while (!Empty(&stack)){int begin = GetTop(&stack);Pop(&stack);int end = GetTop(&stack);Pop(&stack);int mid = SortWay_two(a, begin, end);if (mid + 1 < end){Push(&stack, end);Push(&stack, mid + 1);			}if (begin < mid){Push(&stack, mid);Push(&stack, begin);		}}
}

这里注意栈的特性是先进后出。 

快排的三路划分实现:

在力扣的针对下,有大佬推出了这个算法,使得快排终于能够通过。

我们的快排是大等于或小等于,而三路划分是小的在左,相等于keyi的在中间,大的在右,使得我们直接递归相等数的左边和右边就可。

//快排三路划分
void QuickSort_ThrDiv(int *arr,int left,int right)
{if (left >= right)return;srand((unsigned int)time(NULL));int mid = GetMidNum(arr, left, right);Swap(&arr[left], &arr[mid]);int begin = left;int end = right;int keyi = arr[left];int cur = left + 1;	while (cur <= right){if (arr[cur] < keyi){Swap(&arr[cur], &arr[left]);left++;cur++;}else if (arr[cur] > keyi){Swap(&arr[cur], &arr[right]);right--;}else{cur++;}}QuickSort_ThrDiv(arr, begin, left - 1);QuickSort_ThrDiv(arr, right + 1, end);}

今晚的风,吹得好浪漫~

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

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

相关文章

Ubuntu配置深度学习环境(TensorFlow和pyTorch)

文章目录 一、CUDA安装1.1 安装显卡驱动1.2 CUDA安装1.3 安装cuDNN 二、Anaconda安装三、安装TensorFlow和pyTorch3.1 安装pyTorch3.2 安装TensorFlow2 四、安装pyCharm4.1 pyCharm的安装4.2 关联anaconda的Python解释器 五、VScode配置anaconda的Python虚拟环境 前言&#xff…

一维数组和二维数组的使用(char类型)

目录 导读1. 字符数组1.1 字符数组的创建1.2 字符数组的初始化1.3 不同初始化在内存中的不同1.3.1 strlen测试1.3.2 sizeof测试1.3.3 差异原因 1.4 字符数组的使用 2. 数组越界3. 数组作为函数参数博主有话说 导读 我们在前面讲到了 int 类型的数组的创建和使用&#xff1a; 一…

焕新古文化传承之路,AI为古彝文识别赋能

目录 1 古彝文与古典保护 2 古文识别的挑战 2.1 西文与汉文OCR 2.2 古彝文识别难点 3 合合信息&#xff1a;古彝文保护新思路 3.1 图像矫正 3.2 图像增强 3.3 语义理解 3.4 工程技巧 4 总结 1 古彝文与古典保护 彝文指的是云南、贵州、四川等地的彝族人使用的文字&am…

行为型设计模式——责任链模式

摘要 责任链模式(Chain of responsibility pattern): 通过责任链模式, 你可以为某个请求创建一个对象链. 每个对象依序检查此请求并对其进行处理或者将它传给链中的下一个对象。 一、责任链模式意图 职责链模式&#xff08;Chain Of Responsibility&#xff09; 是一种行为设…

MAC手动修复『已损坏』问题 终端运行命令报错处理

安装一些第三方软件会出现已损坏的报错提醒&#xff0c;需要用命令sudo xattr -rd com.apple.quarantine进行修复&#xff0c;但是终端提示命令错误&#xff0c;怎么版 错误有几种&#xff1a; No module named ‘pkg_resources’ 这是mac电脑上python2&#xff0c;python3并…

mfc140u.dll是什么文件?mfc140u放在哪个文件夹?详细修复教程

今天我想和大家分享一个非常常见的问题——mfc140u.dll丢失的困扰以及解决方法。 首先&#xff0c;让我们来了解一下什么是mfc140u.dll。这是一个非常重要的动态链接库文件&#xff0c;它是Microsoft Foundation Class Library的一个组件。许多软件和游戏都需要这个文件的支持才…

Appium 全新 2.0 全新跨平台生态,版本特性抢鲜体验!

关于Appium V2 Appium V2 beta版本在2021年发布&#xff0c;从2022年1月1号开始&#xff0c;Appium核心团队不会再维护Appium 1.x版本了&#xff0c;所有近期官方发布的平台驱动&#xff08;如Android平台的UIAutomator&#xff0c;IOS平台的XCUITest&#xff09;不再兼容Appi…

Qt多线程实现方式-moveToThread及其注意事项

Qt多线程实现方式-moveToThread及其注意事项 Chapter1 Qt多线程实现方式-moveToThread一、Qt下使用线程主要有两种方法。二、Qt下创建多线程也有两种方法。三、其它问题。 Chapter2 QT多线程接收串口数据1.前言2.功能作用3.软件测试效果4.基本步骤 Chapter3 利用Qt多线程机制实…

面试打底稿⑦ 项目一的第三部分

简历原文 抽查部分 完成路线规划模块选择路线功能&#xff0c;用neo4j这种存储图关系的非关系数据库&#xff0c;实现最短线路规划、最低成本线路规划 设计优化物流信息模块&#xff0c;合理选择数据库、缓存技术&#xff0c;实现数据精简、流量削峰、提高系统可 用性 模拟问答…

Scala第十五章节

Scala第十五章节 1. 递归 2. 案例一: 求阶乘 3. 案例二: 斐波那契数列 4. 案例三: 打印目录文件 scala总目录 文档资料下载

04、EL和JSTL核心技术

目录 1 EL表达式&#xff08;熟悉&#xff09; 1.1 基本概念 1.2 主要功能 1.3 访问内置对象的数据 1.3.1访问方式 1.3.2 执行流程 1.4 访问请求参数的数据 1.5 访问Bean对象的属性 1.5.1 访问方式 1.5.2 主要区别 1.6 访问集合中的数据 1.7 常用的内置对象 …

uboot启动流程-涉及lowlevel_init汇编函数

一. uboot启动流程涉及函数 之前文章简单分析了 uboot启动流程的开始&#xff0c;从链接脚本文件 u-boot.lds 中&#xff0c;我们已经知道了入口点是 arch/arm/lib/vectors.S 文件中的 _start函数。 _start函数&#xff1a;调用了 reset 函数&#xff0c;reset 函数内部&…

1、Kafka 安装与简单使用

第 1 章 Kafka 概述 1.1 定义 Kafka传统定义&#xff1a; Kafka是一个分布式的基于发布/订阅模式的消息队列&#xff08;Message Queue&#xff09;&#xff0c;主要应用于大数据实时处理领域。 Kafka最新定义 &#xff1a; Kafka是 一个开源的 分 布式事件流平台 &#xff08…

《CTFshow-Web入门》10. Web 91~110

Web 入门 索引web91题解总结 web92题解总结 web93题解 web94题解 web95题解 web96题解 web97题解 web98题解 web99题解总结 web100题解 web101题解 web102题解 web103题解 web104题解 web105题解总结 web106题解 web107题解 web108题解 web109题解 web110题解 ctf - web入门 索…

Scala第十四章节

Scala第十四章节 1. 隐式转换和隐式参数介绍 2. 隐式转换 3. 隐式参数 4. 案例: 获取列表元素平均值 scala总目录 文档资料下载

大数据Flink(九十):Lookup Join(维表 Join)

文章目录 Lookup Join(维表 Join) Lookup Join(维表 Join) Lookup Join 定义(支持 Batch\Streaming):Lookup Join 其实就是维表 Join,比如拿离线数仓来说,常常会有用户画像,设备画像等数据,而对应到实时数仓场景中,这种实时获取外部缓存的 Join 就叫做维表 Join。…

10.1 今日任务:select实现服务器并发

#include <myhead.h>#define ERR_MSG(msg) do{\fprintf(stderr, "__%d__:", __LINE__); \perror(msg);\ }while(0)#define PORT 8888 //端口号&#xff0c;范围1024~49151 #define IP "192.168.112.115" //本机IP&#xff0c;ifco…

Qt自定义菜单

Qt开发过程中&#xff0c;弹出菜单时我们一般使用QMenu,但是QMenu都是一条项固定的格式&#xff0c;如查想要自己的设计界面就没法使用默认的Action项了&#xff0c;因此我们得用自定义的QMenu。 本篇介绍使用自定义的QMenu设计出UI。我们使用QWidget QWidgetAction来实现。Q…

Spring注册Bean系列--方法1:@Component

原文网址&#xff1a;Spring注册Bean系列--方法1&#xff1a;Component_IT利刃出鞘的博客-CSDN博客 简介 本文介绍Spring注册Bean的方法&#xff1a;Component。 注册Bean的方法我写了一个系列&#xff0c;见&#xff1a;Spring注册Bean(提供Bean)系列--方法大全_IT利刃出鞘…

前期开发用最内聚环境,最直观简单的方法管理代码

代码稍微一多我们就会思考代码如何去规划和管理&#xff0c;首先想到MVN等管理工具去帮助我们&#xff0c;结果配置了好长时间感觉不是很方便。首先因为没有系统去了解这个工具的使用方法&#xff0c;另外发现IDEA在原本松散的工具之间以插件的形式做了一定的配置&#xff0c;将…