数据结构——归并排序

目录

引言

归并排序

1.算法思想

2.算法步骤

3.代码实现

4.复杂度分析

5.算法优化

(1)区间优化

(2)判断区间是否有序

6.非递归实现

7.应用场景

结束语


引言

在学习完 数据结构——快速排序 后,我们接着学习一种高效的排序方法——归并排序

求点赞收藏关注!!!

归并排序

1.算法思想

归并排序的算法思想主要基于分而治之(Divide and Conquer)的策略。这个策略涉及将原始问题分解成较小的、相似的子问题,递归地解决这些子问题,然后将解决方案合并起来以解决原始问题。在归并排序中,这个策略被应用于数组的排序上。

2.算法步骤

  1. 创建临时数组:这一步是确保在归并过程中有足够的空间来暂存排序后的数据,以避免在原数组上进行修改时破坏未排序的数据。

  2. 分解:归并排序的核心在于递归地将数组分解为更小的部分,直到每个部分只包含一个元素或为空。这是通过计算中点 mid 并将数组分为左右两部分来实现的。

  3. 递归调用:对于每个分解得到的子数组段,递归地调用归并排序函数,直到达到基本情况(即子数组段只有一个元素或为空)。这个过程确保了所有子数组段最终都会变得有序。

  4. 归并:当两个相邻的子数组段都已经被排序后,使用两个指针begin1和begin2分别遍历这两个子数组,并将较小的元素依次放入临时数组 tmp 中。这个过程会持续到两个子数组都被完全遍历。

  5. 拷贝回原数组:归并完成后,使用memecpy函数或循环将临时数组 tmp 中的有序数据拷贝回原数组 arr 的对应位置。这一步确保了原数组在递归调用结束后会被更新为有序状态。

  6. 递归完成:随着递归调用的逐层返回,每个子数组段的有序性逐渐扩展到整个数组。当最顶层的递归调用返回时,整个数组 arr 就完成了排序。

看个图可能容易理解一点,像这样:

动图演示:

3.代码实现

void _MergeSort(int* arr, int* tmp, int begin, int end)
{// 如果当前数组段只有一个元素或没有元素,则无需排序,直接返回  if (begin >= end){return;}// 计算中间索引,将数组段分为两半  int mid = (begin + end) / 2;// 递归地对左半部分进行排序  _MergeSort(arr, tmp, begin, mid);// 递归地对右半部分进行排序  _MergeSort(arr, tmp, mid + 1, end);// 归并两个已排序的数组段  // 设置左右两个子数组的起始和结束索引  int begin1 = begin;int end1 = mid;int begin2 = mid + 1;int end2 = end;int index = begin;  // tmp 数组的当前写入位置  // 当两个子数组都有元素时,比较并归并  while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}// 如果左子数组还有剩余元素,直接复制到 tmp  while (begin1 <= end1){tmp[index++] = arr[begin1++];}// 如果右子数组还有剩余元素,直接复制到 tmp  while (begin2 <= end2){tmp[index++] = arr[begin2++];}// 将排序后的数据从 tmp 复制回 arr  memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}// MergeSort 函数的目的是对数组 arr 进行归并排序,n 是数组的长度  
void MergeSort(int* arr, int n)
{// 分配一个临时数组用于归并过程中的数据交换  int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail:");return;}// 调用递归的归并排序函数,对数组进行排序  _MergeSort(arr, tmp, 0, n - 1);free(tmp);tmp = NULL; 
}

4.复杂度分析

时间复杂度:通常情况下,需要递归logN层,每层都需要遍历,因此时间复杂度为O(N logN)。

空间复杂度:通常情况下,需要创建tmp临时数组,因此空间复杂度为O(N)。

5.算法优化

(1)区间优化

当递归调用层数越多时,最后三层的递归调用会浪费大量时间。为了避免这种情况,我们就可以采用小区间使用插入排序的方法。这与我们之前学习快排的情况类似。

代码如下:

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 (tmp < arr[end]){arr[end + 1] = arr[end];--end;}else{break;}}arr[end + 1] = tmp;}
}void _MergeSort(int* arr, int* tmp, int begin, int end)
{// 如果当前数组段只有一个元素或没有元素,则无需排序,直接返回  if (begin >= end){return;}// 小区间优化if (end - begin + 1 < 10){InsertSort(arr + begin, end - begin + 1);}// 计算中间索引,将数组段分为两半  int mid = (begin + end) / 2;// 递归地对左半部分进行排序  _MergeSort(arr, tmp, begin, mid);// 递归地对右半部分进行排序  _MergeSort(arr, tmp, mid + 1, end);int begin1 = begin;int end1 = mid;int begin2 = mid + 1;int end2 = end;int index = begin; while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}} while (begin1 <= end1){tmp[index++] = arr[begin1++];}  while (begin2 <= end2){tmp[index++] = arr[begin2++];}memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
(2)判断区间是否有序

在归并排序合并时,如果两个区间已经有序,即 arr[end1] <= arr[begin2] 时就不需要对其进行归并。

代码如下:

void _MergeSort(int* arr, int* tmp, int begin, int end)
{// 如果当前数组段只有一个元素或没有元素,则无需排序,直接返回  if (begin >= end){return;}// 小区间优化if (end - begin + 1 < 10){InsertSort(arr + begin, end - begin + 1);}// 计算中间索引,将数组段分为两半  int mid = (begin + end) / 2;// 递归地对左半部分进行排序  _MergeSort(arr, tmp, begin, mid);// 递归地对右半部分进行排序  _MergeSort(arr, tmp, mid + 1, end);int begin1 = begin;int end1 = mid;int begin2 = mid + 1;int end2 = end;int index = begin;  if (arr[begin2] < arr[end1]){while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int));} 
}

6.非递归实现

上面都是基于递归实现的归并排序。归并排序也可以使用非递归实现。

归并排序的非递归(迭代)实现主要依赖于循环来分解和合并数组,而不是递归调用。这种方法避免了递归实现中可能产生的调用栈开销,这在处理非常大的数据集时尤为重要,因为递归调用栈的深度可能会成为性能瓶颈或导致栈溢出错误。

非递归实现需要更复杂的索引和边界处理来确保算法能够正确地遍历数组、分解子数组以及合并它们。这是因为非递归实现必须显式地管理归并过程中的每一步,包括确定哪些子数组需要被归并,以及这些子数组在原始数组中的位置。

1. 初始化:

为临时数组tmp分配了与原始数组arr相同大小的内存空间,用于存储归并过程中的中间结果。 

2. 归并过程:

使用一个变量 gap 来控制归并过程中子数组的大小。初始时, gap 被设置为1,表示每个子数组只包含一个元素。 通过一个外层循环, gap 的值在每次迭代后翻倍,直到 gap 大于等于数组的长度 n。这个循环确保了整个数组最终会被归并为一个有序的整体。

3. 遍历和归并子数组:

  • 在外层循环内部,使用一个内层循环来遍历数组arr,每次跳过2 * gap个元素,以处理相邻的、大小为gap的子数组对。
  • 对于每对子数组,计算它们的起始和结束索引(begin1, end1, begin2, end2)。
  • 检查第二组子数组的起始索引 begin2 是否越界。如果是,则跳出内层循环,因为后续的子数组对已经不需要归并了(它们要么已经是有序的单个元素,要么已经在此前的迭代中被归并)。
  • 如果第二组子数组的结束索引 end2 越界,则将其修正为 n - 1 ,以确保不会访问数组的越界元素。
  • 使用一个临时索引 j 来追踪 tmp 数组中当前应该写入的位置。
  • 通过一个内部循环,将两个子数组中的元素逐个比较并复制到 tmp 数组中,直到其中一个子数组的所有元素都被复制完毕。
  • 然后,将剩余的元素(如果有的话)从另一个子数组复制到tmp数组中。
  • 使用 memcpy 函数将归并后的结果从 tmp 数组复制回 arr 数组的相应位置。注意这里复制的长度是 end2 - i + 1 ,它包括了第二个子数组可能因越界而缩短的部分。

来看个图或许好理解很多:

代码实现如下:

void MergeSortNonR(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail:");return;}// gap为每组归并数据的个数,初始化为1  int gap = 1;// 当gap小于数组长度时,继续归并过程while (gap < n){// 遍历数组,每次跳过2*gap个元素// 以处理相邻的、大小为gap的子数组对for (int i = 0; i < n; i += 2 * gap){int begin1 = i;// 计算第一组子数组的结束索引int end1 = i + gap - 1;// 计算第二组子数组的起始索引int begin2 = i + gap;// 计算第二组子数组的结束索引int end2 = i + 2 * gap - 1;//如果第二组的两个索引都越界,这组不需要归并if (begin2 >= n){break;}//如果第二组的begin2没越界//end2越界,则需要修正一下//继续归并if (end2 >= n){end2 = n - 1;}int j = i;while (begin1 <= end1 && begin2 <= end2){// 从两个子数组中取出较小的元素放入tmp数组if (arr[begin1] < arr[begin2]){tmp[j++] = arr[begin1++];}else{tmp[j++] = arr[begin2++];}}// 如果第一组子数组还有剩余元素,将它们复制到tmp数组while (begin1 <= end1){tmp[j++] = arr[begin1++];}// 如果第二组子数组还有剩余元素,将它们复制到tmp数组while (begin2 <= end2){tmp[j++] = arr[begin2++];}memcpy(arr + i, tmp + i, sizeof(int) * (end2 - i + 1));}// 将gap翻倍,为下一轮归并准备更大的子数组gap *= 2;}free(tmp);tmp = NULL;
}

7.应用场景

大数据集排序:当需要处理的数据量非常大时,归并排序由于其稳定的性能和较好的可扩展性,成为一种理想的排序选择。它可以很容易地并行化,以提高在多核处理器上的执行效率。

外部排序:当数据集太大,无法一次性装入内存时,归并排序特别有用。它可以在排序过程中分批次读取数据到内存中,对每批次数据进行排序,然后将排序后的数据写入到外部存储设备(如硬盘)。最后,通过归并这些已排序的数据块来完成整个数据集的排序。

数据库和文件系统的索引构建:在构建数据库或文件系统的索引时,归并排序可以用于对索引条目进行排序,从而加速数据的查找、插入和删除操作。

并发编程:在多线程或分布式系统中,归并排序可以很容易地并行化。每个线程或进程可以独立地排序数据的一部分,然后合并结果。

结束语

本篇博客学习排序中的一重要排序:归并排序。

求点赞收藏评论关注!!!

感谢!!!

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

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

相关文章

stm32之外部flash下载算法

文章目录 下载算法下载到芯片的核心思想算法程序中擦除操作执行流程擦除操作大致流程&#xff1a;算法程序中编程操作执行流程算法程序中校验操作执行流程 创建MDK下载算法通用流程第1步&#xff0c;使用MDK提供好的程序模板第2步&#xff0c;修改工程名第3步&#xff0c;修改使…

值得听歌入手的开放式耳机推荐?分享四款开放式蓝牙耳机

作为网易云十级的耳机重度患者来说&#xff0c;我觉得值得听歌入手的开放式耳机还得是挂耳式的开放式耳机。 因为挂耳式的开放式耳机拥有着不错的佩戴体验&#xff0c;挂耳式的设计还能够牢牢贴合耳廓&#xff0c;而且不用入耳&#xff0c;所以能够保持耳道空气流通&#xff0…

【软件测试】软件测试-----什么是Bug?Bug是如何分级的?Bug的生命周期是怎样的?如何描述一个Bug?

博客目录 一.软件测试的生命周期二.BUG的定义和级别2.1 bug的概念.2.2 如何描述一个bug.2.3bug的级别2.3.1 bug分级的意义.2.3.2 bug的四种级别. 三.BUG的生命周期.四.当与开发人员发生冲突该如何处理(高频面试)五.总结 一.软件测试的生命周期 软件测试贯穿于软件的整个生命周…

出现 TypeError: Cannot read properties of undefined (reading ‘getUserMedia‘) 解决方法

目录 1. 问题所示2. 原理分析3. 解决方法1. 问题所示 调用摄像头的时候出现如下所示: Uncauht (in promise) TypeError: Cannot read properties of undefined (reading getUserMedia)截图如下: 2. 原理分析 TypeError: Cannot read properties of undefined (reading ‘…

NSS题目练习

[SWPUCTF 2022 新生赛]js_sign 打开后先随便填入&#xff0c;点击check&#xff0c;发现出现弹窗&#xff0c;并且尝试抓包抓不到&#xff0c;说明是js前端 查看源码找到js文件 补充&#xff1a; ‌‌ btoa函数是‌JavaScript中的一个全局函数&#xff0c;用于将二进制字符串…

【分享】Excel表格设置“打开密码”的两种方法

在工作中&#xff0c;Excel文件通常包含敏感数据&#xff0c;出于安全性考虑&#xff0c;给文件设置打开密码是非常有效的方式。接下来&#xff0c;小编给大家介绍两种方法&#xff0c;帮助你轻松为Excel文件设置密码。 方法一&#xff1a;在Excel表里设置“打开密码” 这是Ex…

基于yolov8的水面垃圾水面漂浮物检测系统python源码+onnx模型+评估指标曲线+精美GUI界面

【算法介绍】 基于YOLOv8的水面垃圾与漂浮物检测系统是一种高效、智能的监测解决方案。该系统利用YOLOv8这一前沿的深度学习模型&#xff0c;结合智能视频分析技术&#xff0c;对河道、湖泊等水面的垃圾漂浮物进行实时监测与识别。 YOLOv8作为YOLO系列的最新迭代&#xff0c;…

828华为云征文|华为云Flexus云服务器X实例部署Cockpit服务

828华为云征文&#xff5c;华为云Flexus云服务器X实例部署Cockpit笔记工具 前言一、Flexus云服务器X实例介绍1.1 Flexus云服务器X实例简介1.2 Flexus云服务器X实例特点1.3 Flexus云服务器X实例使用场景 二、Cockpit介绍2.1 Cockpit简介2.2 Cockpit特点 三、本次实践介绍3.1 本次…

录屏软件电脑,精选5款录屏神器推荐

嘿&#xff0c;朋友们&#xff01;想象一下&#xff0c;你正在与好友分享你最新的游戏成就&#xff0c;或是与同事展示你的最新项目进展&#xff0c;但却发现文字描述无法完美呈现你的精彩瞬间。别担心&#xff0c;在这个数字化的时代&#xff0c;我们有着无数种方式记录和分享…

计算机网络(一) —— 网络基础入门

目录 一&#xff0c;关于网络 二&#xff0c;协议 2.1 协议是什么&#xff0c;有什么用&#xff1f; 2.2 协议标准谁定的&#xff1f; 2.3 协议分层 2.4 OSI 七层模型 2.5 TCP/IP 四层模型 三&#xff0c;网络传输基本流程 3.1 局域网中两台主机通信* 3.2 报文的封装与…

Hadoop运行jps没有datanode节点【已解决】

1 原因&#xff1a; 格式化NameNode后&#xff0c;如果DataNode的clusterID与新的NameNode的clusterID不匹配&#xff0c;DataNode将无法加入集群&#xff0c;导致HDFS无法正常提供服务。 2 解决方式&#xff1a; 将新的NameNode的clusterID与DataNode的clusterID保持一致 &…

TCP/IP网络编程:Linux实现的web服务器

请求消息&#xff08;Request Message&#xff09; 的结构 这是客户端向服务端发送的请求消息的结构&#xff0c;Web服务器需要解析并响应客户端请求&#xff0c;从图中看出&#xff0c;请求信息包含请求行&#xff0c;消息头&#xff0c;消息体等三个部分&#xff0c;这里我们…

计算机网络 第1章 概述

文章目录 计算机网络概念计算机网络的组成计算机网络的功能三种数据交换技术电路交换&#xff08;Circuit Switching&#xff09;报文交换&#xff08;message&#xff09;分组交换 三种交换方式性能对比计算机网络的分类计算机网络的性能指标性能指标1&#xff1a;速率性能指标…

重磅!微信放开公众号注册限制!只要手机号,不用实名!

重磅&#xff01;微信放开公众号注册限制&#xff01;只要手机号&#xff0c;不用实名&#xff01; 随着移动互联网的发展&#xff0c;微信公众号已经成为了许多个人与企业传递信息、分享内容的首选平台。就在近日&#xff0c;微信官方再次放出大招&#xff1a;公众号注册无需…

Seataf分布式事务的使用

一、事务的四大特征&#xff08;面试题&#xff09; 原子性&#xff1a;一个事务是不可分割的&#xff0c;要不都做&#xff0c;要不都不做一致性&#xff1a;事务必须是使数据库从一个一致性变成另一个一致性状态隔离性&#xff1a;一个事务的执行不被其他事务干扰&#xff0…

开放式耳机对耳朵伤害大吗?开放式耳机值不值得购买?

开放式耳机对耳朵的伤害相对较小。这是因为开放式耳机通常不需要将耳塞插入耳道&#xff0c;因此不会对耳道造成物理压力&#xff0c;也不会因为耳塞堵塞耳道而增加耳内压力&#xff0c;减少了使用耳机时可能对耳膜和耳道造成的损伤风险。同时&#xff0c;由于开放式耳机不会完…

前端请求的路径baseURL怎么来的 ?nodejs解决cors问题的一种方法

背景&#xff1a;后端使用node.js搭建&#xff0c;用的是express 前端请求的路径baseURL怎么来的 &#xff1f; 前后端都在同一台电脑上运行&#xff0c;后端的域名就是localhost&#xff0c;如果使用的是http协议&#xff0c;后端监听的端口号为3000&#xff0c;那么前端请求…

欧科云链OKLink受邀参与WebX ,旗下EaaS助力项目方“弯道超车”

8 月 27 日&#xff0c;作为亚洲顶级区块链行业盛会 WebX 的 side event 之一的 OKJ Night 在东京盛大拉开帷幕&#xff0c;会上正式宣布 OKCoin Japan 升级为 OKJ&#xff0c;进一步以合规的形式推动区块链产业在日蓬勃发展。日本首相为本次活动发来贺电。 OKLink 非常荣幸作为…

Java学习中如何分辨 = 和 == 及其使用方法

在学习Java编程语言时&#xff0c; 和 是两个非常基础的运算符&#xff0c;虽然它们看起来相似&#xff0c;但在语义和应用场景上却有明显的区别。理解并正确使用这两个符号对于编写正确且高效的Java代码至关重要。 1. 运算符&#xff1a;赋值运算符 在Java中是赋值运算符&a…

网恋照妖镜源码搭建教程

文章目录 前言创建网站1.打开网站设置 配置ssl2.要打开强制HTTPS&#xff0c;用宝塔免费的ssl证书即可&#xff0c;也可以使用其他证书&#xff0c;必须是与域名匹配的3.上传文件至根目录进行解压4.解压后&#xff0c;修改文件 sc.php 里面的内容5.其余探索 前言 前俩年很火的…