归并排序
归并排序分治法的一个典型且基本的应用。它的基本思想是：将对N个对象的问题转换成两次对N/2个对象的问题。归并排序减少了数据的比较次数，转而增加了数据的移动次数，使得排序速度相对较快。该算法的递推公式T(N) = 2T(N/2) + O(N)表明其算法复杂度上限为O(NlogN)。下面是其C++代码：
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int innersort(int* A,int left,int right,int* CPY)
{//[left,mid]and[mid+1,right];
if(right==left)return 0;
int mid=(left+right)/2;
int i=left,k=mid+1;
int cur=left;
while(i!=mid+1&&k!=right+1)
{
if(A[i]>A[k])CPY[cur++]=A[k++];
else CPY[cur++]=A[i++];
}//一定有一侧的数据会最先完成排序
while(i!=mid+1)CPY[cur++]=A[i++];
while(k!=right+1)CPY[cur++]=A[k++];//对剩余的一侧数据一次添加进入CPY数组即可
memcpy(A+left,CPY+left,sizeof(int)*(right-left+1));//复制回到原数组
return 0;
}
int merger(int* A,int left,int right,int* CPY)
{//[left,mid]and[mid+1,right];
if(left<right)
{
int center=(left+right)/2;
//中点的归属需要特别考虑
merger(A,left,center,CPY);
merger(A,center+1,right,CPY);
innersort(A,left,right,CPY);
}
return 0;
}
int mergesort(int* A,int* Aend)
{//[left,right);
int right=Aend-A;
int* temp=new int[right+1];//临时数组开得大了一点
merger(A,0,right-1,temp);
//数组的边界问题与分割方案问题一直是关注点
delete[] temp;
return 0;
}
int main()
{
int aim[]={3,5,2,6,7,3,2,6,2,6,3,7,3,2};
mergesort(aim,aim+14);
for(int i=0;i<14;i++)
{
printf("%d ",aim[i]);
}
printf("\n");
return 0;
}归并排序中的比较次数是所有排序中最少的。原因是，它一开始是不断地划分，比较只发生在合并各个有序的子数组时。
因此，JAVA的泛型排序类库中实现的就是归并排序。因为：对于JAVA而言，比较两个对象的操作代价是很大的（根据Comparable接口的compareTo方法进行比较），而移动两个对象，其实质移动的是引用，代价比较小。（排序本质上是两种操作：比较操作和移动操作）
归并排序算法分析
归并排序算法有两个基本的操作，一个是分，也就是把原数组划分成两个子数组的过程。另一个是治，它将两个有序数组合并成一个更大的有序数组。
它将数组平均分成两部分: center = (left + right)/2，当数组分得足够小时---数组中只有一个元素时，只有一个元素的数组自然而然地就可以视为是有序的，此时就可以进行合并操作了。因此，上面讲的合并两个有序的子数组，是从 只有一个元素 的两个子数组开始合并的。
合并后的元素个数：从 1-->2-->4-->8......
比如初始数组：[24,13,26,1,2,27,38,15]
①分成了两个大小相等的子数组：[24,13,26,1] [2,27,38,15]
②再划分成了四个大小相等的子数组：[24,13] [26,1] [2,27] [38,15]
③此时，left < right 还是成立，再分：[24] [13] [26] [1] [2] [27] [38] [15]
此时，有8个小数组，每个数组都可以视为有序的数组了！！！，每个数组中的left == right，从递归中返回，故开始执行合并：
merge([24],[13]) 得到 [13,24]
merge([26],[1]) 得到[1,26]
.....
.....
最终得到 有序数组。