常见排序算法之归并排序

目录

一、什么是归并排序

二、递归实现

2.1 思路

2.2 C语言源码

三、非递归实现

3.1 思路

3.2 C语言源码

一、什么是归并排序

归并排序是一种基于分治思想的排序算法。它的基本思想是将原始的待排序序列不断地分割成更小的子序列，直到每个子序列中只有一个元素，然后逐步将这些子序列合并为一个有序的序列。

具体来说，归并排序的操作流程如下：

1. 分割阶段：将待排序序列不断地二分为更小的子序列，直到每个子序列只包含一个元素。
2. 合并阶段：将相邻的子序列两两合并，合并过程中按照大小顺序排列元素，直到所有的子序列合并为一个有序序列。

归并排序由于是自上而下的递归排序，每次合并操作都需要额外的空间来存储临时的序列，因此归并排序的空间复杂度较高。但由于合并操作是稳定的，因此归并排序是一种稳定的排序算法。

归并排序的时间复杂度为 O(nlogn)，其中 n 为待排序序列的长度，因此归并排序在时间上具有较高的效率。由于其稳定性和高效性，归并排序通常被用于需要稳定性的排序场景，或者对于大数据量的排序。

可以看出，归并排序类似于快速排序的思想，都是基于分治法的二叉树思路实现。但是二者存在区别：

• 快速排序是一种类似前序的思路-先排序大区间再排序小区间
• 归并排序是一种类似后序的思路-先排子区间再排大区间最后合并

  这样的区别会体现在代码实现中递归代码的位置上。

  二、递归实现

  2.1 思路

  核心思路：将每个小区间数组在新数组上排序，然后复制回原数组上。重复递归，由小区间到大区间，直至排序完成

  • 考虑单次
    1. 比较逻辑：两个区间分别初始化两个指针指向起始位置，逐个元素遍历比较，按照大小顺序放入新数组中。
    2. 收尾逻辑：区间内或许存在顺序已经排好的序列，比较逻辑结束后将他们放入新数组中
    3. 最后将新数组拷贝到原数组中，一个区间排序完成
    • 考虑递归
      1. 每次计算区间的中点进行二分法
      2. 传入[起始位置，中点] 以及 [中点的下一个位置，结束位置] 进行重复递归
      3. 递归结束的条件是，子区间仅有一个元素（意味着不需要排列）

      注意事项：

      实际写代码的过程中，每次开辟空间的做法大大降低了程序执行的效率。更好的处理方法是：开辟于要排序数组等大的空间，每次小区间复制只需传入区间的起始位置，区间的大小就可以避免空间的重复开辟。

      2.2 C语言源码

      //递归版本void _MergeSort(int* a, int begin, int end, int* tmp){if (begin == end){return;}int mid = (begin + end) / 2;//递归_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);//归并int begin1 = begin;int end1 = mid;int begin2 = mid + 1;int end2 = end;int i = begin;while (begin1