/**
* 采用递归方法实现排序，特点：复杂度O(nlgn),非原地排序(有非常数个元素存放在数组以外的地方)
* 分解：将n个元素分成各含n/2个元素的子序列
* 解决：用合并排序法对两个子序列递归地排序
* 合并：合并两个已排序好的子序列以得到排序结果
*/
public class MergeSort {
/**
* 合并两个已排序的子序列
* @param arr 数组
* @param p 数组arr中从p到q为已排序的子序列一，共q-p+1个元素
* @param q 数组arr中从q+1到r为已排序的子序列二，共r-q个元素
* @param r
*/
public void merge(int arr[],int p,int q,int r){
int n1=q-p+1;
int n2=r-q;
//由于这里创建了两个数组来存放两个子序列的元素，所以为非原地排序
int tem1[] = new int[n1];
int tem2[] = new int[n2];
for(int i = 0;i<n1;i++)
tem1[i]=arr[p+i];
for(int j=0;j<n2;j++)
tem2[j]=arr[q+j+1];
int i = 0;
int j = 0;
int k = p;
for(;i<n1&&j<n2;){
if(tem1[i]<tem2[j])
arr[k++]=tem1[i++];
else
arr[k++]=tem2[j++];
}
//把剩余的元素放入arr中
while(i<n1)
arr[k++]=tem1[i++];
while(j<n2)
arr[k++]=tem2[j++];
}
/**
* 合并排序算法的外层调用函数，
* 把n个元素分成各含n/2个元素的子序列，然后递归进行分解，分解到两个子序列只有一个元素时调用merge进行合并
* @param arr 数组
* @param p 开始位置
* @param r 结束位置
*/
void mergeSort(int arr[],int p,int r){
if(p<r){
int q= (p+r)/2;
mergeSort(arr,p,q);
mergeSort(arr,q+1,r);
merge(arr,p,q,r);
}
}
public static void main(String[] args) {
int arr[] = {3,4,5,14,19,11,16,1,9,7,8,10,2,6,12,15,18,13,17,20};
MergeSort ms = new MergeSort();
ms.mergeSort(arr,0,arr.length-1);
for(int i=0;i<arr.length;i++)
System.out.println(arr[i]);
}
}
