大一计算机的自学总结：归并排序及归并分治
前言
之前写过最基础的三种排序算法大一计算机的自学总结：初见排序，但时间复杂度都是O(n^2)，运行起来会很慢，而归并排序的时间复杂度是O(n*logn)，会比之前三种排序算法快很多。
一、归并排序
原理就是每次都将数组分为左半部分和右半部分，使它们各自有序，再合并起来，让整体有序。
1.递归版
根据原理不难看出，如果用递归的话过程会非常简单。
#include<bits/stdc++.h>
using namespace std;
//全局变量
#define n 10
int arr[n];
//左跨右
void merge(int l,int m,int r)
{
int i=l;
int a=l;
int b=m+1;
int help[n];//辅助数组
while(a<=m&&b<=r)
{
help[i++]=arr[a]<=arr[b]?arr[a++]:arr[b++];
}
while(a<=m)
{
help[i++]=arr[a++];
}
while(b<=r)
{
help[i++]=arr[b++];
}
for(i=l;i<=r;i++)
{
arr[i]=help[i];
}
}
//归并排序 ——递归版
void mergeSort(int l,int r)
{
if(l==r)
{
return ;
}
int m=(l+r)/2;
mergeSort(l,m);
mergeSort(m+1,r);
merge(l,m,r);
}
int main()
{
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
//归并排序
mergeSort(0,n-1);
cout<<"Sorted:"<<endl;
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}排序函数没什么好说的，就是一个递归函数，重点是merge函数。
merge函数的作用是让两部分整体有序，考虑到直接在原数组上操作很麻烦，所以这里借助一个辅助数组，先将两部分的数从大到小填入辅助数组，再用辅助数组覆盖原数组即可。
将两部分的数从大到小填入，思路是，借助两个指针a和b，分别控制左半部分和右半部分的数，还有指针i，控制填入help数组的位置。当a和b都在各自范围内时，根据各自位置数的大小填入辅助数组。之后，将两部分的剩余部分填入辅助数组即可。
2.非递归版
在有些题目中，可能要求额外的空间复杂度为O(1)，此时就不能使用递归的方法了。
#include<bits/stdc++.h>
using namespace std;
//全局变量
#define n 10
int arr[n];
//左跨右
void merge(int l,int m,int r)
{
int i=l;
int a=l;
int b=m+1;
int help[n];//辅助数组
while(a<=m&&b<=r)
{
help[i++]=arr[a]<=arr[b]?arr[a++]:arr[b++];
}
while(a<=m)
{
help[i++]=arr[a++];
}
while(b<=r)
{
help[i++]=arr[b++];
}
for(i=l;i<=r;i++)
{
arr[i]=help[i];
}
}
//归并排序——非递归版
void mergeSort(void)
{
for(int l,m,r,step=1;step<n;step*=2)
{
l=0;
while(l<n)
{
m=l+step-1;
if(m+1>n-1)
{
break;
}
r=(m+step>n-1)?(n-1):(m+step);
merge(l,m,r);
l=r+1;
}
}
}
int main()
{
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
//归并排序
mergeSort();
cout<<"Sorted:"<<endl;
for(int i=0;i<n;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}观察递归的过程，可以发现，每次都是从中间分割直到只剩一个数，那么考虑设置步长step变量来控制每次merge的两部分大小。
merge函数跟递归版一样，重点是排序函数的变化。
初始化step=1，每次都乘以二，表示递归中分割的过程。之后使l=0，只要l没到最后，此时可以借助step来计算m的位置，若m+1越界，则表示只剩下一部分，所以break；否则计算r的大小，此时注意当剩余部分不够一个step时让r=n-1。之后merge两部分，让l=r+1往下跳即可。
二、归并分治
归并排序的思想，即分开求解再合并。
1.条件
（1）答案可以分为左侧答案+右侧答案+左跨右的答案
（2）在计算左跨右的答案时，若左右各有序，则可简便计算
2.例题——计算数组的小和
#include <iostream>
using namespace std;
typedef long long ll;
ll merge(int arr[],int n,int l,int m,int r)
{
ll ans=0;
for(ll i=l,j=m+1,sum=0;j<=r;j++)
{
while(i<=m&&arr[i]<=arr[j])
{
sum+=arr[i++];
}
ans+=sum;
}
int i=l;
int a=l;
int b=m+1;
int help[n];
while (a<=m&&b<=r)
{
help[i++]=arr[a]<=arr[b]?arr[a++]:arr[b++];
}
while(a<=m)
{
help[i++]=arr[a++];
}
while(b<=r)
{
help[i++]=arr[b++];
}
for(i=l;i<=r;i++)
{
arr[i]=help[i];
}
return ans;
}
ll smallSum(int arr[],int n,int l,int r)
{
if(l==r)
{
return 0;
}
int m=(l+r)/2;
return smallSum(arr,n,l, m)+smallSum(arr,n,m+1,r)+merge(arr,n,l,m,r);
}
int main()
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
cout<<smallSum(arr,n,0,n-1);
return 0;
}由上述第一个条件分析可以得出，求数组中每个数的小和，答案可以分为左半部分数的小和、右半部分数的小和以及左跨右部分的小和三者之和。
求小和的函数就是一个递归函数，重点是merge函数。
merge函数负责返回左跨右部分的小和，即右侧每一个数在左侧的小和。此时考虑上述第二个条件：左右各有序可简便运算。这是肯定的，若左右各有序，只需要遍历一遍即可解决。
解决方法如下：初始化i和j两指针分别控制左侧和右侧，当i始终在左侧，并且i位置的数比j位置的数小时，将数累加到sum里。若不小于j位置的数，因为左右各有序，则说明i位置右侧没有比j位置数更小的数，跳出循环，将sum累加到ans里。之后，将j移动到下一个位置， 此时，由于左右各自有序，所以不需要从头遍历左侧部分，只需要从i位置继续累加即可。
最后加上归并排序的部分使整体有序即可。
总结
归并排序的时间复杂度非常优秀，并且其归并分治的思想更是非常非常重要！！