归并排序介绍
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
排序过程
将一个数组分解成两个子序列，这两子序列继续分解，直到不能在分解为止；从最小的子序列开始进行归并，形成一个较大的有序子序列，再继续归并直到整个数组有序。该过程我们可以用递归来实现。排序过程如下图所示：
归并排序.png
归并操作的工作原理
将两个分别有序的子序列归并成一个新的较大有序序列，其过程如下：
1.准备一个辅助数组，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2.设定两个指针p1和p2，最初位置分别为两个已经排序序列的起始位置
3.比较指针p1和p2所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4.重复步骤3直到某一指针超出序列尾
5.将另一序列剩下的所有元素直接复制到合并序列尾
算法实现
public class MergeSort {
private static void mergeSort(int[] arr,int left, int right) {
if(left == right) return;
int mid = left + ((right - left) >> 1); //int mid = (left + right)/2;
mergeSort(arr,left,mid); //左侧序列分解
mergeSort(arr,mid+1,right); //右侧序列分解
merge(arr,left,mid,right); //归并
}
private static void merge(int[] arr,int left,int mid,int right) {
int[] help = new int[right - left + 1]; //准备辅助数组
//准备两个指针分别指向两个序列的开始
int p1 = left;
int p2 = mid + 1;
int i = 0;
/*
* 比较指针p1和p2所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置,
* 直到某一指针超出序列尾
* */
while(p1 <= mid && p2 <= right) {
help[i++] = (arr[p1] < arr[p2])?arr[p1++]:arr[p2++];
}
//p2指针超出序列尾，将左侧序列继续添加进辅助数组
while(p1 <= mid) {
help[i++] = arr[p1++];
}
//p1指针超出序列尾，将右侧序列继续添加进辅助数组
while(p2 <= right) {
help[i++] = arr[p2++];
}
//拷贝会原数组
for(int j = 0; j < help.length; j++) {
arr[left + j] = help[j];
}
}
public static void mergeSort(int[] arr) {
if(arr == null || arr.length < 2) return;
mergeSort(arr,0,arr.length-1);
}
//测试
public static void main(String[] args) {
int[] arr0= {10,4,6,3,8,2,5,7};
mergeSort(arr0);
for(int i=0; i<arr0.length; i++) {
System.out.print(arr0[i] + " ");
}
//2 3 4 5 6 7 8 10
System.out.println();
int[] arr1 = {10,9,8,7,6,5,4,3,2,1};
mergeSort(arr1);
for(int i=0; i<arr1.length; i++) {
System.out.print(arr1[i] + " ");
}
//1 2 3 4 5 6 7 8 9 10
}
}
复杂度
在排序中由于我们使用了辅助数组，所以额外空间复杂度为O(n);
由归并排序的递归公式：T(N) = 2T(N/2) + O(N) 可知时间复杂度为O(NlogN)
算法的复杂度与master定理：http://www.gocalf.com/blog/algorithm-complexity-and-master-theorem.html
