当前位置: 首页 > news >正文

[数据结构] 归并排序快速排序 及非递归实现

()标题:[数据结构] 归并排序&&快速排序 及非递归实现

@水墨不写bug


(图片来源于网络)


目录

(一)快速排序

类比递归谋划非递归

快速排序的非递归实现:

(二)归并排序 

归并排序的递归实现:

归并排序的非递归

细节处理:

归并排序的非递归实现:


 

 正文开始:

(一)快速排序

        快速排序一般通过递归来实现,但是递归也有递归的劣势:当递归程度太深,会导致栈溢出的问题,我们在前面的分享中已经讲解了快速排序的递归实现,这里不再赘述,为了便于讲解,直接给出快速排序的递归实现:


int GetRandomKey(vector<int>& nums, int l, int r)
{return nums[rand() % (r - l + 1) + l];
}
void QuickSort(vector<int>& nums,int l,int r)
{//递归出口if (l >= r)return;int key = GetRandomKey(nums,l,r);int left = l - 1, right = r + 1, cur = l;while (cur < right){if (nums[cur] < key)swap(nums[cur++], nums[++left]);else if (nums[cur] == key)cur++;elseswap(nums[--right],nums[cur]);}QuickSort(nums, l, left);QuickSort(nums, right, r);
}

这里给出的快速排序的递归实现是比较完备的优化过的快排,它解决了:

        (1)、key选取不合适导致的分区不平衡的问题。

        (2)、key在数据中重复大量出现的问题。

递归的过程:

        其实通过观察快排的过程,我们会发现之所以在传入参数的时候必须传入左右区间,是因为我们在快排的内部过程中并不确定需要对哪一个区间的数据 进行排序。

        随着递归的进行,函数栈帧逐层开辟,每一层函数栈帧中都存有需要排序的区间的边界值。

每一个函数栈帧都有一个 

        左区间端点值 :l 

        右区间端点值 :r 

递归是在栈区进行的,我们既然需要避免计算机自己的栈区溢出,那么我们为什么不自己模拟一个栈呢?


递归原理:

        通过模拟一个栈,来协助存储左右区间端点值,以此来达到让快排正常进行的目的。

因此,重要的是需要对自己实现的栈精确的控制。


类比递归谋划非递归

        什么时候递归停止?

        当所有递归都返回的时候递归停止——当模拟实现的栈为空的时候停止迭代;

        递归出口的条件设置?

        当递归区间不存在的时候,递归通过return返回到上一层——当递归区间不存在的时候,直接进入下一次迭代,这里就用到了continue;

        如何准确的控制接收的左右区间的端点值?

        通过栈来模拟,需要注意栈的后进先出的特点,push的顺序和pop的顺序是相反的,比如:先push左端点,再push右端点;在top的时候,先取得的是右端点值,pop后,top再取得的是左端点值。

快速排序的非递归实现:

 


void QuickSort_NoR(vector<int>& nums,int l1,int r1)
{stack<int> st;st.push(l1);st.push(r1);while (!st.empty()){int r = st.top();st.pop();int l = st.top();st.pop();if (l >= r)continue;int left = l - 1, right = r + 1, cur = l;int key = GetRandomKey(nums, l, r);while (cur < right){if (nums[cur] < key)swap(nums[cur++], nums[++left]);else if (nums[cur] == key)cur++;elseswap(nums[--right], nums[cur]);}st.push(right);st.push(r);st.push(l);st.push(left);}
}

(二)归并排序 

         归并是一种算法,当归并应用在排序中,实际上的操作就是将两个有序数组合并为一个有序数组的过程。

        归并排序一般通过非递归实现,其核心思想是分治,但是递归的缺点明显,本文上半部分也说明了递归的缺点,因此非递归实现归并有很大意义。

 

 
        时间复杂度:O(N*logN)
        空间复杂度:O(N)
        稳定性:稳定

        归并的缺点:需要O(N)的空间复杂度

我们在实现归并排序的时候,需要注意的是:

(1)、需要一个N个空间的数组辅助进行排序,由于递归次数很多,在递归过程中创建数组代价太大,所以我们在全局来创建一个数组tem,作为辅助,不仅在每一层递归中都可使用,也节省了资源。

(2)、归并的主要过程通过三目运算符处的逻辑实现。

(3)、三目运算符之后,需要再将没有遍历到末尾的数据继续添加到tem末尾即可,此时归并结束。

(4)、最终不要忘了将tem内的数据拷贝回原数组。

归并排序的递归实现:

vector<int> tem(0);
void MergeSort(vector<int>& nums,int l,int r)
{if (l >= r)return;int mid = (r - l) / 2 + l;int cur1 = l, cur2 = mid + 1;MergeSort(nums, l, mid);MergeSort(nums, mid + 1, r);int i = 0;while (cur1 <= mid && cur2 <= r){tem[i++] = nums[cur1] < nums[cur2] ?nums[cur1++] : nums[cur2++];}while (cur1 <= mid)tem[i++] = nums[cur1++];while (cur2 <= r)tem[i++] = nums[cur2++];for (int j = l; j <= r;++j){nums[j] = tem[j - l];}
}
int main()
{vector<int> nums = { 99,0,7,5,44,3,78,653,90,81 };tem.resize(nums.size());Print(nums);MergeSort(nums,0,nums.size()-1);Print(nums);return 0;
}

归并排序的非递归

        想要实现归并的非递归,在整体上需要换一种思路。

        在局部上,归并的逻辑仍然是与递归是一致的;

我们在思考的时候要将问题逐渐拆成一个一个的小问题:

(1)、归并过程:

        将[begin1,end1],[begin2,end2]归并为一个有序的数组,算法本质和步骤和非递归的实现方法完全一致;

(2)、非递归省去了进入递归的过程,而是直接将数组分为多份,每一份有gap个:

        gap开始取1,表示一个数字就是一个区间,这个步骤是数组本身就满足的;

        gap每次*2,表示区间扩大的过程,这样一来gap逐渐扩大,就在思路上完成了归并;

        通过分析,你也知道了最重要的是对区间的左右端点的控制,也就是需要控制好区间的偏移和越界问题。

细节处理:

(1)区间的偏移:

        通过一个循环,循环变量为k,两个区间的开始位置是由k来决定的,用k来控制区间的偏移:由于每次是归并两个数组,所以每次归并完成后,k+=2*gap:

演示(以gap=2为例):

偏移后:(k+=2*gap

(2)区间的越界:

我们上图举的例子是一个特殊情况,数组元素个数刚好够归并需要的元素,如果元素有9个而不是8个,这就需要考虑区间的越界问题了。

当数组的长度更加一般时,会出现区间的越界问题,对于每一个区间端点:

        begin1:由k决定(k< n,所以不可能越界)

        end1:begin1+gap-1,有可能越界;如果越界,数组个数只有一个,则不再归并。

        begin2:begin1+gap,可能越界;如果越界,数组个数只有一个,则不再归并。

        end2:begin1+2*gap-1;可能越界;如果越界,数组个数有两个,修正end2的位置后再归并。

归并排序的非递归实现:


void MergeSort_NoR(vector<int>& nums, int l, int r)
{int n = nums.size();int gap = 1;while (gap < n){for (int k = 0; k < n; k += 2*gap){// 对两组进行归并  [beign1,end1]  [begin2,end2] // 组内宽度gap int begin1 = k, end1 = begin1 + gap - 1;int begin2 = end1 + 1, end2 = begin2 + gap - 1;if (end1 >= n || begin2 >= n)break;if (end2 >= n)end2 = n-1;int i = k;while (begin1 <= end1 && begin2 <= end2)tem[i++] = nums[begin1] < nums[begin2] ?nums[begin1++] : nums[begin2++];while (begin1 <= end1) tem[i++] = nums[begin1++];while (begin2 <= end2) tem[i++] = nums[begin2++];for (int j = k; j <= end2; ++j)nums[j] = tem[j];}gap *= 2;}
}

完~

未经作者同意禁止转载 

相关文章:

[数据结构] 归并排序快速排序 及非递归实现

&#xff08;&#xff09;标题&#xff1a;[数据结构] 归并排序&&快速排序 及非递归实现 水墨不写bug &#xff08;图片来源于网络&#xff09; 目录 (一)快速排序 类比递归谋划非递归 快速排序的非递归实现&#xff1a; &#xff08;二&#xff09;归并排序 归…...

面试题 12. 矩阵中的路径

矩阵中的路径 题目描述示例 题解 题目描述 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 单词必须按照字母顺序&#xff0c;通过相邻的单元格内的字母构成&#xff0…...

钉钉扫码登录第三方

钉钉文档 实现登录第三方网站 - 钉钉开放平台 (dingtalk.com) html页面 将html放在 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><title>登录</title>// jquery<script src"http://code.jqu…...

多GPU系统中的CUDA设备不可用问题

我们在使用多GPU系统时遇到了CUDA设备不可用的问题&#xff0c;详细情况如下&#xff1a; 问题描述&#xff1a; 我们在一台配备有8块NVIDIA GeForce RTX 3090显卡的服务器上运行CUDA程序时&#xff0c;遇到了如下错误&#xff1a; cudaErrorDevicesUnavailable: CUDA-capabl…...

python的列表推导式

文章目录 前言一、解释列表推导式二、在这句代码中的应用三、示例四、使用 for 循环的等价代码总结 前言 看看这一行代码&#xff1a;questions [q.strip() for q in examples["question"]] &#xff0c;问题是最外层的 中括号是做什么的&#xff1f; 最外层的中括…...

类与对象(2)

我们在了解了类的简单创建后&#xff0c;需要对类的创建与销毁有进一步的了解&#xff0c;也就是对于类的构造函数与析构函数的了解。 目录 注意&#xff1a; 构造函数的特性&#xff1a; 析构函数&#xff1a; 注意&#xff1a; 该部分内容为重难点内容&#xff0c;在正常…...

迂回战术:“另类“全新安装 macOS 15 Sequoia beta2 的极简方法

概述 随着 WWDC 24 的胜利闭幕&#xff0c;Apple 平台上各种 beta 版的系统也都“跃跃欲出”&#xff0c;在 mac 上自然也不例外。 本次全新的 macOS 15 Sequoia&#xff08;红杉&#xff09;包含了诸多重磅升级&#xff0c;作为秃头开发者的我们怎么能不先睹为快呢&#xff1…...

如何设计一个秒杀系统,(高并发高可用分布式集群)

设计一个高并发、高可用的分布式秒杀系统是一个非常具有挑战性的任务&#xff0c;需要从架构、数据库、缓存、并发控制、降级限流等多个维度进行考虑。以下是一个典型的秒杀系统设计思路&#xff1a; 1. 系统架构 微服务架构 拆分服务&#xff1a;将系统功能拆分为多个微服务…...

深度优先搜索(所有可达路径)

参考题目&#xff1a;所有可达路径 题目描述 给定一个有 n 个节点的有向无环图&#xff0c;节点编号从 1 到 n。请编写一个函数&#xff0c;找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示。 输入描述 第一行包含两个整数 N&#xff0c;M&…...

如何配置yolov10环境?

本文介绍如何快速搭建起yolov10环境&#xff0c;用于后续项目推理、模型训练。教程适用win、linux系统 yolo10是基于yolo8&#xff08;ultralytics&#xff09;的改进&#xff0c;环境配置跟yolo8几乎一模一样。 目录 第1章节&#xff1a;创建虚拟环境 第2章节&#xff1a;…...

『大模型笔记』GraphRAG:利用复杂信息进行发现的新方法!

GraphRAG:利用复杂信息进行发现的新方法! 文章目录 一. GraphRAG:利用复杂信息进行发现的新方法!1. 将RAG应用于私人数据集2. 整个数据集的推理3. 创建LLM生成的知识图谱4. 结果指标5. 下一步二. 参考文献微软官方推文:https://www.microsoft.com/en-us/research/blog/gra…...

数据结构1:C++实现变长数组

数组作为线性表的一种&#xff0c;具有内存连续这一特点&#xff0c;可以通过下标访问元素&#xff0c;并且下标访问的时间复杂的是O(1)&#xff0c;在数组的末尾插入和删除元素的时间复杂度同样是O(1)&#xff0c;我们使用C实现一个简单的边长数组。 数据结构定义 class Arr…...

C++入门基础篇(下)

目录 6.引用 6.1 引用的特性 6.2 const引用 7.指针和引用的关系 8.内联函数 9.nullptr 6.引用 引⽤不是新定义⼀个变量&#xff0c;⽽是给已存在变量取了⼀个别名&#xff0c;编译器不会为引⽤变量开辟内存空间&#xff0c; 它和它引⽤的变量共⽤同⼀块内存空间。比如&a…...

LabVIEW图像分段线性映射

介绍了如何使用LabVIEW对图像进行分段线性映射处理&#xff0c;通过对特定灰度值区间进行不同的线性映射调整&#xff0c;以优化图像的显示效果。案例中详细展示了如何配置和使用LabVIEW中的图像处理工具&#xff0c;包括设置分段区间、计算映射参数和应用映射函数等步骤。 实…...

Linux开发:进程件通过UDS传递内存文件句柄

Linux开发:进程间通过Unix Domain Socket传递文件描述符-CSDN博客 介绍了通过UDS传递文件描述符 Linux开发:通过memfd_create创建一个内存文件-CSDN博客 介绍了如果创建一个内存文件 将两者相结合,就可以通过UDS传递一块内存文件句柄也就是内存数据 //uds_fd.hpp #pragma …...

Internet Download Manager6.42最新下载器互联网冲浪小能手们!

今天我要来种草一个超级棒的宝贝——Internet Download Manager&#xff08;简称 IDM&#xff09;。这个小家伙简直是下载界的“速度与激情”代言人&#xff0c;让我彻底告别了等待的日子。&#x1f389; IDM马丁正版下载如下: https://wm.makeding.com/iclk/?zoneid34275 …...

Vue 使用Audio或AudioContext播放本地音频

使用Audio 第一种 使用标签方式 <audio src"./tests.mp3" ref"audio"></audio><el-button click"audioPlay()">播放Audio</el-button>audioPlay() {this.$refs.audio.currentTime 0;this.$refs.audio.play();// this.$…...

从数据仓库到数据湖(上):数据湖导论

文章目录 一、什么是数据湖&#xff1f;起源数据湖的特征 二、为什么要用数据湖&#xff1f;三、数据湖与数据仓库的区别数据仓库和数据湖的对比 四、数据湖本质数据存储架构数据处理工具&#xff1a;三类第一类工具第二类工具第三类工具 小结 五、总结六、参考资料 一、什么是…...

Perl 语言开发(六):深入探索 Perl 中的数组与列表操作

目录 1. 数组和列表的基本概念 1.1 数组的定义与特点 1.2 列表的定义与特点 2. 数组的基本操作 2.1 访问数组元素 2.2 数组的长度 2.3 添加和删除元素 2.4 切片操作 2.5 迭代数组 3. 列表的常见操作 3.1 创建和使用列表 3.2 列表的上下文 3.3 列表和数组的转换 3…...

统一视频接入平台LntonCVS视频监控平台具体功能介绍

LntonCVS视频监控平台是一款基于H5技术开发的安防视频监控解决方案&#xff0c;专为全球范围内不同品牌、协议及设备类型的监控产品设计。该平台提供了统一接入管理&#xff0c;支持标准的H5播放接口&#xff0c;使其他应用平台能够快速集成视频功能。无论开发环境、操作系统或…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...