深入理解数据结构第六弹——排序(3)——归并排序

简介: 深入理解数据结构第六弹——排序(3)——归并排序

前言:

在前面,我们已经学习了插入排序、堆排序、快速排序等一系列排序,今天我们来讲解一下另一个很高效的排序方法——归并排序


一、归并排序的思想

归并排序是一种经典的排序算法,它采用了分治法的思想。分治法的核心是“分而治之”,即将一个复杂的问题分解成两个或多个相同或相似的子问题,将这些子问题逐个解决,最后将子问题的解合并以解决原问题。

归并排序的基本思想如下:

  1. 分解(Divide):
  • 将待排序的数组从中间分成两半,递归地对这两半分别进行归并排序。
  • 一直分解,直到每个子数组只包含一个元素,因为一个元素的数组自然是有序的。

2.解决(Conquer):

  • 当分解到最小子问题时,即每个子数组只有一个元素时,开始解决这些小问题。
  • 解决的方式是合并(Merge)两个有序的子数组,从而得到一个更大的有序数组。

3.合并(Merge):


  1. 合并过程是归并排序的关键步骤。它将两个有序的子数组合并成一个有序的数组。
  2. 通常使用两个指针分别指向两个子数组的起始位置,然后比较两个指针所指向的元素,将较小的元素放入结果数组中,并移动该指针。
  3. 重复这个过程,直到一个子数组被完全合并到结果数组中,然后将另一个子数组的剩余元素直接复制到结果数组中。

归并排序的操作如下:

归并操作其实就是将一组数据通过递归等不断划分成两个部分,直到划分到一个元素之后,再对这两部分排序排进一个数组内,相当于把划分的过程再反过来走了一遍,只是走回去的过程中会把数组一步一步的有序化

二、归并排序的递归实现

递归的实现其实是很有意思的,在上面我们已经讲了递归的思想,其实就是不断的重复划分然后排序的过程,所以我们就可以设计一个递归来实现这种,同时,由于每一步都要进行分区划分,所以我们可以封装一个划分函数(_MergeSort函数)在前,重复这个过程


void MergeSort(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
 
  _MergeSort(a, 0, n - 1,tmp);
 
  free(tmp);
}

1、因为我们在划分结束后,需要将各个小的部分再排序成一个有序的大部分,所以我们创建一个tmp的指针指向一个与原数组一样大小的空间,然后每一次排序放进这个空间,最后再把这个空间中的数据复制回原数组


2、其中_MergeSort函数内参数分别为原数组指针,首元素位置,尾元素位置,tmp指针


然后我们就来实现这个分步函数,这个函数的功能就是实现将一个数组不断分为两个部分,当划分成最小单元时,两个两个比较大小,并且放入tmp中,再复制进原数组中,我们先拿数组 { 8 ,7,6,5,4,3,2,1 } 举个例子

实现上述过程的代码如下

//归并排序
void _MergeSort(int* a, int begin,int end,int* tmp)
{
  if (begin == end)
    return;
 
  //小区间优化
  if (end - begin + 1 < 10)
  {
    InsertSort(a + begin, begin - end + 1);
  }
 
  int mid = (begin + end) / 2;
  _MergeSort(a, begin, mid, tmp);
  _MergeSort(a, mid + 1, end, tmp);
  
  int begin1 = begin, end1 = mid;
  int begin2 = mid + 1, end2 = end;
  int i = begin;
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] < a[begin2])
    {
      tmp[i++] = a[begin1];
      begin1++;
    }
    else
      tmp[i++] = a[begin2++];
  }
  while (begin1 <= end1)
  {
    tmp[i++] = a[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[i++] = a[begin2++];
  }
  memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

在这段代码有些部分我们在下面单独讲解一下:

小区间优化是什么及其作用

三、归并排序的非递归实现

学习完归并排序的递归实现后,我们来看一下归并排序的非递归实现


归并排序由于需要不断划分,可想而知其非递归实现是一定需要用到循环的,但是它其实还是有几个很大的坑等着我们的,归并排序的非递归实现要比其递归实现复杂的多


归并排序非递归实现需要注意的点:


1、在上面举的例子中我们都是举的2的n次方的例子,所以能恰好完全归并,但是我们实际排序时也可能遇到排11个数等,这里就比较麻烦了,所以我们需要分情况处理


2、由于上面在循环归并时次数的不确定性,所以我们每一次循环排序结束都要拷贝回原数组

如图,我们在对两个数组进行归并时是要定义两个数组的起始位置的,但是我们可能会遇到下面三种情况:

1、end1>n,即从end1开始就超出数组长度

2、end1<n,begin2>n,即从begin2开始超出数组长度

3、end2>n,即从end2开始才超出数组长度

不管这上面哪一种,都会导致我们之后的归并排序中会有数组落单,所以我们就需要针对这中情况进行处理

针对这种情况我们有两种解决方法:

1、跳出:就是当end1或者begin2大于n时跳出不进行处理

2、优化:就是将end1、begin2、end2进行优化处理,让它能够进行操作

具体操作如下:

1、跳出的思想

//非递归的归并排序(跳出的思想)
void MergeSortNonR(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  int gap = 1;
  while (gap < n)
  {
    gap *= 2;
    int j = 0;
    for (int i = 0; i < n; i += 2 * gap)
    {
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i + gap, end2 = i + gap * 2 - 1;
      
      if (end1 >= n || begin2 >= n)
      {
        break;
      }
      if (end2 >= n)
      {
        end2 = n - 1;
      }
 
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] < a[begin2])
        {
          tmp[j++] = a[begin1++];
        }
        else
        {
          tmp[j++] = a[begin2++];
        }
      }
      
      while (begin1 <= end1)
      {
        tmp[j++] = a[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[j++] = a[begin2++];
      }
 
      memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
    }
  }
  free(tmp);
}

2、优化的思想

//非递归的归并排序(修正的思路)
void MergeSortNonR2(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  int gap = 1;
  while (gap < n)
  {
    gap *= 2;
    int j = 0;
    for (int i = 0; i < n; i += 2 * gap)
    {
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i + gap, end2 = i + gap * 2 - 1;
 
      if (end1 >= n )
      {
        end1 = n - 1;
        begin2 = n;
        end2 = n - 1;
      }
      else if (begin2 >= n)
      {
        begin2 = n;
        end2 = n - 1;
      }
      else if (end2 >= n)
      {
        end2 = n - 1;
      }
 
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] < a[begin2])
        {
          tmp[j++] = a[begin1++];
        }
        else
        {
          tmp[j++] = a[begin2++];
        }
      }
 
      while (begin1 <= end1)
      {
        tmp[j++] = a[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[j++] = a[begin2++];
      }
 
      memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
    }
  }
  free(tmp);
}

四、完整的代码实例

下面我们通过排序数组{ 4,7,1,9,3,6,5,6,8,3,2,0,6 }来检验这三种方法是否成功(递归一种,非递归i两种)

SeqList.h

#include<stdio.h>
//归并排序
void MergeSort(int* a, int n);

test.c

//测试归并排序
void TestMergeSort()
{
  int a[] = { 4,7,1,9,3,6,5,6,8,3,2,0,6 };
  int b[]= { 4,7,1,9,3,6,5,6,8,3,2,0,6 };
  int c[]= { 4,7,1,9,3,6,5,6,8,3,2,0,6 };
  printf("a数组排序前:");
  PrintArray(a, sizeof(a) / sizeof(a[0]));
  MergeSort(a, sizeof(a) / sizeof(a[0]));   //递归法
  printf("a数组排序后(递归法):");
  PrintArray(a, sizeof(a) / sizeof(a[0]));
  printf("\n");
 
  printf("b数组排序前:");
  PrintArray(b, sizeof(b) / sizeof(b[0]));
  MergeSortNonR(b, sizeof(b) / sizeof(b[0]));   //非递归法(跳出法)
  printf("b数组排序后(跳过法):");
  PrintArray(b, sizeof(b) / sizeof(b[0]));
  printf("\n");
 
  printf("c数组排序前:");
  PrintArray(c, sizeof(c) / sizeof(c[0]));
  MergeSortNonR2(c, sizeof(c) / sizeof(c[0]));   //非递归法(修正法)
  printf("c数组排序后(修正法):");
  PrintArray(c, sizeof(c) / sizeof(c[0]));
  printf("\n");
}
int main()
{
  
  TestMergeSort();
  
  return 0;
}

SeqList.c

//归并排序
void _MergeSort(int* a, int begin,int end,int* tmp)
{
  if (begin == end)
    return;
 
  //小区间优化
  if (end - begin + 1 < 10)
  {
    InsertSort(a + begin, begin - end + 1);
  }
 
  int mid = (begin + end) / 2;
  _MergeSort(a, begin, mid, tmp);
  _MergeSort(a, mid + 1, end, tmp);
  
  int begin1 = begin, end1 = mid;
  int begin2 = mid + 1, end2 = end;
  int i = begin;
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] < a[begin2])
    {
      tmp[i++] = a[begin1];
      begin1++;
    }
    else
      tmp[i++] = a[begin2++];
  }
  while (begin1 <= end1)
  {
    tmp[i++] = a[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[i++] = 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);
 
  _MergeSort(a, 0, n - 1,tmp);
 
  free(tmp);
}
//非递归的归并排序(跳出的思想)
void MergeSortNonR(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  int gap = 1;
  while (gap < n)
  {
    int j = 0;
    for (int i = 0; i < n; i += 2 * gap)
    {
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i + gap, end2 = i + gap * 2 - 1;
      
      if (end1 >= n || begin2 >= n)
      {
        break;
      }
      if (end2 >= n)
      {
        end2 = n - 1;
      }
 
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] < a[begin2])
        {
          tmp[j++] = a[begin1++];
        }
        else
        {
          tmp[j++] = a[begin2++];
        }
      }
      
      while (begin1 <= end1)
      {
        tmp[j++] = a[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[j++] = a[begin2++];
      }
 
      memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
    }
    gap *= 2;
 
  }
  free(tmp);
}
//非递归的归并排序(修正的思路)
void MergeSortNonR2(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  int gap = 1;
  while (gap < n)
  {
    int j = 0;
    for (int i = 0; i < n; i += 2 * gap)
    {
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i + gap, end2 = i + gap * 2 - 1;
 
      if (end1 >= n )
      {
        end1 = n - 1;
        begin2 = n;
        end2 = n - 1;
      }
      else if (begin2 >= n)
      {
        begin2 = n;
        end2 = n - 1;
      }
      else if (end2 >= n)
      {
        end2 = n - 1;
      }
 
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] < a[begin2])
        {
          tmp[j++] = a[begin1++];
        }
        else
        {
          tmp[j++] = a[begin2++];
        }
      }
 
      while (begin1 <= end1)
      {
        tmp[j++] = a[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[j++] = a[begin2++];
      }
 
      memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
    }
    gap *= 2;
  }
  free(tmp);
}
//打印数组
void PrintArray(int* a, int n)
{
  for (int i = 0; i < n; i++)
  {
    printf("%d ", a[i]);
  }
  printf("\n");
}

程序运行结果:

五、总结

综合以上,我们其实就可以清楚的认识到归并排序的有趣及其思想,这篇文章并没有将归并排序的时间复杂度和适用场景等问题,我打算在后边写一个总结的文章,将这几种排序放在一起比较,给出他们时间复杂度的快慢和适用场景的不同,敬请期待吧!!!


谢谢各位大佬观看,创作不易,还请各位大佬点赞支持!!!

目录
打赏
0
1
1
0
23
分享
相关文章
C 408—《数据结构》图、查找、排序专题考点(含解析)
408考研——《数据结构》图,查找和排序专题考点选择题汇总(含解析)。
69 29
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
38 10
【C++数据结构——内排序】希尔排序(头歌实践教学平台习题)【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括: - **任务描述**:实现希尔排序算法。 - **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。 - **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。 - **我的通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了代码运行的测试结果。 通过这些内容,读者可以全面了解希尔排序的原理和实现方法。
60 10
|
1月前
|
【C++数据结构——内排序】快速排序(头歌实践教学平台习题)【合集】
快速排序是一种高效的排序算法,基于分治策略。它的主要思想是通过选择一个基准元素(pivot),将数组划分成两部分。一部分的元素都小于等于基准元素,另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序,最终使整个数组有序。(第一行是元素个数,第二行是待排序的原始关键字数据。本关任务:实现快速排序算法。开始你的任务吧,祝你成功!
45 7
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
84 1
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
基数排序是一种稳定的排序算法,通过将数字按位数切割并分配到不同的桶中,以空间换时间的方式实现快速排序,但占用内存较大,不适合含有负数的数组。
60 0
数据结构与算法学习十三:基数排序,以空间换时间的稳定式排序,速度很快。
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
45 1
|
4月前
【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序
【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
蓝桥杯宝藏排序 | 数据结构 | 快速排序 归并排序
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等