算法：归并排序

算法：归并排序

• • 归并思想
  • 递归法
  • 非递归

    ---

    归并思想

    在讲解归并���序前，我们先看到一个问题：

    对于这样两个有序的数组，如何将它们合并为一个有序的数组？

    在此我们处理这个问题的思路就是：开辟一个新的数组，然后分别安置一个指针在左右数组，利用指针遍历数组，每次对比将比较小的那个元素插入到数组的尾部。

    像这样：

    那么我们要如何利用这个思想，让一个无序的数组有序？

    比如这个数组：

    我们可以这样划分数组：

    将其不断往小份划分，划分到最后一段：

    对于每一个区域，我们可以认为：左边的一个元素是一个有序数组，右边的一个元素是一个有序数组。然后在对其进行一次归并。

    就像这样：

    这样我们又得到了8组有序的数组，我们继续归并：

    以此类推：

    归并排序就是这样一个不断划分子区间，然后进行合并的过程。

    ---

    递归法

    看到不断划分出子区间，毫无疑问这将会是一个递归的过程，而我们将子区间划分到底，再进行处理数据，所以这是同样是一个后序遍历的过程。

    在进行合并数组的时候，我们会需要开辟一个新的数组来存放临时的数据。

    如果每次合并数组时都额外开辟一段空间，就有点浪费时间了，空间是可以重复利用的，所以我们一开始就要开辟一个和原数组等大的空间。后序进行合并操作都在这个拷贝数组中，当合并完成后，再把数组复制回原数组即可。

    那么我们的归并排序一开始要这样写，

    void _MergeSort(int* a, int begin, int end, int* tmp){//归并主体}void MergeSort(int* a, int n){int* tmp = (int*)malloc(sizeof(int) * n);//开辟空间if (tmp == NULL){perror("malloc fali!");return;}_MergeSort(a, 0, n - 1, tmp);//归并主体free(tmp);}

    _MergeSort函数是归并排序的主体函数，它接受一个待排序的数组a、数组的起始位置begin、数组的结束位置end以及一个临时数组tmp。函数中实现了归并排序的核心部分，即将数组a中的元素从位置begin到位置end进行排序。

    MergeSort函数是对_MergeSort函数的封装，它接受一个待排序的数组a和数组的长度n。函数中首先动态分配了一个大小为n的临时数组tmp，用于存放归并时的临时数据，然后调用_MergeSort函数对数组a进行归并排序。排序完成后，释放临时数组tmp的空间。

    接下来我们完成归并主体的代码：

    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, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;//使拷贝的数组与原数组的位置对应while (begin1 if (a[begin1]  n){break;}if (end2 > n){end2 = n - 1;}int j = begin1;while (begin1 if (a[begin1]