归并排序思想
首先是自顶向下的思路
给出一组数，把数划分为两部分，再把两部分划分四部分，直至每部分只有一个元素剩余
然后对底下剩余的两部分排序，使划分的这两部分有序，这样它的上一层就有序了。一直这样做，最后把有序的左半部分和有序的右半部分归并，就可以使得原数组有序也就是分为两个部分-----逐次向下化层，逐次向上归并
由于二分化为不同部分，时间复杂度O（logn）
然后两个部分进行排序的过是O（n）所以归并排序是O（nlogn）的复杂度
代码实现
void mergeSort(T a[],int n){
mergeSortHelper(a,0,n-1);//调用辅助函数，将参数变为3个
}?归并排序要传入的只是数组的首地址和数组长度
但是归并排序在分层时候需要二分，所以自己调用内部子函数，使得有自己部分数组的左边索引和右边索引（这里是左闭右闭）
void mergeSortHelper(T a[],int L,int R){
if(L>=R) return; //结束递归
int mid=(L+R)/2;//将数组一分为二的索引
mergeSortHelper(a,L,mid);
mergeSortHelper(a,mid+1,R);
_merge(a,L,mid,R);//真正进行归并排序过程--由于两部分构成，所以传mid
}?首先利用递归将原数组从两部分到四部分，直至每一个部分的元素个数为1.
?然后递归结束，就可以把两部分进行归并操作，使得划分它们的前一个部分是有序的。注意索引的数字：
一部分是【L,mid】;另一部分【mid+1,R】由于归并排序是对两部分排序使其划分他们的那部分数组有序，所以要传入：三个索引
- L---第一部分数组的起始标识
- mid---第一部分数组的结束标识
- mid+1---第二部分数组的起始标识
- R---第二部分数组的结束标识
void _merge(T a[],int L,int mid,int R){
T* aux=new T[R-L+1];//构造辅助函数，以便进行归并
int i=L;//左部分标识
int j=mid+1;//右部分标识
for(int k=0;k<R-L+1;k++){//k--辅助数组当前要存入的数的索引
if(i>mid){//左边数组偏小至遍历结束
aux[k]=a[j];
j++;
}
else if(j>R){//右边数组偏小至遍历结束
aux[k]=a[i];
i++;
}
else if(a[i]>a[j]){
aux[k]=a[j];
j++;
}
else{//a[i]<=a[j]
aux[k]=a[i];
i++;
}
}//for
//把aux的值传递给a,完成归并
for(int i=L;i<=R;i++)
a[i]=aux[i-L];
}?真正进行排序的过程---体现算法的思想
? ?首先构造辅助数组，对两部分数据进行比较，然后值存入辅助数组-----辅助数组有序
? ?然后把辅助数组的值copy给原数组就可以了索引的建立----i,j,k
- i----第一部分的起始位置，结束位置是mid;
- j----第二部分的起始位置，结束位置是R;
- k----辅助数组要放入的元素当前索引
情况：
- 两部分数组均没有遍历完，比较i,j当前位置的大小去存入k
- 第一部分已经结束了，但是第二部分有剩余，把余下的第二部分copy给辅助数组
- 第二部分已经结束了，但第一部分有剩余，把余下的第一部分copy给辅助数组
?其中代码段：
for(int k=0;k<=R-L+1;k++){//k--辅助数组当前要存入的数的索引
if(i>mid){//左边数组偏小至遍历结束
aux[k]=a[j];
j++;
}
else if(j>R){//右边数组偏小至遍历结束
aux[k]=a[i];
i++;
}
else if(a[i]>a[j]){
aux[k]=a[j];
j++;
}
else{//a[i]<=a[j]
aux[k]=a[i];
i++;
}
}//for可以这样写
int k=0;
while(i<=mid&&j<=R){
if(a[i]>a[j]){
aux[k++]=a[j++];
}
else{
aux[k++]=a[i++];
}
}
while(i<=mid){
aux[k++]=a[i++];
}
while(j<=R){
aux[k++]=a[j++];
}这个写法就是严格按照上述三种情况写的code
注意：如果i,j有超出范围的，后两种情况条件要选符合要求的：
i<=mid;? ? j<=R;
完整程序
template<typename T>
void _merge1(T a[],int L,int mid,int R){
T aux[R-L+1];
int e=a[L];
//索引
int i=L;
int j=mid+1;
for(int k=0;k<R-L+1;k++){
if(i>mid){
aux[k]=a[j++];
}
else if(j>R){
aux[k]=a[i++];
}
else if(a[i]>a[j]){
aux[k]=a[j++];
}
else{
aux[k]=a[i++];
}
}
//aux赋值给a
for(int i=L;i<=R;i++){
a[i]=aux[i-L];
}
}
/*while的用法*/
template<typename T>
void _merge2(T a[],int L,int mid,int R){
T* aux=new T[R-L+1];
T e=a[L];
//索引
int i=L;
int j=mid+1;
int k=0;
while(i<=mid&&j<=R){
if(a[i]>a[j]){
aux[k++]=a[j++];
}
else{
aux[k++]=a[i++];
}
}
while(i<=mid){
aux[k++]=a[i++];
}
while(j<=R){
aux[k++]=a[j++];
}
for(int i=L;i<=R;i++){
a[i]=aux[i-L];
}
}
//归并排序递归调用
template<typename T>
void mergesortHelper(T a[],int L,int R){
if(L>=R) return;
int mid=(L+R)/2;
mergesortHelper(a,L,mid);
mergesortHelper(a,mid+1,R);
_merge2(a,L,mid,R);//或者merge1
}
//归并排序调用接口
template<typename T>
void mergeSort(T a[],int n){
mergesortHelper(a,0,n-1);
}?几种优化
1：
if(a[mid]>a[mid+1]){
_merge(a,L,mid,R);//真正进行归并排序过程--由于两部分构成，所以传mid
}因为归并排序传入的左右两部分一定是有序的，如果左部分最后一个元素比右半部分第一个元素小，那么就可以不用归并操作
由于if的判断也需要时间，数据量很小时不一定会缩短时间
利用---近乎有序数组的插入排序很快的性质?
可以在递归结束条件利用：R-L<=某个数，然后用插入排序以缩短运行时间
2：?
if(R-L<=10) {
insertSort(a,L,R);
return;}/*插入排序*/
template<typename T>
void insertSort(T a[],int L,int R){
for(int i=L+1;i<=R;i++){
T e=a[i];
int j;
for(j=i;j>L&&a[j-1]>e;j--){
a[j]=a[j-1];
}
a[j]=e;
}
}?注意几点：
- i的位置从L+1开始，因为默认第一个元素有序
- j=i，而且j>L,因为不会遍历到第一个位置
- a[j]=e在循环体内赋值
利用循环--自顶向上进行归并
template<typename T>
void mergeSortB2U(T a[],int n){
for(int sz=1;sz<=n;sz+=sz)
for(int i=0;i+sz<n;i+=sz+sz){
_merge1(a,i,i+sz-1,min(i+sz+sz-1,n-1));
}
}?思想很简单，从1大小选两个元素归并，接下来选2大小，对两个元素归并
