首页/新闻资讯/正文详情

【分治】归并排序:局部有序到整体有序

发布时间:2026/11/22 2:24:42 来源:云帆数科 栏目:资讯中心
【分治】归并排序:局部有序到整体有序
核心思想先把数组不断二分直到每个子数组只有一个元素再把相邻的有序子数组两两合并最终得到完整的有序数组。1. 问题定义给定长度为n的数组A[0...n-1]要求将数组按非递减顺序排列A[0]≤A[1]≤⋯≤A[n−1] A[0] \le A[1] \le \cdots \le A[n-1]A[0]≤A[1]≤⋯≤A[n−1]示例输入[5, 2, 8, 3, 1, 6, 4] 输出[1, 2, 3, 4, 5, 6, 8]归并排序使用分治思想最好、平均和最坏时间复杂度均为O(n log n)。2. 核心操作合并两个有序数组假设已有两个升序数组左[2, 5, 8] 右[1, 3, 6, 9]由于两个数组内部已经有序最小元素一定在两个数组当前未处理部分的首部。每次比较左右首元素把较小者写入辅助数组。三个指针i指向左区间尚未处理的第一个元素j指向右区间尚未处理的第一个元素k指向辅助数组下一个写入位置。合并步骤步骤比较取出结果数组12与11[1]22与32[1, 2]35与33[1, 2, 3]45与65[1, 2, 3, 5]58与66[1, 2, 3, 5, 6]68与98[1, 2, 3, 5, 6, 8]7左侧已空复制9[1, 2, 3, 5, 6, 8, 9]小的拿出来从数组删掉大的在数组留下继续跟后面的比两个数组共有n个元素每个元素只被处理常数次因此合并时间为O(n)。3. 分治框架归并排序包含三个阶段Divide分解从中点把数组分成左右两半Conquer解决递归地对左右两半排序Combine合并线性合并两个有序子数组。当区间长度为0或1时区间天然有序可以直接返回。是否MergeSort(A, left, right)left right?区间天然有序返回计算 mid递归排序左区间递归排序右区间合并两个有序区间当前区间有序4. 完整执行过程以[5, 2, 8, 3, 1, 6, 4]为例。分解阶段[5, 2, 8, 3, 1, 6, 4] ├── [5, 2, 8, 3] │ ├── [5, 2] │ │ ├── [5] │ │ └── [2] │ └── [8, 3] │ ├── [8] │ └── [3] └── [1, 6, 4] ├── [1, 6] │ ├── [1] │ └── [6] └── [4]合并阶段[5] [2] - [2, 5] [8] [3] - [3, 8] [2, 5] [3, 8] - [2, 3, 5, 8] [1] [6] - [1, 6] [1, 6] [4] - [1, 4, 6] [2, 3, 5, 8] [1, 4, 6] - [1, 2, 3, 4, 5, 6, 8]递归负责制造“局部有序”归并负责把两个局部有序区间变成更大的有序区间。5. 伪代码MERGE-SORT(A, left, right): if left right: return mid left (right - left) / 2 MERGE-SORT(A, left, mid) MERGE-SORT(A, mid 1, right) MERGE(A, left, mid, right) MERGE(A, left, mid, right): i left j mid 1 k left while 左右区间都还有元素: if A[i] A[j]: temp[k] A[i] i else: temp[k] A[j] j k 复制左区间剩余元素 复制右区间剩余元素 将 temp[left...right] 写回 A[left...right]6. C 语言实现下面的实现只申请一次辅助数组供整个递归过程复用。#includestdio.h#includestdlib.h/** * 合并两个有序区间 * A[left...mid] 和 A[mid1...right] */staticvoidmerge(int*A,int*temp,intleft,intmid,intright){intileft;intjmid1;intkleft;while(imidjright){if(A[i]A[j]){// 相等时优先取左侧元素保证稳定性。temp[k]A[i];}else{temp[k]A[j];}}while(imid){temp[k]A[i];}while(jright){temp[k]A[j];}for(intpleft;pright;p){A[p]temp[p];}}staticvoidmergeSortRecursive(int*A,int*temp,intleft,intright){if(leftright){return;}// 防止 left right 发生整数溢出。intmidleft(right-left)/2;mergeSortRecursive(A,temp,left,mid);mergeSortRecursive(A,temp,mid1,right);merge(A,temp,left,mid,right);}/** * 成功返回 1内存分配失败或参数无效返回 0。 */intmergeSort(int*A,intn){if(n1){return1;}if(ANULL){return0;}int*tempmalloc((size_t)n*sizeof(int));if(tempNULL){return0;}mergeSortRecursive(A,temp,0,n-1);free(temp);return1;}测试代码staticvoidprintArray(constint*A,intn){for(inti0;in;i){printf(%d%c,A[i],in-1?\n: );}}intmain(void){intarr1[]{5,2,8,3,1,6,4};intarr2[]{1};intarr3[]{9,8,7,6,5};intarr4[]{3,1,3,-2,0};intn1sizeof(arr1)/sizeof(arr1[0]);intn2sizeof(arr2)/sizeof(arr2[0]);intn3sizeof(arr3)/sizeof(arr3[0]);intn4sizeof(arr4)/sizeof(arr4[0]);if(mergeSort(arr1,n1))printArray(arr1,n1);if(mergeSort(arr2,n2))printArray(arr2,n2);if(mergeSort(arr3,n3))printArray(arr3,n3);if(mergeSort(arr4,n4))printArray(arr4,n4);return0;}输出1 2 3 4 5 6 8 1 5 6 7 8 9 -2 0 1 3 37. 正确性说明可以用数学归纳法证明。基础情况区间长度为0或1时天然有序。归纳假设假设所有长度小于n的数组都能被归并排序正确排序。归纳步骤对于长度为n的数组左右子数组长度都小于n根据归纳假设递归后左右子数组分别有序merge每次选择两个区间中尚未处理的最小元素写入辅助数组的元素始终保持非递减顺序合并结束后整个长度为n的区间有序。因此归并排序能够正确排序任意长度的数组。8. 复杂度分析时间复杂度递推式为T(n)2T(n/2)O(n) T(n) 2T(n/2) O(n)T(n)2T(n/2)O(n)每层所有合并操作共处理n个元素工作量为O(n)每次把规模减半递归树深度为O(log n)总时间为O(n) × O(log n) O(n log n)。情况时间复杂度最好情况O(n log n)平均情况O(n log n)最坏情况O(n log n)即使数组已经有序标准归并排序仍会完成全部拆分与合并。空间复杂度辅助数组O(n)递归栈O(log n)总体空间复杂度O(n)。9. 算法性质性质结论原因原地排序否标准实现需要辅助数组稳定排序是相等时优先取左侧元素最坏时间保证O(n log n)划分方式不依赖输入排列适合链表是链表合并可以通过修改指针完成适合外部排序是可以顺序读取并合并大文件稳定性若两个元素关键字相同排序后仍保持原来的相对次序则算法稳定。排序前[3a, 1, 3b] 排序后[1, 3a, 3b]合并时使用if(A[i]A[j])相等时先取左侧元素因此保持稳定。如果改为可能破坏稳定性。10. 边界情况输入输出说明[][]空数组直接返回[1][1]单元素天然有序[1, 2, 3][1, 2, 3]已排序数组[3, 2, 1][1, 2, 3]逆序数组[2, 2, 1][1, 2, 2]重复元素[-1, 3, -5][-5, -1, 3]负数11. 与其他排序算法对比算法平均时间最坏时间额外空间稳定性选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)通常O(log n)不稳定12. 与逆序对计数的关系归并排序还可以在合并阶段统计逆序对。当右侧当前元素小于左侧当前元素时左区间尚未处理的所有元素都与它构成逆序对因此可以一次增加mid−i1 mid - i 1mid−i1无序数组 ↓ 不断二分 单元素区间天然有序 ↓ 从下向上两两合并 比较左右当前元素 ├─ 左 右取左元素 └─ 左 右取右元素 ↓ 复制剩余元素 ↓ 得到更大的有序区间 ↓ 最终数组有序先递归制造局部有序再利用线性归并得到整体有序递推式为T(n)2T(n/2)O(n)所以时间复杂度为O(n log n)空间复杂度为O(n)

相关推荐

极空间NAS部署道理鱼全栈媒体管理指南
极空间NAS部署道理鱼全栈媒体管理指南

1. 为什么“道理鱼”在极空间NAS上值得专门折腾一次?“道理鱼”这个名字乍一听像某款冷门国产App,但实际它是个在小众音乐爱好者圈子里悄悄发酵了两年的全栈媒体管理工具——不是播放器,不是下载器,而是把本地音乐库、MV视频、有声… · 2026/9/26 13:14:14

安卓逆向工程实战:Apktool解包、Smali修改与APK签名全流程详解
安卓逆向工程实战:Apktool解包、Smali修改与APK签名全流程详解

1. 项目概述:为什么我们需要深入理解Apktool?在安卓应用开发、安全研究乃至日常的玩机折腾中,你或多或少都遇到过需要“窥探”一个APK文件内部结构的场景。可能是想学习某个优秀应用的界面布局实现,可能是需要汉化一个没有提供本地… · 2026/9/26 13:16:11

冲绳科学技术大学院大学研究者们找到了让AI视觉学习更聪明的秘密
冲绳科学技术大学院大学研究者们找到了让AI视觉学习更聪明的秘密

这项由冲绳科学技术大学院大学(OIST)主导的研究,以预印本形式发布于2026年7月,论文编号为arXiv:2607.04044,有兴趣深入了解技术细节的读者可以通过该编号检索完整原文。教一个孩子认识世界,有两种截然不同的… · 2026/9/26 13:14:17

电工证正规证书有哪些?官方报名入口怎么找,证书过期了不知道怎么复审延期
电工证正规证书有哪些?官方报名入口怎么找,证书过期了不知道怎么复审延期

电工证正规证书有哪些?官方报名入口怎么找,证书过期了不知道怎么复审延期 证书过期了不知道怎么复审延期,别急,这几种电工证正规证书你知道吗?别等用到时才后悔没早办。 电工证正规证书有哪些?有哪些是国家认可的? 电工证正规证书有哪些… · 2026/11/22 2:23:45

在哪里可以学好电工证 全国通用电工证怎么考最稳妥
在哪里可以学好电工证 全国通用电工证怎么考最稳妥

在哪里可以学好电工证 全国通用电工证怎么考最稳妥 工地太忙根本没时间复习考试,这是很多一线电工的真实写照。尤其是像驻马店这样的水利工程集中区域,施工周期紧、任务重,很多工人连吃饭的时间都不够,更别说抽出时间来学习、复习电工证考试内容。但现实… · 2026/11/22 2:23:45

襄阳何处可考电工证 上岗必备怎么考才不白费钱
襄阳何处可考电工证 上岗必备怎么考才不白费钱

襄阳何处可考电工证 上岗必备怎么考才不白费钱 怕考不过白交培训费?襄阳电工证报考前你必须知道的真相,别再踩坑了! 你有没有遇到过这种情况:花了几千块培训费,考试还是没过,心里既心疼又着急?这在襄阳电工证报考人群中并不罕见。很多人因为信息不对… · 2026/11/22 2:23:45

电工证大概学习的内容 上岗必备的实操与理论全解析
电工证大概学习的内容 上岗必备的实操与理论全解析

电工证大概学习的内容 上岗必备的实操与理论全解析 你现在找工作卡在哪儿了?是不是因为 特种作业证 还没到手,连面试机会都摸不着?别急,今天咱们就从最基础的开始聊起—— 电工证大概学习的内容 ,搞懂这些,你就能顺利拿到 上岗必备… · 2026/11/22 2:23:45

低压电工证考点在哪里郑州报考避坑指南
低压电工证考点在哪里郑州报考避坑指南

低压电工证考点在哪里郑州报考避坑指南 证书过期了不知道怎么复审延期,是不是你最近的烦心事?低压电工证作为特种作业人员的“上岗通行证”,一旦过期就等于失去执业资格,不仅影响收入,还可能被单位辞退甚至面临法律风险。尤其是在郑州,建筑、制造、电力… · 2026/11/22 2:23:45

工地太忙根本没时间复习考试,怎样办中级电工证还能拿电子证书
工地太忙根本没时间复习考试,怎样办中级电工证还能拿电子证书

工地太忙根本没时间复习考试,怎样办中级电工证还能拿电子证书 工地太忙根本没时间复习考试,这话说的像极了我们一线电工的真实写照。项目赶工期、任务重,每天连喘口气的时间都没有,更别说抽出时间复习中级电工证的考试内容了。但现实是, 中级电工证… · 2026/11/22 2:22:44

平价的电工证查询保姆级教程:别被中介坑,一步步教你搞定
平价的电工证查询保姆级教程:别被中介坑,一步步教你搞定

平价的电工证查询保姆级教程:别被中介坑,一步步教你搞定 你是不是也经常在网上看到“平价的电工证查询”这样的关键词,但又不知道去哪报名,怕被中介坑?特别是像你这样的平顶山学员,既想考个正规电工证,又怕花冤枉钱走弯路。别担心,这篇保姆级教程就是… · 2026/11/22 0:00:42

麻阳考电工证在哪里考内部消息你知道吗
麻阳考电工证在哪里考内部消息你知道吗

麻阳考电工证在哪里考内部消息你知道吗 不知道去哪报名怕被中介坑, 内部消息 告诉你,麻阳考电工证不一定要去外地,本地其实也有正规渠道,但很多人因为不了解流程和资质,反而被坑了钱还考不到证。今天我就从一个干了这么多年特种作业培训的“老江湖”角… · 2026/11/22 0:00:43

揭阳普宁电工证换证怎么操作?良心建议帮你理清流程
揭阳普宁电工证换证怎么操作?良心建议帮你理清流程

揭阳普宁电工证换证怎么操作?良心建议帮你理清流程 之前考的证在外省能不能转过来?这是很多已经在外地工作、现在想回揭阳普宁发展的电工朋友最关心的问题。如果你也是其中之一,那这篇文章就是为你们量身定制的,从换证流程到避坑建议,良心建议全给你讲透… · 2026/11/22 0:00:43

平价的电工证查询保姆级教程:别被中介坑,一步步教你搞定
平价的电工证查询保姆级教程:别被中介坑,一步步教你搞定

平价的电工证查询保姆级教程:别被中介坑,一步步教你搞定 你是不是也经常在网上看到“平价的电工证查询”这样的关键词,但又不知道去哪报名,怕被中介坑?特别是像你这样的平顶山学员,既想考个正规电工证,又怕花冤枉钱走弯路。别担心,这篇保姆级教程就是… · 2026/11/22 0:00:42

麻阳考电工证在哪里考内部消息你知道吗
麻阳考电工证在哪里考内部消息你知道吗

麻阳考电工证在哪里考内部消息你知道吗 不知道去哪报名怕被中介坑, 内部消息 告诉你,麻阳考电工证不一定要去外地,本地其实也有正规渠道,但很多人因为不了解流程和资质,反而被坑了钱还考不到证。今天我就从一个干了这么多年特种作业培训的“老江湖”角… · 2026/11/22 0:00:43

揭阳普宁电工证换证怎么操作?良心建议帮你理清流程
揭阳普宁电工证换证怎么操作?良心建议帮你理清流程

揭阳普宁电工证换证怎么操作?良心建议帮你理清流程 之前考的证在外省能不能转过来?这是很多已经在外地工作、现在想回揭阳普宁发展的电工朋友最关心的问题。如果你也是其中之一,那这篇文章就是为你们量身定制的,从换证流程到避坑建议,良心建议全给你讲透… · 2026/11/22 0:00:43

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/21 15:19:37

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/21 15:19:30

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/21 15:19:32

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码