算法模板:归并排序

简介: 算法模板:归并排序

前言

唤我沈七就好。


往期专栏:

算法模板:快速排序


基本概念

归并排序是一种稳定的排序算法,即相同元素在排序后位置不会发生改变。

快速排序相比,归并排序的时间复杂度妥妥的nlogn


算法思想

归并排序采用的同样是分治的思想,用递归的方式来处理子问题。

但与快速排序算法的执行顺序不同。


归并排序是先递归左右区间,直到分成每个区间左右只有一个元素的时候然后再借用答案数组进行合并,最后再将答案数组复制到原数组当中。


觉得比较抽象的话,可以看下图来帮助理解(图片来源:图解归并排序

14.png


常用模板


伪代码模板


1.确定分界点中间值,将整个区间一分为二
2.递归 两个子区间,直到每个子区间左右的仅有一个元素时开始合并
   因为后面在合并的过程中会将区间排序 
   所以每次递归之后返回的数组区间都是排序好的
3.归并,将左右两个有序序列合并成一个有序序列
   合并方法:双指针
   先创建一个暂时存储答案的temp数组
   同时将放在左右区间的左端点的指针向右移动
   于此同时比较两指针各指向的元素
   将较小的元素放到tmep数组里
   然后较小的元素的指针继续向中间移动
   一位后继续与另一个指针指向的元素比较大小
   再将较小的元素放到tmep数组里
   反复重复这个过程直到某一个区间被全部遍历
   就可以直接将另一个区间的元素按顺序存入到temp数组里面了
   最后在将答案数组复制到原数组中


C++模板


#include<bits/stdc++.h>
using namespace std;
int a[10000];
void merge_sort(int a[],int l , int r)
{
  if(l>=r)return ;
  int temp[100];
  int mid=l+r>>1;
  int k=0,i=l,j=mid+1;
  merge_sort(a,l,mid);
  merge_sort(a,mid+1,r);
  while(i<=mid&&j<=r)
  if(a[i]<=a[j])
  temp[k++]=a[i++];
  else
  temp[k++]=a[j++];
  while(i<=mid)temp[k++]=a[i++];
  while(j<=r)temp[k++]=a[j++];
  for(int i = l,j = 0 ; i <= r ; i ++, j ++)
  a[i]=temp[j];
}
int main()
{
  int n;
  cin>>n;
  for(int i = 0 ; i < n ; i ++)
  cin>>a[i];
  merge_sort(a,0,n-1);
  for(int i = 0 ; i <  n ; i ++)
  cout<<a[i]<<" ";
  return 0;
}


完结散花


ok以上就是对 归并排序 的全部讲解啦,很感谢你能看到这儿。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我,我后期再补充完善。


参考文献


https://www.acwing.com/activity/content/19/


相关文章
|
3月前
|
算法
【算法】前缀和——二维前缀和模板题
【算法】前缀和——二维前缀和模板题
|
25天前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
16 1
|
5月前
|
机器学习/深度学习 算法 搜索推荐
【初阶算法4】——归并排序的详解,及其归并排序的扩展
【初阶算法4】——归并排序的详解,及其归并排序的扩展
【初阶算法4】——归并排序的详解,及其归并排序的扩展
|
29天前
|
存储 搜索推荐 算法
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
|
1月前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
66 0
|
1月前
|
搜索推荐 Java Go
深入了解归并排序算法
深入了解归并排序算法
18 0
|
3月前
|
算法 搜索推荐 Java
算法实战:手写归并排序,让复杂排序变简单!
归并排序是一种基于“分治法”的经典算法,通过递归分割和合并数组,实现O(n log n)的高效排序。本文将通过Java手写代码,详细讲解归并排序的原理及实现,帮助你快速掌握这一实用算法。
41 0
|
3月前
|
数据采集 搜索推荐 算法
【高手进阶】Java排序算法:从零到精通——揭秘冒泡、快速、归并排序的原理与实战应用,让你的代码效率飙升!
【8月更文挑战第21天】Java排序算法是编程基础的重要部分,在算法设计与分析及实际开发中不可或缺。本文介绍内部排序算法,包括简单的冒泡排序及其逐步优化至高效的快速排序和稳定的归并排序,并提供了每种算法的Java实现示例。此外,还探讨了排序算法在电子商务、搜索引擎和数据分析等领域的广泛应用,帮助读者更好地理解和应用这些算法。
37 0
|
4月前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
【7月更文挑战第12天】归并排序是高效稳定的排序算法,采用分治策略。Python 实现包括递归地分割数组及合并已排序部分。示例代码展示了如何将 `[12, 11, 13, 5, 6]` 分割并归并成有序数组 `[5, 6, 11, 12, 13]`。虽然 $O(n log n)$ 时间复杂度优秀,但需额外空间,适合大规模数据排序。对于小规模数据,可考虑其他算法。**
75 4
|
4月前
|
算法 搜索推荐 C#