歸并排序可以說是分治法的一個很形象的實例
歸并排序與快排不同的是绽族，歸并排序重點在整合姨涡，簡單的說把相對分區(qū)有序而內(nèi)部
元素亂序的兩區(qū)通過歸并整合成有序的序列。
歸并思路（分治法）：
分解：將n個元素一刀從中間分成兩個序列
遞歸：將子序列遞歸的進行分區(qū)劃分
解決：合并兩個子序列（歸并排序的重點）
歸并排序的合并（以空間換時間）：
申請額外的和原數(shù)組大小相同的輔助空間吧慢，將原數(shù)組元素copy到輔助空間中
定義兩個指針：left right 涛漂，其中l(wèi)eft指向輔助空間頭（第一區(qū)的頭），right指向輔助空間中間元素下一個（第二區(qū)的頭）比較大小，每次將小的元素覆蓋到原數(shù)組匈仗，并且該指針后移
（Java代碼示例）
public class MergeSort {
private static int[] helper;//輔助數(shù)組
public static void main(String[] args) {
int[] a = {5,15,8,20,6};
printArray(a);
sort(a);
printArray(a);
}
static void sort(int[] a) {
helper = new int[a.length];
mergeSort(a, 0, a.length - 1);
}
/**
*
* @param arr 待排序數(shù)組
* @param p 低位
* @param r 高位
*/
static void mergeSort(int[] arr, int p, int r) {
if(p < r) {
int mid = p + ((r - p)>>1);
mergeSort(arr, p, mid);//左側(cè)排序
mergeSort(arr, mid+1, r);//右側(cè)排序
merge(arr, p, mid, r);
}
}
static void printArray(int[] arr){
for(int i : arr){
System.out.print(i + " ");
}
System.out.println();
}
/**
*
* @param arr 待合并數(shù)組
* @param p 低位
* @param mid 中間位置
* @param r 高位
*/
static void merge(int[] arr, int p, int mid, int r) {
//arr中的數(shù)據(jù)拷貝到helper中
System.arraycopy(arr, p, helper, p, r-p+1);
//輔助數(shù)組的兩個指針
int left = p;
int right = mid + 1;
//原始數(shù)組的指針
int current = p;
while(left <= mid&&right <= r) {
if(helper[left] <= helper[right]) {
arr[current] = helper[left];
current++;
left++;
}else {
arr[current] = helper[right];
current++;
right++;
}
}
while(left <= mid) {//左邊沒有到頭,右邊不到頭也可以
arr[current] = helper[left];
current++;
left++;
}
}
}
