mergeSort
应用分治法思想，有两种实现方法：
- 自顶向下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）
- 自底向上的迭代
算法步骤
UpDown
通过二分法达到log(n)这样一个层级，然后再通过O(n)的归并操作，就形成了nlog(n)的归并排序
- 二分操作：将n个元素平均分成两部分，再分别将这两部分进行递归二分操作。直到所有分组都只有1个元素（只有一个元素时，数列显然有序）
- 归并操作：从最底层开始逐步合并两个排好序的数列
我这里采用对原数组进行操作，所以先建立一个辅助数组T temp[r-l+1]，通过for循环将原数组数据复制到辅助数组
又因为两个序列都已经有序，因此只需要两个序列的低位轮流进行比较，输的一方为小值，将这个值赋值到原数组，输的一方继续拿出一个值来比较，直到有一方没有元素后，将另一方的所有元素依次赋值到原数组中即可。此时，原数组为两个序列的有序合并。
下面两个子数组分别进行比较，将合适的元素赋值到上面的大数组
BottomUp
自底向上进行归并操作
- size是归并子数组的长度，从1开始直到n，归并一次，size扩大一倍
- 从下标i开始，对
arr[i,i+size-1]和arr[i+size,i+2*size-1]进行合并（两个子数组中对应的坐标相差size），下轮循环开始是从i+2*size
自顶向下的递归实现
#include <iostream>
#include "insertionSort.h"
usingnamespacestd;
//归并操作
template<typenameT>
void__merge(Tarr[],intleft,intmid,intright){
Ttemp[right-left+1];//临时数组
for(inti=left;i<=right;i++)
temp[i-left]=arr[i];
//临时数组中的左右指针（左指针是第一个元素，右指针从内部看来也是右部第一个元素，但从全局上看，就是中值+1）
intcurL=left,curR=mid+1;
//k是要原数组中即将要赋值的坐标
for(intk=left;k<=right;k++){
//这里四选一，所以要在一个if-else体系中，否则就会多次赋值
//越界判断
if(curL>mid){
arr[k]=temp[curR-left];
curR++;
}
elseif(curR>right){
arr[k]=temp[curL-left];
curL++;
}
//左右低位轮流PK
//右值为小值，加入到arr中，右边再拿出一个值来比较
elseif(temp[curL-left]>temp[curR-left]){
arr[k]=temp[curR-left];
curR++;
}else { //左值小于等于右值，左值加入arr中，左边再拿出一个值来比较（b）
arr[k]=temp[curL-left];
curL++;
}
}
}
//对数组中arr[left]至arr[right]进行归并排序
template<typenameT>
void__mergeSort(Tarr[],intleft,intright){
//1. 二分操作
//递归出口：处理的数据集为空
if(left>=right)
return ;
intmid=(left+right)/2;
__mergeSort(arr,left,mid);
__mergeSort(arr,mid+1,right);
//2. 归并操作
__merge(arr,left,mid,right);
}
//归并排序
template<typenameT>
voidmergeSort(Tarr[],intn){
//注意这里，数组范围是前闭后闭的
__mergeSort(arr,0,n-1);
}
intmain(){
intn=100000;
//生成乱序数组
int*arr=SortTestHelper::generateRandomArray(n,0,n);
int*arr2=SortTestHelper::copyIntArray(arr,n);
//测试耗时
//SortTestHelper::testSort("insertionSort",insertionSort,arr,n);
SortTestHelper::testSort("mergeSort",mergeSort,arr2,n);
//释放空间
delete[] arr;
delete[] arr2;
return0;
}
优化1：归并操作前的判断
当数组是近乎有序时，归并排序是弱于插入排序的时间复杂度的，可以在归并操作之前对数组进行是否有序判断
//归并操作
//左边的末尾大于右边首元素才会进行归并操作，如果是小于等于，则说明已经有序，不再进行归并操作
if(arr[mid]>arr[mid+1])
__merge(arr,left,mid,right);
当我们要处理的元素中可能出现有序的情况，可以使用上述代码优化
优化2：穿插使用插入排序
对于所有高级排序算法，都可以这么进行优化：
快要递归到底时，可以使用插入排序，当递归到数组数量非常小的时候，可以改为使用插入排序来提高性能
- 数组数量较小时，有序的概率较大
- 虽然插入排序最差时间复杂度为O(n^2)，归并排序时间复杂度为O(nlogn)，但是时间复杂度前面是有一个常数的系数的，插入排序的系数比归并排序的系数小，也就是说，当n小到一定程度时，插入排序是要比归并排序要快的
//二分操作
//处理数据集为空
// if(left>=right)
// return ;
//当数组元素<=15时，更换为插入排序
if((right-left)<=15){
insertionSort(arr ,left ,right);
return ;
}
需要在insertionSort.h中重载insertionSort函数
//对arr中[l,r]范围内的元素进行插入排序
template<typenameT>
voidinsertionSort(Tarr[],intleft,intright){
for(inti=left+1;i<=right;i++){
intj;
Te=arr[i];
//注意这里是j>left，而不是j>0
for(j=i;j>left&&arr[j-1]>e;j--)
arr[j]=arr[j-1];
arr[j]=e;
}
}
test
n=500000
//原始代码
mergeSort_TopDown : 0.173s
//使用优化1
mergeSort_TopDown : 0.158s
//使用优化2
mergeSort_TopDown : 0.144s
//使用优化1&2
mergeSort_TopDown : 0.119s
优化效果一目了然
自底向上的递推实现
//自底向上的归并排序
template<typenameT>
voidmergeSort_BottomUp(Tarr[],intn){
//size表示归并子数组的长度，归并之后的归并子数组长度要变为原来的2倍，因此每次循环结束size=size*2
for(intsize=1;size<=n;size=size*2){
//两个要进行归并的子数组间隔为size，对arr[i,i+size-1]和arr[i+size,i+2*size-1]进行归并，归并之后下次开始是arr[i+2*size]，因此每轮循环结束后i=i+2*size
//第一轮对[0,size-1]和[size,2*size-1]进行归并，第二轮对[2*size,3*size-1]和[3*size,4*size-1]进行归并
//界限处理：
//1. 因为只有存在两个子数组才能进行归并，那么要求i+size<n，保证了第二个子数组中arr[i+size]存在的合法性，并且避免了第一个子数组中arr[i+size-1]越界
//2. 遍历到后面，第二个子数组长度可能小于size，那么(2*size-1)>(n-1)造成越界，将其和(n-1)取最小值即可,min(i+2*size-1,n-1)
for(inti=0;i+size<n;i=i+2*size){
__merge(arr,i,i+size-1,min(i+2*size-1,n-1));
}
}
}
自底向上没有使用数组的重要特性：根据索引获取元素
正因如此，可以非常好的使用O(nlogn)的时间对链表这样的数据结构进行归并排序
