一、分治思想
分治，就是分而治之，將一個(gè)大問(wèn)題分解成小的子問(wèn)題來(lái)解決。小的子問(wèn)題解決了，大問(wèn)題也就解決了。
分治算法一般都是用遞歸來(lái)實(shí)現(xiàn)的。分治是一種解決問(wèn)題的處理思想，遞歸是一種編程技巧。
二、歸并排序
歸并排序是建立在歸并操作上的一種有效，穩(wěn)定的排序算法。
該算法是采用分治思想，將已有序的子序列合并，得到完全有序的序列；
即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。
第一步：申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
第二步：設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
第三步：比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
重復(fù)步驟3直到某一指針超出序列尾。
三、歸并排序代碼實(shí)現(xiàn)
import java.util.*;
class MergeSort {
public static void main(String[] args) {
int[] arr = {5,7,4,2,0,3,1,6};
mergeSort(arr, 0, arr.length-1);
System.out.print(Arrays.toString(arr));
}
public static void mergeSort(int[] arr,int left,int right){
if(left>=right){
return;
}
int mid = (left + right) / 2;
//先將數(shù)組按照中間下標(biāo)分解成兩部分，遞歸直到分解每部分只有1個(gè)元素為止
mergeSort(arr, left, mid);
mergeSort(arr, mid+1, right);
//分解結(jié)束后，由下到上，遞歸合并已經(jīng)排序好的兩部分
merge(arr, left, mid, right);
}
//需要注意的是整個(gè)合并過(guò)程中并沒(méi)有將兩個(gè)被合并的數(shù)組單獨(dú)拎出來(lái)，
//二者始終是存在于一個(gè)數(shù)組地址上的
public static void merge(int[] arr,int left,int mid,int right){
//根據(jù)拿到的左邊界，我們定其為第一個(gè)數(shù)組的指針
int s1 = left;
//根據(jù)中間位置，讓中間位置右移一個(gè)單位，那就是第二個(gè)數(shù)組的指針
int s2 = mid+1;
//根據(jù)左右邊界相減我們得到這片空間的長(zhǎng)度，以此聲明額外空間
int[] temp = new int[right - left+1];
//定義額外空間的指針
int i = 0;
while(s1<=mid && s2 <=right){
//如果第一個(gè)數(shù)組的指針數(shù)值小于第二個(gè)數(shù)組的，那么其放置在臨時(shí)空間上
if(arr[s1]<=arr[s2]){
temp[i++] = arr[s1++];
}else{//否則是第二個(gè)數(shù)組的數(shù)值放置于其上
temp[i++] = arr[s2++];
}
}
//如果這是s1仍然沒(méi)有到達(dá)其終點(diǎn)，那么說(shuō)明它還有剩
while(s1<=mid){
//因?yàn)槲覀冎烂總€(gè)參與合并的數(shù)組都是有序數(shù)組，因此直接往后拼接即可
temp[i++] = arr[s1++];
}
while(s2<=right){//同上
temp[i++] = arr[s2++];
}
for(int j = 0;j<temp.length;j++){//數(shù)組復(fù)制
arr[j+left] = temp[j];
}
}
}
二、歸并排序復(fù)雜度
時(shí)間復(fù)雜度O（N*logN)
空間復(fù)雜度O (N）
穩(wěn)定性：穩(wěn)定
