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

这个 归并排序详解过程 我能吹一辈子!!!

文章目录

  • 归并排序概念
  • 归并排序算法思路
    • 归并排序递归实现
    • 归并排序非递归实现

归并排序概念

1945年,约翰·冯·诺依曼(John von Neumann)发明了归并排序,这是典型的分治算法的应用。

归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。

归并排序算法思路

归并排序算法有两个基本的操作,一个是分,也就是把原数组划分成两个子数组的过程。另一个是治,它将两个有序数组合并成一个更大的有序数组。

1> 将待排序的线性表不断地切分成若干个子表,直到每个子表只包含一个元素,这时,可以认为只包含一个元素的子表是有序表。
2> 将子表两两合并,每合并一次,就会产生一个新的且更长的有序表,重复这一步骤,直到最后只剩下一个子表,这个子表就是排好序的线性表。
在这里插入图片描述

相信大家都知道如何将两个有序序列合为一个有序序列吧:
在这里插入图片描述

那么如何得到有序的子序列呢?当序列分解到只有一个元素或是没有元素时,就可以认为是有序了,这时分解就结束了,开始合并:
在这里插入图片描述

归并排序递归实现

归并排序,从其思想上看就很适合使用递归来实现,并且用递归实现也比较简单。其间我们需要申请一个与待排序列大小相同的数组用于合并过程两个有序的子序列,合并完毕后再将数据拷贝回原数组。

代码示例:

//归并排序(子函数)
void _MergeSort(int* a, int left, int right, int* tmp)
{if (left >= right)//归并结束条件:当只有一个数据或是序列不存在时,不需要再分解{return;}int mid = left + (right - left) / 2;//中间下标_MergeSort(a, left, mid, tmp);//对左序列进行归并_MergeSort(a, mid + 1, right, tmp);//对右序列进行归并int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;//将两段子区间进行归并,归并结果放在tmp中int i = left;while (begin1 <= end1&&begin2 <= end2){//将较小的数据优先放入tmpif (a[begin1] < a[begin2])tmp[i++] = a[begin1++];elsetmp[i++] = a[begin2++];}//当遍历完其中一个区间,将另一个区间剩余的数据直接放到tmp的后面while (begin1 <= end1)tmp[i++] = a[begin1++];while (begin2 <= end2)tmp[i++] = a[begin2++];//归并完后,拷贝回原数组int j = 0;for (j = left; j <= right; j++)a[j] = tmp[j];
}
//归并排序(主体函数)
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int)*n);//申请一个与原数组大小相同的空间if (tmp == NULL){printf("malloc fail\n");exit(-1);}_MergeSort(a, 0, n - 1, tmp);//归并排序free(tmp);//释放空间
}

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

归并排序非递归实现

归并排序的非递归算法并不需要借助栈来完成,我们只需要控制每次参与合并的元素个数即可,最终便能使序列变为有序:
在这里插入图片描述
当然,以上例子是一个待排序列长度比较特殊的例子,我们若是想写出一个广泛适用的程序,必定需要考虑到某些极端情况:

情况一
 当最后一个小组进行合并时,第二个小区间存在,但是该区间元素个数不够gap个,这时我们需要在合并序列时,对第二个小区间的边界进行控制。
在这里插入图片描述

情况二
 当最后一个小组进行合并时,第二个小区间不存在,此时便不需要对该小组进行合并。
在这里插入图片描述

情况三
 当最后一个小组进行合并时,第二个小区间不存在,并且第一个小区间的元素个数不够gap个,此时也不需要对该小组进行合并。(可与情况二归为一类)
在这里插入图片描述

只要把控好这三种特殊情况,写出归并排序的非递归算法便轻而易举了。

代码示例:

//归并排序(子函数)
void _MergeSortNonR(int* a, int* tmp, int begin1, int end1, int begin2, int end2)
{int j = begin1;//将两段子区间进行归并,归并结果放在tmp中int i = begin1;while (begin1 <= end1&&begin2 <= end2){//将较小的数据优先放入tmpif (a[begin1] < a[begin2])tmp[i++] = a[begin1++];elsetmp[i++] = a[begin2++];}//当遍历完其中一个区间,将另一个区间剩余的数据直接放到tmp的后面while (begin1 <= end1)tmp[i++] = a[begin1++];while (begin2 <= end2)tmp[i++] = a[begin2++];//归并完后,拷贝回原数组for (; j <= end2; j++)a[j] = tmp[j];
}
//归并排序(主体函数)
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int)*n);//申请一个与待排序列大小相同的空间,用于辅助合并序列if (tmp == NULL){printf("malloc fail\n");exit(-1);}int gap = 1;//需合并的子序列中元素的个数while (gap < n){int i = 0;for (i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;if (begin2 >= n)//最后一组的第二个小区间不存在或是第一个小区间不够gap个,此时不需要对该小组进行合并break;if (end2 >= n)//最后一组的第二个小区间不够gap个,则第二个小区间的后界变为数组的后界end2 = n - 1;_MergeSortNonR(a, tmp, begin1, end1, begin2, end2);//合并两个有序序列}gap = 2 * gap;//下一趟需合并的子序列中元素的个数翻倍}free(tmp);//释放空间
}

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

http://www.lryc.cn/news/69338.html

相关文章:

  • docker版jxTMS使用指南:自动生成代码
  • 聚观早报 | 小冰启动GPT克隆人计划;ofo创始人在美创业改做咖啡
  • 面试造航母,入职拧螺丝,工资离了个大谱...
  • Python+selenium自动化元素定位防踩坑
  • 【计算机组成原理】实验一
  • 前端022_广告模块_修改功能
  • makefile 学习(3):C++的编译及库文件的生成与链接
  • Ceph crush运行图
  • 【分布族谱】泊松分布和二项分布、正态分布的关系
  • 关于QTreeWidget的setData函数
  • Microsoft Office 2003的安装
  • 使用Spring Boot和Spring Cloud实现多租户架构:支持应用多租户部署和管理
  • 智聚北京!相约全球人力资源数智化峰会
  • 工业缺陷检测数据及代码(附代码)
  • CentOS 安装MongoDB 6.0
  • 美团面试,被拷打了一小时....
  • 017+C语言中函数栈帧的创建与销毁(VS2022环境)
  • 马斯克们叫停 GPT-5,更像是场行为艺术
  • 事务基础知识
  • 国产高性能DSP音频处理芯片的工作原理以及应用领域
  • BEVDet4D 论文学习
  • 【设计模式与范式:创建型】43 | 单例模式(下):如何设计实现一个集群环境下的分布式单例模式?
  • Metal入门学习:绘制渲染三角形
  • python 中常见变量类型
  • SVN使用教程(一)
  • 【5.19】四、性能测试—指标、种类
  • Windows平台上的5种敏捷软件开发(过程)模型
  • 一文实现部署AutoGPT
  • 数值计算 - 误差的来源
  • 【软件测试】5年测试老鸟总结,自动化测试成功实施,你应该知道的...