歸併排序 nO(lgn) 稽核中

大家好，我是藍胖子，我一直相信程式設計是一門實踐性的技術，其中演演算法也不例外，初學者可能往往對它可望而不可及，覺得很難，學了又忘，忘其實是由於沒有真正搞懂演演算法的應用場景，所以我準備出一個系列，囊括我們在日常開發中常用的演演算法，並結合實際的應用場景，真正的感受演演算法的魅力。

程式碼已經上傳github

https://github.com/HobbyBear/codelearning/tree/master/mergesort

演演算法原理

每每實現演演算法的時候，我總是傾向於用文字將演演算法的邏輯描述出來，當你能清晰的描述演演算法邏輯的時候，實現起來就是水到渠成的事情。

所以，我們接下來首先看下歸併排序的演演算法邏輯。歸併排序的時間複雜度是nO(lg n)，它要求每次 將陣列一分為二,被分割的陣列又一分為二直至不能被分割，最後由底向上進行兩兩合併。你可以看到，假設陣列長度是n，整個過程一共有lg n層，每一層需要對n個元素進行合併，所以時間複雜度是nO(lg n)。如下圖所示:

合併的過程是將合併的兩個有序陣列的元素變成一個有序陣列的過程，我們把這個過程稱為merge，於是我們將 歸併排序的詳細步驟總結為如下的步驟，

1，將陣列一分為二,形成左右子陣列。

2，對左子陣列進行歸併排序。

3，對右子陣列進行歸併排序。

4，對左右子陣列進行merge。

詳細的merge操作我們可以在O(n)時間複雜度內完成，詳細步驟可以總結如下:

1，用i表示左子陣列當前遍歷的元素，j表示右邊子陣列當前遍歷的元素。

2，建立一個新陣列，用於儲存排好序的元素，開始遍歷左右子陣列，如果左右子陣列都沒有遍歷完，則比較各自當前遍歷元素的大小，將小的元素複製到新陣列，然後移動小元素所在陣列當前遍歷的指標指向下一個遍歷元素。

3，如果其中一個陣列遍歷完成則只需要將，沒有遍歷完的那個陣列剩下元素全部複製到新陣列即可。

實現

瞭解了上述詳細步驟後，我們可以很容易的用遞迴實現上述歸併排序邏輯。

// 將陣列[l...r]一分為二，分別對左右陣列進行排序，然後對排序好的陣列進行歸併  
func mergesort(arr []int, l, r int) {  
   if l >= r {  
      return  
   }  
   mid := (l + r) / 2  
   mergesort(arr, l, mid)  
   mergesort(arr, mid+1, r)  
   merge(arr, l, mid, r)  
}

merge 部分程式碼如下，

寫演演算法邏輯的時候一定要注意邊界條件，比如我這裡定義的是閉區間，那麼下面的邏輯都是按閉區間去寫的。

// [l...mid] [mid+1...r]  
func merge(arr []int, l, mid, r int) {  
   arr1 := arr[l : mid+1]  
   arr2 := arr[mid+1 : r+1]  
   newArr := make([]int, r-l+1)  
   i := 0 // 當前遍歷元素  
   j := 0  
   k := 0  
   for i < len(arr1) && j < len(arr2) {  
      if arr1[i] > arr2[j] {  
         newArr[k] = arr2[j]  
         j++  
         k++  
         continue  
      }  
      newArr[k] = arr1[i]  
      k++  
      i++  
   }  
   if i == len(arr1) {  
      copy(newArr[k:], arr2[j:])  
   }  
   if j == len(arr2) {  
      copy(newArr[k:], arr1[i:])  
   }  
   copy(arr[l:], newArr)  
}

應用 求解逆序對的數量

關於歸併排序的一個應用，我這裡用leetcode一個題舉例，這個題是leetcode 的劍指 Offer 51題，求解逆序對。

劍指 Offer 51. 陣列中的逆序對  
困難  
1.1K  
相關企業  
在陣列中的兩個數位，如果前面一個數位大於後面的數位，則這兩個數位組成一個逆序對。輸入一個陣列，求出這個陣列中的逆序對的總數。  
  
範例 1:  
輸入: [7,5,6,4]  
輸出: 5  
  
限制：  
  
0 <= 陣列長度 <= 50000

這道題可以採用歸併排序的思想，在merge時，得到逆序對的數量，如下,

merge時的兩個陣列是有序的，且歸併排序的左右陣列的相對順序是不變的，當右邊陣列合併到左邊陣列時，如果左邊的陣列元素大，則說左邊陣列當前遍歷的元素和其以後的元素都可以和右邊的陣列構成一個逆序對。

所以我們可以在merge的程式碼邏輯中新增一段累計逆序對的邏輯，如下:

func mergeCopy(arr []int, l, mid, r int, cnt *int) {  
   arr1 := arr[l : mid+1]  
   arr2 := arr[mid+1 : r+1]  
   newArr := make([]int, r-l+1)  
   i := 0 // 當前遍歷元素  
   j := 0  
   k := 0  
   for i < len(arr1) && j < len(arr2) {  
      if arr1[i] > arr2[j] {  
         newArr[k] = arr2[j]  
         //  新增cnt 變數用於儲存逆序對的數量
         *cnt += len(arr1) - i  
         j++  
         k++  
         continue  
      }  
      newArr[k] = arr1[i]  
      k++  
      i++  
   }  
   if i == len(arr1) {  
      copy(newArr[k:], arr2[j:])  
   }  
   if j == len(arr2) {  
      copy(newArr[k:], arr1[i:])  
   }  
   copy(arr[l:], newArr)  
}