手撕排序算法4:归并排序及其非递归版本(下)

简介: 手撕排序算法4:归并排序及其非递归版本(下)

二.归并排序非递归版本

1.算法剖析

递归改非递归

1.直接改循环(简单)

2.借助数据结构栈模拟递归过程(复杂一点)

这里我们使用循环的方式来做

大家看一下这张图片

2.代码实现

void MergeSortNonR(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  int gap = 1;//每组需要归并的数据个数,控制每组有多少个
  while (gap < n)
  {
    for (int i = 0; i < n; i += 2 * gap)
    //每一轮for循环都是归并这两组数据
    //[i,i+gap-1]        [i+gap,i+2*gap-1]
     // [begin1,end1]       [begin2,end2] 
     //所以说每次for循环之后i都要从第一组的begin1到第二组的begin1,
     //所以要加2*gap
    //归并到一起
    {
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i + gap, end2 = i + 2 * gap - 1;
      //1.归并过程中右半区间可能就不存在
      if (begin2 >= n)
      {
        break;//此时根本就不用进行归并了
      }
      //2.归并过程中右半区间算多了,修正一下
      if (end2 >= n)
      {
        end2 = n - 1;
      }
      int index = i;
      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++];
      }
      //拷贝回去
      for (int j = i; j <= end2; j++)
      {
        a[j] = tmp[j];
      }
    }
    gap *= 2;
  }
  free(tmp);
}
难点剖析:1.
    for (int i = 0; i < n; i += 2 * gap)
    每一轮for循环都是归并这两组数据
    [i,i+gap-1]        [i+gap,i+2*gap-1]
     [begin1,end1]       [begin2,end2] 
     所以说每次for循环之后i都要从第一组的begin1到第二组的begin1,
     所以要加2*gap
    归并到一起
    2.
      for (int j = i; j <= end2; j++)
      {
        a[j] = tmp[j];
      }
      必须写j<=end2,不能写j<= i + 2 * gap - 1,因为
      //2.归并过程中右半区间算多了,修正一下
      if (end2 >= n)
      {
        end2 = n - 1;
      }
      出现这种情况时我们将边界修正了一下,到那时如果写为
      j<= i + 2 * gap - 1,那就是写死了,导致越界访问了.
    3.  拷贝回去
      for (int j = i; j <= end2; j++)
      {
        a[j] = tmp[j];
      }
要放在上面那个for循环的内部
否则如果放在上面的那个for循环外面,
像这样的话
      for (int j = 0; j <n; j++)
      {
        a[j] = tmp[j];
      }
最外层while循环的里面的话会发生一下这种情况
因为如果放在外面的话,当循环到达4个gap==4且i==0时
| 10 6 7 1 |3 9 4 2|2
我们发现第一轮for循环时左右区间都完整
但是第二轮for循环时不仅右半区间不存在,而且连左半区间都残缺不全
也就是说这个2根本不会拷进tmp临时数组中
tmp临时数组中对应位置存放的是一个随机值
但是我们却在最后进行拷贝,这样就会使得原数组对应位置的这个2被随机值所覆盖,出现错误
4.总之,归并排序的非递归最难的点在于边界的修正和思想
5.因为右半区间的边界需要去时刻准备修正
所以这个归并排序的非递归版本使用栈的话就会很麻烦

3.归并排序的用途

归并排序也叫外排序,还可以对文件中的数据进行排序

只有归并排序才能解决这个问题

假设10G的数据放到硬盘的文件中,要排序,如何排呢?

可能内存不够,假设只有1G的内存可以使用

10G的文件,切分成为10个1G的文件,并且让10个1G的文件有序

依次读文件,每次读1G到内存中形成一个数组,用快排对其进行排序

再写到一个文件中,再继续下一个1G的数据

然后再用归并排序把每个1G的文件逐步归并为一个10G的文件

以上就是归并排序的剖析,希望能对大家有所帮助

相关文章
|
11天前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
28 2
|
1月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
20 1
|
1月前
|
算法 定位技术
数据结构与算法学习九:学习递归。递归的经典实例:打印问题、阶乘问题、递归-迷宫问题、八皇后问题
本文详细介绍了递归的概念、重要规则、形式,并展示了递归在解决打印问题、阶乘问题、迷宫问题和八皇后问题等经典实例中的应用。
40 0
|
1月前
|
存储 搜索推荐 算法
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
|
1月前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
72 0
|
1月前
|
搜索推荐 Java Go
深入了解归并排序算法
深入了解归并排序算法
20 0
|
2月前
|
算法 计算机视觉
Mat未初始化引起拼接算法结果,release版本和debug版本不一致
在OpenCV中由于Mat对象未初始化导致的拼接算法在release版本和debug版本中结果不一致的问题,并提供了通过显式初始化Mat对象为零来解决这一问题的修改方法。
|
26天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
11天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
13天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。