♉️一、前置知识—什么是归并排序
归并排序是一种基于分治思想的排序算法。它将待排序的数组分成两个子数组，对每个子数组进行排序，最后将子数组合并成一个有序的数组。具体来说，归并排序采用递归的方式将数组不断二分，直到每个子数组只有一个元素，然后再将相邻的两个子数组归并成一个有序的数组，然后不断合并，直到最终得到原数组的有序排列，当然你也可以采用非递归的方法，总体的思路都是一样的。与快速排序不同的是，归并排序在每轮排序中都会将数组完全拆分成两个子数组。
♊️二、归并排序
归并排序的思想
归并排序是基于分治思想的一种排序算法，它可以将一个大问题分解成若干个小问题，再通过合并小问题的解来得到大问题的解。
具体来说，归并排序的思想如下：
1.将待排序的数组划分为两个子数组，对每个子数组进行递归排序；
2.将排好序的子数组合并成一个有序的数组。
这一过程可以不断重复，直到将整个数组划分为单个元素的子数组，然后再将其合并成一个有序数组，排序完成。
一图理解~
动图了解~
归并排序的递归实现
归并排序的递归实现步骤如下：
1.如果数组长度为1，直接返回该数组；
2.将数组按中间位置划分成两个子数组，分别对这两个子数组进行递归排序，得到排好序的两个子数组；
3.将排好序的两个子数组合并成一个有序数组，具体方法为创建一个辅助数组，同时遍历两个子数组，比较两个子数组中当前位置的元素，将较小的元素放入辅助数组中；
4.将辅助数组中的元素复制回原数组中。
代码实现：
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.将长度为1的有序子数组两两合并，得到长度为2的有序子数组；
3.重复以上步骤，直到得到一个完整有序的数组。
代码实现：
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. 稳定性：稳定
感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！
