归并排序
归并排序的时间复杂度是O(n*log2n)，是稳定的
归并排序的思想是分治法（Divide and Conquer）
首先思考一个问题，已经排序的两个数组如何融合为一个有序数组
数组a，数组b，b中的第一个与a中的第一个比较，小的那个放到临时数组c中，一旦数组a或者b已经遍历完了，那么另外一个剩下的数组全部放到临时数组即可
1.融合两个已经排序的数组片段
融合两个已经排序的数组段代码如下：
/**
*a为排序数组，left为已排序左片段的下标，mid为已排序左片段的最后一个下标
*，right为已排序的右片段的最后一个下标，tem为临时数组
*
**/
private static void mergeArray(int[] a ,int left,int mid,int right,int[] tem){
//i为待会要进行比较的左数组的游标，j为右数组的游标，k为临时数组的游标
int i = left;
int j = mid + 1;
int k = left;
//一旦某个数组片段已经遍历完了，退出循环
while(i <= mid && j <= right){
if(a[i] < a[j]){
tem[k] = a[i];
i++;
k++;
}else{
tem[k] = a[j];
j++;
k++;
}
}
//把那个未遍历完的数组片段全部加到临时数组即可
while(i <= mid){
tem[k] = a[i];
i++;
k++;
}
//与上一个while循环只会执行其一，因为只可能出现一个片段有剩余
while(j <= right){
tem[k] = a[j];
j++;
k++;
}
//把临时数组放回到原数组
for(;left <= right;left++){
a[left] = tem[left];
}
}
2.递归划分出已排序的两个数组片段
如何递归划分出已排序的两个数组片段？
如果那个数组片段只有一个元素，就可以看成它是有序的，以下代码递归出这个片段：
private static void mergeSortMethod(int [] array,int start ,int end ,int[] tem){
//数组元素大于1的时候才进行递归分割。等于1就直接有序了
if(start < end){
//将一个数组分为两段，mid为左边的最后一个下标
int mid = (start + end) / 2;
//对左边再进行分割
mergeSortMethod(array, start, mid, tem);
//对右边再进行分割
mergeSortMethod(array, mid + 1, end, tem);
//归并两个已排序数组
mergeArray(array, start, mid, end, tem);
}
当片段长度为1的数组进入上述方法时候，递归停止，然后进行第一次的方法调用
mergeArray(array, start, mid, end, tem);
然后继续上一层的递归出栈。最后完成整个调用。
3.调用mergeArray()方法：
public static void mergeSort(int[] array){
//这场的临时数组用的是同一个，导致空间复杂度是O(n)
mergeSortMethod(array, 0, array.length - 1, new int[array.length]);
}
4.完整代码：
public class MergeSortSenninha {
public static void main(String[] arg){
int [] left = {1,2,5,7,889,3,4,6,7};
mergeSort(left);
print(left);
}
private static void mergeArray(int[] a ,int left,int mid,int right,int[] tem){
int i = left;
int j = mid + 1;
int k = left;
while(i <= mid && j <= right){
if(a[i] < a[j]){
tem[k] = a[i];
i++;
k++;
}else{
tem[k] = a[j];
j++;
k++;
}
}
while(i <= mid){
tem[k] = a[i];
i++;
k++;
}
while(j <= right){
tem[k] = a[j];
j++;
k++;
}
for(;left <= right;left++){
a[left] = tem[left];
}
}
public static void mergeSort(int[] array){
mergeSortMethod(array, 0, array.length - 1, new int[array.length]);
}
private static void mergeSortMethod(int [] array,int start ,int end ,int[] tem){
if(start < end){
int mid = (start + end) / 2;
mergeSortMethod(array, start, mid, tem);
mergeSortMethod(array, mid + 1, end, tem);
mergeArray(array, start, mid, end, tem);
}
}
public static void print(int[] array){
for(int i : array){
System.out.print(i + " ");
}
System.out.println("");
}
}
