归并排序
约 544 个字 47 行代码 预计阅读时间 2 分钟
把原问题“把n个元素排成升序”,分解成“把前\frac n2个排成升序”和“把后\frac n2个排成升序”两个子问题,然后合并这两个问题的解
Q1:为什么是分成两半?
A1:分成两半使问题规模缩小一半,这样从 n 的规模缩小到 1 的规模,只花了 \log_2 n 次,这也是复杂度中 \log_2 n 的来源
Q2:处理斐波那契数列时,终止状态是 n\le 2 时,返回1,那么归并排序如何处理终止状态?
A2:当问题规模缩小到 1 时,长度为 1 的数组自然是升序的,所以不用处理,直接返回即可
Q3:如何合并子问题?
A3:此时问题是两个升序序列合并,两个序列从头开始,谁首元素小,谁就放到前面,当一个序列遍历完,另一个序列全部放到末尾
实现¶
int TmpArray[N];
void Merge(int Lpos,int Rpos,int RightEnd)
{
int st=Lpos,LeftEnd=Rpos-1,TmpPos=Lpos;
while(Lpos<=LeftEnd && Rpos<=RightEnd)
{
if(a[Lpos]<=a[Rpos])
TmpArray[TmpPos++]=a[Lpos++];
else
TmpArray[TmpPos++]=a[Rpos++];
}
while(Lpos<=LeftEnd)
TmpArray[TmpPos++]=a[Lpos++];
while(Rpos<=RightEnd)
TmpArray[TmpPos++]=a[Rpos++];
for(;st<=RightEnd;--RightEnd)
a[RightEnd]=TmpArray[RightEnd];
}
void MSort(int left,int right)
{
if(left>=right)
return;
int center=(left+right)/2;
MSort(left,center);
MSort(center+1,right);
Merge(left,center+1,right);
}
void MergeSort()
{
MSort(0,n-1);
}
归并排序求逆序对的数量¶
逆序对:若 i<j,a_i>a_j,则称 a_i,a_j 是一个逆序对
合并序列时,对于后半序列第 i 个元素,将要合并时,前半序列比他小的元素个数已知
long long ans=0;
void Merge(int Lpos,int Rpos,int RightEnd)
{
...
while(Lpos<=LeftEnd && Rpos<=RightEnd)
{
if(a[Lpos]<=a[Rpos])
TmpArray[TmpPos++]=a[Lpos++];
else
{
TmpArray[TmpPos++]=a[Rpos++];
ans+=LeftEnd-Lpos+1;
}
}
...
}
cdq分治比较难,这里不作介绍
归并排序复杂度分析¶
归并排序是分析递归例程方法的经典实例,给运行时间写出一个递归关系。
假设 n 是 2 的幂,从而总可以把它分成均为偶数的两部分。
对于 n=1,归并排序所用时间是常数,我将记为 1
否则,对 n 个数归并排序的用时等于完成两个大小为 \frac n2 的递归排序所用的时间再加上合并的时间,它是线性的
下述方程给出表示
T(1)=1
T(n)=2T(\frac n2)+n
对上式求解
\frac{T(n)}n=\frac{T(\frac n2)}{\frac n2}+1
\frac{T(\frac n2)}n=\frac{T(\frac n4)}{\frac n4}+1
...
\frac{T(2)}2=\frac{T(1)}1+1
\frac{T(n)}n=\frac{T(1)}1+\log_2 n
T(n)=n+n\log_2 n
回忆我们假设 n 是 2 的幂,但对于其他情况,答案几乎是一样的