1、歸并排序的基本思想
以下面的這個數(shù)組為例肋坚，首先我們將數(shù)組對半分割，直到分割成單個元素，此時對于每一個單個元素來說都是有序的智厌，因為就他一個元素嘛诲泌，然后開始向上逐漸歸并的過程，直到上升到最后一個層級铣鹏，此時排序結(jié)束敷扫。
那我們?yōu)槭裁促M那么大勁，要將數(shù)組先分割在歸并呢诚卸？大家可以看到我們是對一個長度為“8”的數(shù)組進(jìn)行的排序葵第，一步步通過二分法到單個元素總共是經(jīng)歷了“3”個層級，這個“3”是怎么來的呢合溺？數(shù)組長度8/2/2/2=1卒密，8到1總共是經(jīng)歷了3次除以2的操作，也就是log2(8)=3棠赛，如果有N個元素哮奇，那么就有l(wèi)og2(N)的層級，由此我們可以推斷歸并排序的時間復(fù)雜度是Nlog(N)級別的睛约。
2鼎俘、歸并的過程
可以發(fā)現(xiàn)我們要使用遞歸的方式來逐漸歸并，這里以倒數(shù)第二層歸并到最后一層的過程為例來說明歸并的過程辩涝。
1贸伐、開辟出一個相同的數(shù)組空間；
2怔揩、設(shè)立三個索引捉邢，第一個藍(lán)色箭頭放在原數(shù)組的第一位，第二個紅色箭頭放在要比較的第一個數(shù)組的第一位商膊，第三個紅色箭頭放在要比較的第二個數(shù)組的第一位伏伐；
3、比較兩個紅色箭頭索引處元素的大小翘狱，將較小的那個元素放到藍(lán)色箭頭索引位置處秘案，藍(lán)色箭頭索引+1砰苍，移動的紅色索引+1潦匈，然后繼續(xù)下一輪的比較。
三個索引分別對應(yīng)：左邊的紅色箭頭定義為i赚导，右邊的紅色箭頭定義為j茬缩，上面的藍(lán)色箭頭定義為k.
具體代碼實現(xiàn)如下：
public class MergeSort {
//第一步：我們對傳遞的數(shù)組從位置0到n-1進(jìn)行歸并排序，因為我們的定義是前閉后閉吼旧，當(dāng)然你也可以使用前閉后開的定義凰锡。
public static void mergeSort(int arr[],int n){
mergeSortT(arr, 0, n-1);
}
//第二步：遞歸歸并
public static void mergeSortT(int arr[],int l,int r){
if (l >= r) {
return;
}
int mid = (l+r)/2;
mergeSortT(arr,l,mid);
mergeSortT(arr, mid+1, r);
merge(arr, l, mid,r);
}
//第三步：歸并操作
// 將arr[l...mid]和arr[mid+1...r]兩部分進(jìn)行歸并
private static void merge(int[] arr, int l, int mid, int r) {
//1、開辟臨時數(shù)組（因為是閉區(qū)間所以這里臨時數(shù)組的大小為：r-l+1）
int temp[] = new int[r-l+1];
for (int i = l; i <= r; i++) { //注意是L,不是1
temp[i-l] = arr[i];
}
//2、定義索引：i=L,j,k
int i = l,j = mid +1;
for (int k = l; k <= r; k++) { //K=L...
//判斷索引越界
if (i>mid) {
arr[k] = temp[j-l];
j++;
}
else if (j>r) {
arr[k] = temp[i-l];
i++;
}
//比較臨時數(shù)組兩邊的大小
else if (temp[i-l] <temp[j-l]) {
arr[k] = temp[i-l];
i++;
}
else {
arr[k] = temp[j-l];
j++;
}
}
}
}
測試用例：
public static void main(String[] args) {
Random rand = new Random();
int arr[] = new int[50000];
for (int i = 0; i < 50000; i++) {
int randNum = rand.nextInt() + 1;
arr[i] = randNum;
}
long currentTimeMillis = System.currentTimeMillis();
mergeSort(arr,50000);
long currentTimeMillis2 = System.currentTimeMillis();
System.out.println("基礎(chǔ)歸并排序所用時間："+(currentTimeMillis2-currentTimeMillis));
}
輸出結(jié)果：
基礎(chǔ)歸并排序所用時間：24
3掂为、歸并排序的優(yōu)化
第一步優(yōu)化：
當(dāng)我們使用一個近乎有序的數(shù)組作為測試用例時候裕膀，會發(fā)現(xiàn)插入排序的效率比歸并排序的效率要高很多！
public static void main(String[] args) {
int[] arr = SortTestHelper.generateNearlyOrderdArray(50000, 10);
int[] copyIntArray = SortTestHelper.copyIntArray(arr, 50000);
long currentTimeMillis = System.currentTimeMillis();
mergeSort(arr,50000);
long currentTimeMillis2 = System.currentTimeMillis();
System.out.println("基礎(chǔ)歸并排序所用時間："+(currentTimeMillis2-currentTimeMillis));
long currentTimeMillis3 = System.currentTimeMillis();
InsertSort.insertSort(copyIntArray, 0, 50000);
long currentTimeMillis4 = System.currentTimeMillis();
System.out.println("插入排序所用時間："+(currentTimeMillis4-currentTimeMillis3));
}
輸出結(jié)果：
基礎(chǔ)歸并排序所用時間：33
插入排序所用時間：4
現(xiàn)在只是對五萬個數(shù)進(jìn)行排序勇哗，如果測試的數(shù)據(jù)量更大的話昼扛，差距可想而知。這是因為插入排序?qū)τ谝粋€近乎有序的數(shù)組會降低到O（N）的級別欲诺，那么歸并排序是否有什么方案對這種特殊的情況進(jìn)行優(yōu)化呢抄谐？答案是肯定的！
大家來看這一段代碼：
public static void mergeSortT(int arr[],int l,int r){
if (l >= r) {
return;
}
int mid = (l+r)/2;
mergeSortT(arr,l,mid);
mergeSortT(arr, mid+1, r);
merge(arr, l, mid,r);
}
在這里我們mergeSortT(arr,l,mid);mergeSortT(arr, mid+1, r);對兩個部分進(jìn)行排序之后不管他們之間的順序如何扰法，都會進(jìn)行一次merge操作蛹含，是不是有時候可以省略掉這一次merge操作呢？答案是沒問題的塞颁，當(dāng)arr[mid] > arr[mid +1]我們才需要merge操作浦箱。下面我們將這句話加入到原來的代碼中，運行一下：
基礎(chǔ)歸并排序所用時間：8
插入排序所用時間：4
可見這一步優(yōu)化對于一個基本有序的數(shù)組來說是非常有效的殴边！但是歸并排序還是比插入排序要慢一些憎茂，這是因為歸并排序無法退化成一個O（N）級別的算法。
第二步優(yōu)化
現(xiàn)在我們的遞歸是遞歸到只有一個元素的時候然后return锤岸，但是事實上當(dāng)我們遞歸到元素量非常小的時候竖幔，我們可以轉(zhuǎn)而使用插入排序來提高性能。這是基于兩個方面是偷，一方面當(dāng)我們的元素數(shù)量比較小的時候拳氢，整個數(shù)組近乎有序的概率就會比較大，此時插入排序有優(yōu)勢蛋铆，另外一方面雖然插入排序的最差事件復(fù)雜度是N2 級別的馋评，但是要注意不管是N2還是NlogN都是
有一個N常數(shù)的，換句話說當(dāng)N小到一定程度的時候刺啦，插入排序要比歸并排序要快一些留特。為此對于上面的代碼我們就可以這樣修改：
public static void mergeSortT(int arr[],int l,int r){
/*if (l >= r) {
return;
}*/
if (r-l <=15) {
InsertSort.insertSort(arr, l, r);
return;
}
int mid = (l+r)/2;
mergeSortT(arr,l,mid);
mergeSortT(arr, mid+1, r);
if (arr[mid] > arr[mid+1])
merge(arr, l, mid,r);
}
輸出結(jié)果：
基礎(chǔ)歸并排序所用時間：7
插入排序所用時間：3
至此我們的兩個優(yōu)化方案也就完成了~
當(dāng)然優(yōu)化是沒有止境的，這里就簡單介紹這么多玛瘸，剩下的還需要自己去探索了蜕青。
本文用到的一個工具類：
public class SortTestHelper {
public static int[] generateRandomArray(int n, int range_l, int range_r) {
int arr[] = new int[n];
Random rand = new Random();
for (int i = 0; i < n; i++) {
int randNum = rand.nextInt(range_r - range_l + 1) + range_l;
arr[i] = randNum;
}
return arr;
}
public static int[] generateRandomArray(int n) {
int arr[] = new int[n];
Random rand = new Random();
for (int i = 0; i < n; i++) {
int randNum = rand.nextInt();
arr[i] = randNum;
}
return arr;
}
public static int[] generateNearlyOrderdArray(int n, int swapTimes) {
int arr[] = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = i;
}
Random random = new Random();
for (int i = 0; i < swapTimes; i++) {
int posx = random.nextInt(n);
int posy = random.nextInt(n);
int temp = posx;
posx = posy;
posy = temp;
}
return arr;
}
public static int[] copyIntArray(int a[], int n) {
int arr[] = new int[n];
for (int i = 0; i < a.length; i++) {
arr[i] = a[i];
}
return arr;
}
}
