手撕排序算法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的文件

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

相关文章
|
20天前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
14 1
|
20天前
|
算法 定位技术
数据结构与算法学习九:学习递归。递归的经典实例:打印问题、阶乘问题、递归-迷宫问题、八皇后问题
本文详细介绍了递归的概念、重要规则、形式,并展示了递归在解决打印问题、阶乘问题、迷宫问题和八皇后问题等经典实例中的应用。
29 0
|
24天前
|
存储 搜索推荐 算法
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
|
26天前
|
存储 算法 搜索推荐
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
算法进阶之路:Python 归并排序深度剖析,让数据排序变得艺术起来!
65 0
|
27天前
|
搜索推荐 Java Go
深入了解归并排序算法
深入了解归并排序算法
15 0
|
2月前
|
算法 计算机视觉
Mat未初始化引起拼接算法结果,release版本和debug版本不一致
在OpenCV中由于Mat对象未初始化导致的拼接算法在release版本和debug版本中结果不一致的问题,并提供了通过显式初始化Mat对象为零来解决这一问题的修改方法。
|
3月前
|
数据采集 搜索推荐 算法
【高手进阶】Java排序算法:从零到精通——揭秘冒泡、快速、归并排序的原理与实战应用,让你的代码效率飙升!
【8月更文挑战第21天】Java排序算法是编程基础的重要部分,在算法设计与分析及实际开发中不可或缺。本文介绍内部排序算法,包括简单的冒泡排序及其逐步优化至高效的快速排序和稳定的归并排序,并提供了每种算法的Java实现示例。此外,还探讨了排序算法在电子商务、搜索引擎和数据分析等领域的广泛应用,帮助读者更好地理解和应用这些算法。
35 0
|
8天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
26天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于MSER和HOG特征提取的SVM交通标志检测和识别算法matlab仿真
### 算法简介 1. **算法运行效果图预览**:展示算法效果,完整程序运行后无水印。 2. **算法运行软件版本**:Matlab 2017b。 3. **部分核心程序**:完整版代码包含中文注释及操作步骤视频。 4. **算法理论概述**: - **MSER**:用于检测显著区域,提取图像中稳定区域,适用于光照变化下的交通标志检测。 - **HOG特征提取**:通过计算图像小区域的梯度直方图捕捉局部纹理信息,用于物体检测。 - **SVM**:寻找最大化间隔的超平面以分类样本。 整个算法流程图见下图。
|
5天前
|
人工智能 算法 数据安全/隐私保护
基于遗传优化的SVD水印嵌入提取算法matlab仿真
该算法基于遗传优化的SVD水印嵌入与提取技术,通过遗传算法优化水印嵌入参数,提高水印的鲁棒性和隐蔽性。在MATLAB2022a环境下测试,展示了优化前后的性能对比及不同干扰下的水印提取效果。核心程序实现了SVD分解、遗传算法流程及其参数优化,有效提升了水印技术的应用价值。