【数据结构】—超级详细的归并排序（含C语言实现）

食用指南：本文在有C基础的情况下食用更佳

🔥这就不得不推荐此专栏了：C语言

♈️今日夜电波：斜陽—ヨルシカ

0:30━━━━━━️💟──────── 3:20
🔄 ◀️ ⏸ ▶️ ☰

💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍

♉️一、前置知识—什么是归并排序

♊️二、归并排序

归并排序的思想

归并排序的递归实现

♒️归并排序的非递归实现（难点）

♋️三、归并排序的特性总结

♉️一、前置知识—什么是归并排序

归并排序是一种基于分治思想的排序算法。它将待排序的数组分成两个子数组，对每个子数组进行排序，最后将子数组合并成一个有序的数组。具体来说，归并排序采用递归的方式将数组不断二分，直到每个子数组只有一个元素，然后再将相邻的两个子数组归并成一个有序的数组，然后不断合并，直到最终得到原数组的有序排列，当然你也可以采用非递归的方法，总体的思路都是一样的。与快速排序不同的是，归并排序在每轮排序中都会将数组完全拆分成两个子数组。

♊️二、归并排序

归并排序的思想

        归并排序是基于分治思想的一种排序算法，它可以将一个大问题分解成若干个小问题，再通过合并小问题的解来得到大问题的解。

        具体来说，归并排序的思想如下：

将待排序的数组划分为两个子数组，对每个子数组进行递归排序；
将排好序的子数组合并成一个有序的数组。

        这一过程可以不断重复，直到将整个数组划分为单个元素的子数组，然后再将其合并成一个有序数组，排序完成。

一图理解~

动图了解~

归并排序的递归实现

归并排序的递归实现步骤如下：

如果数组长度为1，直接返回该数组；
将数组按中间位置划分成两个子数组，分别对这两个子数组进行递归排序，得到排好序的两个子数组；
将排好序的两个子数组合并成一个有序数组，具体方法为创建一个辅助数组，同时遍历两个子数组，比较两个子数组中当前位置的元素，将较小的元素放入辅助数组中；
将辅助数组中的元素复制回原数组中。

代码实现：

void _Mergesort(int* a, int* temp,int begin, int end)
{if (end <= begin)//递归结束条件return;int mid = (begin + end) / 2;//开始二分_Mergesort(a, temp, begin, mid);//左半边_Mergesort(a, temp, mid + 1, end);//右半边//正式的归并操作//分出来的两个数组的下标int begin1 = begin;int end1 = mid;int begin2 = mid + 1;int end2 = end;int index = begin;while(begin1 <= end1 && begin2 <= end2)//归并{if (a[begin1] < a[begin2]){temp[index++] = a[begin1++];}else{temp[index++] = a[begin2++];}}//当其中有一个条件不符合时，跳出循环，但是可能还有数据每遍历完while (begin1 <= end1){temp[index++] = a[begin1++];}while (begin2 <= end2){temp[index++] = a[begin2++];}// 拷贝回原数组memcpy(a + begin, temp + begin, (end - begin + 1) * sizeof(int));//拷贝对应的数据到对应的位置}void Mergesort(int* a, int n)
{int* temp = (int*)malloc(sizeof(int) * n);if (temp == NULL){perror("malloc fail");return;}_Mergesort(a, temp,0,n-1);free(temp);
}

♒️归并排序的非递归实现（难点）

归并排序的非递归实现，也称为迭代实现，采用的是自底向上的方式，

步骤如下：

将原数组按照长度为1的子数组进行划分，每个子数组都是有序的；
将长度为1的有序子数组两两合并，得到长度为2的有序子数组；
重复以上步骤，直到得到一个完整有序的数组。

代码实现：

void MergesortNonR(int* a, int n)
{int* temp = (int*)malloc(sizeof(int) * n);if (temp == NULL){perror("malloc fail");return;}//设置一个gap用于从间距为1开始（也就是最开始的归并），对于数组进行归并操作，然后归并完一遍后让gap*2继续归并，以此类推int gap = 1;while (gap < n)//gap停止的条件，实际上gap在n的一半时就已经排好了{for (int i = 0; i < n; i += 2 * gap){//首先分出要归并的数组int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//以下是处理越界的情况，有些时候当数组会越界// 如果第二组不存在，这一组不用归并了if (begin2 >= n){break;}// 如果第二组的右边界越界，修正一下if (end2 >= n){end2 = n - 1;}//以下的操作就是和递归的操作相同的归并操作int index = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){temp[index++] = a[begin1++];}else{temp[index++] = a[begin2++];}}while (begin1 <= end1){temp[index++] = a[begin1++];}while (begin2 <= end2){temp[index++] = a[begin2++];}// 拷贝回原数组memcpy(a + i, temp + i, (end2 - i + 1) * sizeof(int));}gap *= 2;}free(temp);
}

♋️三、归并排序的特性总结

        1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的

        外排序问题。

        2. 时间复杂度：O(N*logN)

        3. 空间复杂度：O(N)

        4. 稳定性：稳定