归并算法:分治而治的高效算法大揭秘(图文详解)

简介: 归并算法:分治而治的高效算法大揭秘(图文详解)

📋 前言

归并算法是我们算法中最常见的算法之一,其思想非常巧妙。本身归并是只能归并有序数组但是当我们利用了二路归并分治法之后,就可以使用归并的思想来帮我们排序其算法性能属于第一梯队。

一、什么是归并排序

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

1.1 归并的核心思想

归并的思想大家都知道就是俩个有序数组的数据进行比较,如果 数组一的数据小 就把它插入到我们的新数组里面:

  • 当一个数组比较完后直接把另一个还没比较完的有序数组数组插入到新数组就归并完了

🔥 注:归并的前提是俩个数组都是有序的。

1.2 归并排序的图文解析

那么我们无序数组想要排成有序的改怎么办,这时就有人提出了分治的思想把每个数组的数据都看为一个有序数组,在进行归并

先递归进行分割然后再利用递归返回的特性来进行,回溯归并这样就可以达成俩个有序数组合并

二、归并排序的实现

归并的思想讲完了,以上就是归并排序的全部过程了,诶这样大家是不是理解起来更方便了,既然是归并那么必须就需要一个另一个空间来存放数据:

  • 而我们需要归并的数组就是原数组所递归分割我区间每次归并完了之后在复制
  • 回原数组,这样就能从归并一个数据到整个数组的数据了;

-

2.1 实现代码

好滴思路捋清楚了,代码实现就简单首先我们需要开辟一个和排序数组一模一样大的空间那么就 malloc 一个但是我们需要递归分割所以肯定不能再这个函数里面进行递归这时就需要:

  • _MergeSort 来进行递归分割排序数组
  • 剩下的注意好每次分割的区间和,每次归并完了复制到原数组就好了

🍸 代码演示:

void _MergeSort(int* a, int* tmp, int begin, int end)
{
  if (end <= begin)
    return;
  int mid = (begin + end) / 2;
  //[begin, mid-1] [mid, end]
  _MergeSort(a, tmp, begin, mid);
  _MergeSort(a, tmp, mid+1, end);
  //开始归并
  int begin1 = begin, end1 = mid;
  int begin2 = mid + 1, end2 = end;
  int index = begin;
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] < a[begin2])
    {
      tmp[index++] = a[begin1++];
    }
    else
    {
      tmp[index++] = a[begin2++];
    }
  }
  while (begin1 <= end1)
  {
    tmp[index++] = a[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[index++] = a[begin2++];
  }
  memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
// 归并排序递归实现
void MergeSort(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int)*n);
  if (tmp == NULL)
  {
    perror("malloc file");
    exit(-1);
  }
  _MergeSort(a, tmp, 0, n-1);
  free(tmp);
}

这里每次的区间都是数组的区间,只要分割好了,那么就照着思路写下去就好了

三、归并排序的总结

总体来说归并排序的性能还是非常好的采取的是拿空间换时间的概念,归并排序的思考更多的是解决在磁盘中的外排序问题。

  1. 归并的缺点在于需要O(N)的空间复杂度
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(N)
  4. 稳定性:稳定

📝文章结语:

看到这里了还不给博主扣个:
⛳️ 点赞🍹收藏 ⭐️ 关注

💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖

拜托拜托这个真的很重要!

你们的点赞就是博主更新最大的动力!

有问题可以评论或者私信呢秒回哦。

目录
相关文章
|
4月前
|
算法 开发者 Python
惊呆了!Python算法设计与分析,分治法、贪心、动态规划...这些你都会了吗?不会?那还不快来学!
【7月更文挑战第10天】探索编程巅峰,算法至关重要。Python以其易读性成为学习算法的首选。分治法,如归并排序,将大问题拆解;贪心算法,如找零问题,每步求局部最优;动态规划,如斐波那契数列,利用子问题解。通过示例代码,理解并掌握这些算法,提升编程技能,面对挑战更加从容。动手实践,体验算法的神奇力量吧!
70 8
|
4月前
|
算法 Python
算法不再难!Python分治法、贪心、动态规划实战解析,轻松应对各种算法挑战!
【7月更文挑战第8天】掌握Python算法三剑客:分治、贪心、动态规划。分治如归并排序,将大问题拆解递归解决;贪心策略在每步选最优解,如高效找零;动态规划利用子问题解,避免重复计算,解决最长公共子序列问题。实例展示,助你轻松驾驭算法!**
67 3
|
18天前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
10 0
|
3月前
|
搜索推荐 算法
十大排序算法-快排-希尔-堆排-归并-冒泡-桶排-选择-插入-计数-基数
十大排序算法-快排-希尔-堆排-归并-冒泡-桶排-选择-插入-计数-基数
十大排序算法-快排-希尔-堆排-归并-冒泡-桶排-选择-插入-计数-基数
|
3月前
|
算法 搜索推荐
算法设计 (分治法应用实验报告)基于分治法的合并排序、快速排序、最近对问题
这篇文章是关于分治法应用的实验报告,详细介绍了如何利用分治法实现合并排序和快速排序算法,并探讨了使用分治法解决二维平面上的最近对问题的方法,包括伪代码、源代码实现及时间效率分析,并附有运行结果和小结。
|
4月前
|
搜索推荐 C++ Python
Python排序算法大PK:归并VS快速,谁才是你的效率之选?
【7月更文挑战第13天】归并排序** 使用分治法,稳定且平均时间复杂度O(n log n),适合保持元素顺序和并行处理。
31 5
|
4月前
|
算法 Python
Python算法高手进阶指南:分治法、贪心算法、动态规划,掌握它们,算法难题迎刃而解!
【7月更文挑战第10天】探索Python算法的精华:分治法(如归并排序)、贪心策略(如找零钱问题)和动态规划(解复杂问题)。通过示例代码揭示它们如何优化问题解决,提升编程技能。掌握这些策略,攀登技术巅峰。
103 2
|
4月前
|
算法 程序员 Python
算法小白到大神的蜕变之路:Python分治法、贪心、动态规划,一步步带你走向算法巅峰!
【7月更文挑战第9天】探索算法之旅,以Python解锁编程高手之路。分治法如二分查找,将复杂问题拆解;贪心算法解决活动选择,每次选取局部最优;动态规划求斐波那契数列,避免重复计算,实现全局最优。每一步学习,都是编程能力的升华,助你应对复杂挑战,迈向算法大师!
46 1
|
4月前
|
存储 算法 Python
Python算法界的秘密武器:分治法巧解难题,贪心算法快速决策,动态规划优化未来!
【7月更文挑战第9天】Python中的分治、贪心和动态规划是三大关键算法。分治法将大问题分解为小问题求解,如归并排序;贪心算法每步选局部最优解,不保证全局最优,如找零钱;动态规划存储子问题解求全局最优,如斐波那契数列。选择合适算法能提升编程效率。
64 1
|
4月前
|
存储 算法 Python
震撼!Python算法设计与分析,分治法、贪心、动态规划...这些经典算法如何改变你的编程世界!
【7月更文挑战第9天】在Python的算法天地,分治、贪心、动态规划三巨头揭示了解题的智慧。分治如归并排序,将大问题拆解为小部分解决;贪心算法以局部最优求全局,如Prim的最小生成树;动态规划通过存储子问题解避免重复计算,如斐波那契数列。掌握这些,将重塑你的编程思维,点亮技术之路。
70 1