归并排序
1.归并排序简介：
归并排序是建立在多次递归的基础上的合并操作的排序算法，是一种建立在归并操作上的有效的排序算法，该算法是采用分治法的一个典型的用例，正因为采用了分治法，并且是二路分支，（我们也称其为二路归并），所以说归并排序的递归树始终是均衡的，在这一点上，归并排序相对于快速排序有明显的优越性（但是实际上因为牵扯到cache的概念，所以归并排序的实际的算法的速度是慢于快速排序的），在这上面本人参考了大量的博客和怠慢论坛但是都看不出快速排序，归并排序，堆排序，希尔排序的真正的忧虑，实感羞愧
因为我们在进行子数组归并的时候完全是按照数组的从左至右的顺序的，所以说，归并排序是稳定的排序
归并排序的递归树附图：
优点：归并排序只对相邻的数组元素进行处理，所以相对来说归并排序的速度有可能在某一数据量区域内优于普通快排
缺点：归并排序占用了大量的内存空间（占用了和原数组等长的空间，一旦待排数组的量非常巨大的话，这完全是致命的缺点）里进行排序操作，所以来说，归并排序在大数据的时候很容易造成内存的溢出。
2.算法讲解：
算法的整体讲解：
我们通过不断的递归，直到每个小段的数据长度只有自身的时候我们自动认为此时已经达到了我们所谓的有序的状态，然后我们进行挑选式的插入排序操作，在这一段里面复杂度仅仅只是我们遍历的长度的大小，即O(n),所以说还是非常高效的（但是要认识到，我们这是采用了空间换时间来进行优化的）
在算法的整体结构上，我们对于整个算法都可以分成两块来进行考虑
第一块代码段：
就是刚才提到的，对每段相邻的采取刚才提及的插入的排序
第二块代码段：
多次递归，当达到我们的递归终止条件（每段只有一个元素，默认有序）的时候，进行回溯的归并操作
算法的复杂度证明：
因为归并排序算法是二分的，所以说分自然而然有以下的证明：
T(n)=2T(n/2)+f(n) 注意这里的f(n)的考虑是从后往前的，因为归并排序优点类似于二叉树的后序遍历，所以说f(n)代表每一层的递归树的归并操作，所以说f(n)是O(n)
T(n)=4T(n/4)+2f(n)
...log2n=k,共进行k层递归
T(n)= nT(1)+kf(n)=O(n*logn)
3.算法的实现：
C++代码类封装：(代码中我会进行更详细的讲解)
#include"iostream"
#include"cstdio"
#include"cstdlib"
#include"cstring"
#define N 100
#define inf 99999999
using namespace std;
template<typename T> class mergesort;
template<typename T> istream& operator>>(istream&,mergesort<T>&);
template<typename T> ostream& operator<<(ostream&,mergesort<T>&);
template<typename T> //需要扩展O(n)的空间复杂度来实现排序操作
class mergesort
{
public:
mergesort()
{
memset(data,0,sizeof(data));
num=0;
}
friend istream& operator>><>(istream&,mergesort<T>&);
friend ostream& operator<<<>(ostream&,mergesort<T>&);
void premerge()
{
merge_sort(1,num);
}
void merge_sort(int,int);
void mergearray(int,int,int);
private:
T data[N];
int num;
};
template<typename T>
istream& operator>>(istream& in,mergesort<T>& k)
{
cout<<"please input the number of the data!"<<endl;
cin>>k.num;
for(int i=1;i<=k.num;i++) cin>>k.data[i];
return in;
}
template<typename T>
ostream& operator<<(ostream& out,mergesort<T>& k)
{
cout<<"排序结果如下："<<endl;
for(int i=1;i<=k.num;i++) cout<<k.data[i]<<' ';
cout<<endl;
return out;
}
template<typename T>
void mergesort<T>::merge_sort(int left,int right)
{
if(left>=right) return ;
int mid=(left+right)/2;
merge_sort(left,mid);
merge_sort(mid+1,right);
mergearray(left,mid,right);
return ;
}
template<typename T>
void mergesort<T>::mergearray(int left,int center,int right)
{
int n1=center-left+1;
int n2=right-center;
T s1[n1+2]; //从1开始，并且最后一个元素设定成监视哨（虽然这么做会将空间复杂度提升至O(n+logn)但是毕竟好实现）
T s2[n2+2];
int j=1;
for(int i=left;i<=center;i++,j++) s1[j]=data[i];
j=1;
for(int i=center+1;i<=right;i++,j++) s2[j]=data[i];
int i=1;j=1;
s1[n1+1]=s2[n2+1]=inf; //监视哨
for(int k=left;k<=right;k++) //插入排序的过程
{
if(s1[i]<s2[j]) data[k]=s1[i++];
else data[k]=s2[j++];
}
}
int main()
{
mergesort<int> my1;
mergesort<double> my2;
cin>>my1>>my2;
my1.premerge();
my2.premerge();
cout<<my1<<my2<<endl;
return 0;
}
4.归并排序的应用：
4.1归并排序求最大逆序对数
我们知道求最大逆序对数的一个方法就是从头到尾都扫一遍，时间复杂度是：
T(n)=1+2+...+n-1=O(n*n)
但是通过归并排序我们可以将方法的时间复杂度优化到O(n*logn)
思路如下：
我们能可以发现，在归并的回溯过程中，我们前一段子数组始终是有序状态，后一段子数组始终是待有序状态（只有后一段也有序了，我们才开始下一次归并）
当后一组有序的时候，我们开始归并，在不断插入的时候我们如果发现了前一段中的某个元素比后一段的某个元素要大的时候，那么这个元素到前一段子数组的末尾这一段的元素都满足相同的状态，那么子数组的求解就会大大加快
但是有的人就会问了，难道这样不会重复计算吗，大男士不会的，因为我们每次是一段一段的来考虑：
这一个一段一段是这样理解的，前一段元素和后一段元素之间存在的逆序对的关系（数目）是不会随着前一段的排序和后一段的排序索引项的，我们之前计算的前一段的之间的逆序对数似小范围的，我们之后是不断将其范围进行扩大之后进行判断的，是完全正确的思路
又有的人可能会问，那么可不可以只记录不排序呢，这样会不会可以将时间复杂度在此优化呢:
这里的话，我们只能说有点异想天开了，我们上面的考虑都是在基于前一段子数组和后一段子数组的有序的情况下考虑的，所以说排序是必不可少的部分，只有排序我们才可以将重复的遍历的累计计算通过有序的方式简化为O(1)的数学表达式计算（下面的注释处）
附上代码：（在刚才的地方进行类小改动而已）
#include"iostream"
#include"cstdio"
#include"cstdlib"
#include"cstring"
#define N 100
#define inf 99999999
using namespace std;
template<typename T> class mergesort;
template<typename T> istream& operator>>(istream&,mergesort<T>&);
template<typename T> ostream& operator<<(ostream&,mergesort<T>&);
template<typename T> //需要扩展O(n)的空间复杂度来实现排序操作
class mergesort
{
public:
mergesort()
{
memset(data,0,sizeof(data));
num=0;
ans=0;
}
friend istream& operator>><>(istream&,mergesort<T>&);
friend ostream& operator<<<>(ostream&,mergesort<T>&);
void premerge()
{
merge_sort(1,num);
}
void merge_sort(int,int);
void mergearray(int,int,int);
private:
T data[N];
int num;
int ans;
};
template<typename T>
istream& operator>>(istream& in,mergesort<T>& k)
{
cout<<"please input the number of the data!"<<endl;
cin>>k.num;
for(int i=1;i<=k.num;i++) cin>>k.data[i];
return in;
}
template<typename T>
ostream& operator<<(ostream& out,mergesort<T>& k)
{
cout<<"排序结果如下："<<endl;
for(int i=1;i<=k.num;i++) cout<<k.data[i]<<' ';
cout<<endl<<"逆序对数为："<<k.ans<<endl;
return out;
}
template<typename T>
void mergesort<T>::merge_sort(int left,int right)
{
if(left>=right) return ;
int mid=(left+right)/2;
merge_sort(left,mid);
merge_sort(mid+1,right);
mergearray(left,mid,right);
return ;
}
template<typename T>
void mergesort<T>::mergearray(int left,int center,int right)
{
int n1=center-left+1;
int n2=right-center;
T s1[n1+2]; //从1开始，并且最后一个元素设定成监视哨（虽然这么做会将空间复杂度提升至O(n+logn)但是毕竟好实现）
T s2[n2+2];
int j=1;
for(int i=left;i<=center;i++,j++) s1[j]=data[i];
j=1;
for(int i=center+1;i<=right;i++,j++) s2[j]=data[i];
int i=1;j=1;
s1[n1+1]=s2[n2+1]=inf; //监视哨
for(int k=left;k<=right;k++) //插入排序的过程
{
if(s1[i]<=s2[j]) data[k]=s1[i++];
else //满足逆序的条件
{
data[k]=s2[j++];
ans+=center-left+1-i+1; //这就是上面讲解的部分
}
}
}
int main()
{
mergesort<int> my1;
mergesort<double> my2;
cin>>my1>>my2;
my1.premerge();
my2.premerge();
cout<<my1<<my2<<endl;
return 0;
}
4.2求最大子数组和（O(n*logn)）（下一篇博文会再次介绍O(n)的动态规划思路求解）
首先我们要明确一点，最大字数组只会有三种情况
1.全部在左半边
2.全部在右半边
3.横跨左中右（计算的时候我们从重点开始向两边扩展进行计算）
那么我们分治法（归并）的思路就是每次通过求解上一层的最大子数组返回其值来求出这一层的最大值，最后三者（上面讨论的）比较就好了
附上C++封装的代码：
#include"iostream"
#include"cstdlib"
#include"cstdio"
#include"cstring"
#define N 100
#define inf -99999999
using namespace std;
template<typename T> class submax;
template<typename T> class submax;
template<typename T>
istream& operator>>(istream&,submax<T>&);
template<typename T>
ostream& operator<<(ostream&,submax<T>&);
template<typename T>
class submax
{
public:
submax()
{
memset(data,0,sizeof(data));
num=ans=0;
}
friend istream& operator>><>(istream&,submax<T>&);
friend ostream& operator<<<>(ostream&,submax<T>&);
void premerge()
{
ans=merge(1,num);
}
T merge(int,int);
T submaxcross(int,int,int);
private:
T data[N];
int num;
T ans;
};
template<typename T>
istream& operator>>(istream& in,submax<T>& k)
{
cout<<"请输入你的数组的个数:";cin>>k.num;
cout<<"请输入你的数组"<<endl;
for(int i=1;i<=k.num;i++) cin>>k.data[i];
return in;
}
template<typename T>
ostream& operator<<(ostream& out,submax<T>& k)
{
cout<<"你所输入的数组的最大子数组之和是："<<k.ans<<endl;
return out;
}
template<typename T>
T submax<T>::merge(int left,int right)
{
if(left>=right);
else
{
T leftsum=inf;
T rightsum=inf;
T crosssum=inf;
int mid=(left+right)/2;
leftsum=merge(left,mid);
rightsum=merge(mid+1,right);
crosssum=submaxcross(left,mid,right);
if(leftsum>rightsum&&leftsum>crosssum) return leftsum;
else
{
if(rightsum>leftsum&&rightsum>crosssum) return rightsum;
else return crosssum;
}
}
}
template<typename T>
T submax<T>::submaxcross(int left,int mid,int right)
{
T leftsum=inf;
T rightsum=inf;
T sum=0;
for(int i=mid;i>=left;i--)
{
sum+=data[i];
if(sum>leftsum) leftsum=sum;
}
sum=0;
for(int i=mid+1;i<=right;i++)
{
sum+=data[i];
if(sum>rightsum) rightsum=sum;
}
return leftsum+rightsum;
}
int main()
{
submax<int> my1;
submax<double> my2;
cin>>my1>>my2;
my1.premerge();
my2.premerge();
cout<<my1<<my2<<endl;
return 0;
}
5.归并排序的空间复杂度优化的思考（原地归并）
先附上参考文献：
6.思考问题：
1.如何记录最大子数组
2.还是没有彻底了解原地归并的原理（手摇算法） 本问题已经解决
3.还是不懂为什么归并相对快排来说慢，cache到底影响在了哪里？
7.参考文献：
| 
转播
