年底總是忙碌的時(shí)候........

作為一個(gè)極少刷算法的java開(kāi)發(fā)，突然刷算法題很吃力，算法里常用到的思想基本不了解，比如分治、動(dòng)態(tài)規(guī)劃、貪心等。淚崩~

這篇文章整理一下排序算法-------歸并排序

基本思想：

歸并排序的主要思想是分治法。主要過(guò)程是：

1. 將n個(gè)元素從中間切開(kāi)，分成兩部分。（左邊可能比右邊多1個(gè)數(shù)）

2. 將步驟1分成的兩部分，再分別進(jìn)行遞歸分解。直到所有部分的元素個(gè)數(shù)都為1。

3. 從最底層開(kāi)始逐步合并兩個(gè)排好序的數(shù)列。

核心思路：

如何將兩個(gè)有序數(shù)列合并成一個(gè)有序數(shù)列？

由于兩個(gè)數(shù)列都已經(jīng)有序，我們只需從兩個(gè)數(shù)列的低位輪番拿出各自最小的數(shù)來(lái)PK就就行了，輸?shù)囊环綖樾≈?，將這個(gè)值放入臨時(shí)數(shù)列，然后輸?shù)囊环嚼^續(xù)拿出一個(gè)值來(lái)PK，直至有一方?jīng)]有元素后，將另一方的所有元素依次接在臨時(shí)數(shù)列后面即可。此時(shí)，臨時(shí)數(shù)列為兩個(gè)數(shù)列的有序合并。歸并排序中的歸并就是利用這種思想。代碼如下：

/**
 * 合并
 */
public static void merge(int[] arr, int l, int mid, int r) {
?
 //定義一個(gè)臨時(shí)數(shù)組存放合并的數(shù)據(jù)
 int[] temp = new int[r - l + 1];
 int i = 0; //temp數(shù)組的索引
 //定義兩個(gè)指針?lè)謩e代表左邊和右邊的索引
 int p1 = l, p2 = mid + 1;
 while (p1 <= mid && p2 <= r) {
   // 比較左右兩部分的元素，哪個(gè)小，把那個(gè)元素填入temp中
   temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
 }
?
 //上面循環(huán)結(jié)束后，將剩余的數(shù)據(jù)放入temp中
 while (p1 <= mid) {
   temp[i++] = arr[p1++];
 }
?
 while (p2 <= r) {
   temp[i++] = arr[p2++];
 }
?
 // 把最終的排序的結(jié)果復(fù)制給原數(shù)組
 for (i = 0; i < temp.length; i++) {
   arr[l + i] = temp[i];
 }
}

圖解思路：

通過(guò)示例圖了解歸并排序的思路。原數(shù)組如下：

img

第一步：分解

首先將數(shù)組分解成兩部分，即19、15、37為一組，12、25為一組，為了區(qū)分，我們起個(gè)名字叫“第一層”，如下圖：

preview

第二步：分解

繼續(xù)分解，19、15為一組，37為一組，12為一組，25為一組，這四組為“第二層”，如下圖：

image

第三步：分解

繼續(xù)分解，此時(shí)只剩下19、15這一組可以分解，分解成19、15，這兩組為“第三層”，如下圖：

image

第四步：歸并

由于所有組都已經(jīng)分解成只有1個(gè)元素，開(kāi)始進(jìn)行歸并，從“高層”開(kāi)始?xì)w并，即先歸并“第三層”，比較“第三層”兩組元素，19 < 15，因此將15排在19前面，由于已經(jīng)沒(méi)有元素，結(jié)束此次歸并，如下圖：

img

第五步：歸并

繼續(xù)歸并，此次歸并“第二層”，這一層有4個(gè)組，進(jìn)行兩兩比較。首先，比較15、19和37：15 < 37，所以15放第一個(gè)位置，接著比較19和37，19 < 37，所以19放第二個(gè)位置，此時(shí)第一組15、19已經(jīng)沒(méi)有元素，于是將37填入15和19之后。接著比較：12和25：12 < 25，所以12放第一個(gè)位置，由于第一組12已經(jīng)沒(méi)有元素，于是將25填入12之后。歸并的結(jié)果如下：

img

第六步：歸并

繼續(xù)歸并，此次歸并“第一層”，這一組有2個(gè)組，第一組：15、19、37，第二組：12、25。同樣的，取兩組的第1個(gè)數(shù)比較：15 > 12，所以12放第1個(gè)位置；接著取第二組的第2個(gè)數(shù)比較：15 < 25，所以15放第2個(gè)位置；接著取第一組的第2個(gè)數(shù)比較：19 < 25，所以19放第3個(gè)位置；接著取第一組的第3個(gè)數(shù)比較：37 > 25，所以25放第4個(gè)位置；由于第二組已經(jīng)沒(méi)有元素，所以37自然歸入第5個(gè)位置。此時(shí)，歸并結(jié)束，最終數(shù)組如下。

image

完整示例步驟如下圖：

image

完整的歸并排序代碼（java）

先分解，再遞歸調(diào)用歸并方法，最后調(diào)用合并方法。

/**
 * 歸并排序
 */
public class MergeSort {
?
?
 /**
 * 歸并排序
 */
 public static void mergeSort(int[] arr) {
   sort(arr, 0, arr.length - 1);
 }
?
?
 /**
 * 分治、遞歸做排序處理
 */
 public static void sort(int[] arr, int l, int r) {
   if (l == r) {
     return;
   }
   int mid = l + ((r - l) >> 1);//分兩部分
   sort(arr, l, mid);//對(duì)左邊數(shù)組處理
   sort(arr, mid + 1, r);//對(duì)右邊數(shù)組處理
   merge(arr, l, mid, r); //合并
?
 }
?
?
 /**
 * 合并
 */
 public static void merge(int[] arr, int l, int mid, int r) {
?
   //定義一個(gè)臨時(shí)數(shù)組存放合并的數(shù)據(jù)
   int[] temp = new int[r - l + 1];
   int i = 0; //temp數(shù)組的索引
   //定義兩個(gè)指針?lè)謩e代表左邊和右邊的索引
   int p1 = l, p2 = mid + 1;
   while (p1 <= mid && p2 <= r) {
     // 比較左右兩部分的元素，哪個(gè)小，把那個(gè)元素填入temp中
     temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
   }
?
   //上面循環(huán)結(jié)束后，將剩余的數(shù)據(jù)放入temp中
   while (p1 <= mid) {
     temp[i++] = arr[p1++];
   }
?
   while (p2 <= r) {
     temp[i++] = arr[p2++];
   }
?
   // 把最終的排序的結(jié)果復(fù)制給原數(shù)組
   for (i = 0; i < temp.length; i++) {
     arr[l + i] = temp[i];
   }
 }
?
?
 public static void main(String[] args) {
?
   int[] arr = {31, 21, 10,  43, 22, 34, 26, 9, 11};
   mergeSort(arr);
   System.out.println(Arrays.toString(arr));
?
 }
}

復(fù)雜度：

時(shí)間復(fù)雜度：O(nlogn)

空間復(fù)雜度：O(N)，歸并排序需要一個(gè)與原數(shù)組相同長(zhǎng)度的數(shù)組做輔助來(lái)排序

穩(wěn)定性：歸并排序是穩(wěn)定的排序算法，temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];這行代碼可以保證當(dāng)左右兩部分的值相等的時(shí)候，先復(fù)制左邊的值，這樣可以保證值相等的時(shí)候兩個(gè)元素的相對(duì)位置不變。

參考文獻(xiàn)

https://zhuanlan.zhihu.com/p/36075856
http://www.itdecent.cn/p/33cffa1ce613