2020-11-28-归并排序和原地归并
归并排序和原地归并
前言
9月份面试找工作的时候，被中国“排名第三”的互联网公司问到常见排序算法的时间和空间复杂度。其中说到归并排序的时候，面试官问我知不知道原地归并？我一脸懵逼，大意了没有闪，hh虽然最后拿到了offer，但是本着程序猿求知若渴的精神，还是写一下此文和分享一下自己理解的原地归并。
一、什么是归并排序？
在说原地归并之前，先简要介绍一下归并排序。归并排序是冯诺依曼首次提出的一个排序算法，这也是第一个在 最坏情况下时间复杂度可以达到O(nlogn) 的排序算法。算法的主要思想为 分而治之：先将待排序数组从中间一分为二，再对两个子数组分别进行排序，排序以后对两个子数组进行归并从而达到整体有序。下面有一个简单示意图：
由于楼主的技术栈是c++,就用c++代码简单实现一下归并排序：
void Merge(vector<int>&ivNums, int lo, int mid, int hi)
{
vector<int>vHelp(ivNums.begin() + lo, ivNums.begin() + mid);
int i = lo;
int j= mid;
int iIndex = lo;
while (i<mid|| j<hi)
{
if (j >= hi || (i<mid&&vHelp[i-lo] <= ivNums[j]))
{
ivNums[iIndex++] = vHelp[i-lo];
++i;
}
else if (i >= mid || (j<hi&&vHelp[i-lo] > ivNums[j]))
{
ivNums[iIndex++] = ivNums[j++];
}
}
}
void MergeSort(vector<int>&ivNums, int lo, int hi)
{
if (hi - lo < 2)
{
return;
}
int mid = lo + ((hi - lo) >> 1);
MergeSort(ivNums, lo, mid);
MergeSort(ivNums, mid, hi);
Merge(ivNums, lo, mid, hi);
}简单分析一下复杂度。可以看出归并排序时间复杂度的通项公式为T(n) = 2T(n/2) + an，a为常数。即排序n个数时所用时间为排序n/2个数所用时间的两倍并且加上归并的时间，归并的时间从merge函数可以看出是O(n)。根据通项公式推导出归并排序的时间复杂度如下：
所以归并排序在 最好、最坏和平均情况下的时间复杂度均为O(nlogn)。至于空间复杂度，则主要消耗在merge中的help数组和递归数据压栈，数组大小最大为n/2，递归深度最多为logn，所以 空间复杂度为O(n+logn)=O(n)。
二、原地归并
在我面试中满心欢喜的写出归并排序代码并且通过测试以后，又遭到了面试官“无情”的拷问，能不能不用辅助数组？空间复杂度能否是常数？（不考虑递归栈）弱小的我被面试官吊打，猿族人永不为奴，不行得研究清楚什么是原地归并。话不多说，先简要介绍一下原地归并实现，原地归并时只用修改merge函数，主要思路如下：
1.我们令i=lo,j=mid,k=hi：
2.++i，找到第一个arr[i]>arr[j]的索引：
3.++j，再找第一个arr[j]>=arr[i]的索引(取等于是为了保证排序是稳定的）:
4.我们将[i,mid)部分和[mid,j)部分交换，而交换所用的技巧相当于将数组的[i,j)部分进行循环右移j-mid个数字。至此只要是刷过leetcode或者剑指offer的都应该有了思路，可以通过swap函数来实现不需要辅助数组的右移，岂不是有手就行了。
5.交换以后，前i-lo+j-mid个元素已经排好序了，交换以后后面的部分和[j,k)的元素又是两个递增的数组，可以重复前面的步骤，直到全部有序。话不多说，直接开干。
void swapNums(vector<int>&ivNums, int lo, int hi)
{
--hi;
while (lo<hi)
{
swap(ivNums[lo++], ivNums[hi--]);
}
}
void MergeInPlace(vector<int>&ivNums, int lo, int mid, int hi)
{
int i = lo, j = mid;
while (j<hi)//后半部分数组为空时停止循环
{
while (i < j&&ivNums[i] <= ivNums[j])
{
++i;
}
while (j<hi&&ivNums[i] > ivNums[j])
{
++j;
}
//三次swap实现右移
swapNums(ivNums, i, j);
swapNums(ivNums, i, i + j - mid);
swapNums(ivNums, i + j - mid, j);
//重置数字继续迭代
i = i + j - mid;
mid = j;
}
}
void MergeSort(vector<int>&ivNums, int lo, int hi)
{
if (hi - lo < 2)
{
return;
}
int mid = lo + ((hi - lo) >> 1);
MergeSort(ivNums, lo, mid);
MergeSort(ivNums, mid, hi);
MergeInPlace(ivNums, lo, mid, hi);
}可以看出通过swap函数可以避免辅助数组使用，达到原地归并，并且时间复杂度仍然是O(nlogn)。
总结
好好学习，天天向上。
腾讯云开发者
