[数据结构 -- 手撕排序算法第七篇] 递归实现归并排序

简介: [数据结构 -- 手撕排序算法第七篇] 递归实现归并排序

1、归并的思想

这是我们第二次了解归并的思想了,第一次在我们之前的链表oj题里面,合并两个有序链表,我们当时解题的思想就是归并的思想。
我们这次来系统的学习一下归并的思想(本篇以升序为例展开):


归并两个数组(链表)时,我们使用两个指针指向不同的数组首元素,控制并遍历两个数组,比较两个指针指向的值,小的我们放入开辟的临时数组里面,然后让指向小值的指针往后走一步,继续比较。不断去比,总有一个数组先被遍历完,由于是有序数组,另外那个没有被遍历完的数组直接连接到临时数组的后面就完成了排序。


我们画图来理解这个思想:



2、归并排序的思想

2.1 基本思想

归并排序是建立在归并操作上的一种有效的排序算法。


1.归并排序的思想是,将一个数组二分为左右两个数组,然后对左右两个数组继续进行二分,直到分为的子区间为一个数据的时候,这一个数据一定是有序的,便不再二分。


2.接下来就对左右两个子区间进行排序合并,不断排序合并,最终就实现了整个数组的排序。

2.2 图解分析


我们归并的时候不是直接在原数组上就交换的,直接在原数组上操作会产生覆盖,导致错误。因此我们是malloc一个与原数组大小相同的空间tmp,将每次合并后的值拷贝到tmp中,合并一次拷贝一次,最中tmp数组为有序,再将tmp使用memcpy拷贝回原数组,再free(tmp) (防止内存泄漏),整个排序就完成了。

3、归并排序递归版本代码实现

// 归并排序递归实现
// 时间复杂度:O(N*logN)
// 空间复杂度:O(N + logN)
void _MergeSort(int* a, int begin, int end, int* tmp)
{
  if (begin >= end)
    return;
  int mid = (begin + end) / 2;
  //[begin, mid] [mid+1, end]
  _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++];
    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);
  if (NULL == tmp)
  {
    perror("malloc fail:");
    return;
  }
  _MergeSort(a, 0, n-1, tmp);
  free(tmp);
}

3.1 代码解析


我们在这一段使用了递归,递归的思想就是二分,将数组分为左右两个区间,然后再对左右两个区间继续进行二分,当 begin >= end 时,就是最小的区间,然后我们就进行排序+合并。

这一段就是排序+合并,我们对两个子区间进行排序+合并,思路就是我们归并的思想。这里要注意,我们tmp的下标是begin,因为我们需要将每一层合并的值先放进tmp中,然后再拷贝到原数组里,如果是0,拷贝回去的时候就会出现错误。

3.2 注意事项

在划分左右区间的时候一定是 [begin, mid],[mid+1, end],

不能是 [begin, mid-1],[mid, end]!!!
这里很容易出错,看着逻辑上没问题,但是在排序的时候就会出问题。

3.2.1错误划分:[begin, mid-1],[mid, end]



3.2.2 正确划分:[begin, mid], [mid+1, end]


总结:造成第一种划分死循环的原因是,当我们 mid = begin+end/2 时,计算器是向下取整的,所以一旦向下取整的时候,我们的区间就要包含mid这个值,这样就会补上向下取整造成的舍去。

4、归并排序的测试

void Print(int* a, int n)
{
  for (int i = 0; i < n; i++)
  {
    printf("%d ", a[i]);
  }
  printf("\n");
}
void _MergeSort(int* a, int begin, int end, int* tmp)
{
  if (begin >= end)
    return;
  int mid = (begin + end) / 2;
  // [begin, mid] [mid+1, end]
  _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++];
    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);
  if (NULL == tmp)
  {
    perror("malloc fail:");
    return;
  }
  _MergeSort(a, 0, n - 1, tmp);
  free(tmp);
}
void test()
{
  int a[] = { 6,3,2,1,5,7,9 };
  Print(&a, sizeof(a) / sizeof(int));
  MergeSort(&a, sizeof(a) / sizeof(int) - 1);
  Print(&a, sizeof(a) / sizeof(int));
}
int main()
{
  test();
  return 0;
}

测试结果:



5、时间复杂度、空间复杂度分析

5.1 时间复杂度

归并排序区间不断二分,时间复杂度为O(logN);然后再合并,时间复杂度为O(N)。

整体的时间复杂度为o(N*logN)。

5.2 空间复杂度

因为我们开辟了一个临时空间用于排序,因此空间复杂度O(N)。

相关文章
|
3月前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
97 1
|
4月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
126 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
17天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
79 29
|
17天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
72 25
|
17天前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
58 23
|
22天前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
1月前
|
存储 人工智能 算法
【C++数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】
本关任务是实现二路归并算法,即将两个有序数组合并为一个有序数组。主要内容包括: - **任务描述**:实现二路归并算法。 - **相关知识**: - 二路归并算法的基本概念。 - 算法步骤:通过比较两个有序数组的元素,依次将较小的元素放入新数组中。 - 代码示例(以 C++ 为例)。 - 时间复杂度为 O(m+n),空间复杂度为 O(m+n)。 - **测试说明**:平台会对你编写的代码进行测试,提供输入和输出示例。 - **通关代码**:提供了完整的 C++ 实现代码。 - **测试结果**:展示代码运行后的排序结果。 开始你的任务吧,祝你成功!
36 10
|
1月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
51 2
|
3月前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
111 33
|
3月前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?

热门文章

最新文章