[TOC] ## 歸并排序 歸并排序是一種分治策略的排序算法。它是一種比較特殊的排序算法，通過遞歸地先使每個子序列有序，再將兩個有序的序列進行合并成一個有序的序列。 歸并排序是唯一一個有穩定性保證的高級排序算法，某些時候，為了尋求大規模數據下排序前后，相同元素位置不變，可以使用歸并排序 ## 算法介紹 1. 先申請一個輔助數組，長度等于兩個有序數組長度的和。 2. 從兩個有序數組的第一位開始，比較兩個元素，哪個數組的元素更小，那么該元素添加進輔助數組，然后該數組的元素變更為下一位，繼續重復這個操作，直至數組沒有元素。 3. 返回輔助數組。 ``` 有序數組A：[3 8 9 11 13] 有序數組B：[1 5 8 10 17 19 20 23] [] 表示比較的范圍。 因為 1 < 3，所以 1 加入輔助數組 有序數組A：[3 8 9 11 13] 有序數組B：1 [5 8 10 17 19 20 23] 輔助數組：1 因為 3 < 5，所以 3 加入輔助數組 有序數組A：3 [8 9 11 13] 有序數組B：1 [5 8 10 17 19 20 23] 輔助數組：1 3 因為 5 < 8，所以 5 加入輔助數組 有序數組A：3 [8 9 11 13] 有序數組B：1 5 [8 10 17 19 20 23] 輔助數組：1 3 5 因為 8 == 8，所以 兩個數都 加入輔助數組 有序數組A：3 8 [9 11 13] 有序數組B：1 5 8 [10 17 19 20 23] 輔助數組：1 3 5 8 8 因為 9 < 10，所以 9 加入輔助數組 有序數組A：3 8 9 [11 13] 有序數組B：1 5 8 [10 17 19 20 23] 輔助數組：1 3 5 8 8 9 因為 10 < 11，所以 10 加入輔助數組 有序數組A：3 8 9 [11 13] 有序數組B：1 5 8 10 [17 19 20 23] 輔助數組：1 3 5 8 8 9 10 因為 11 < 17，所以 11 加入輔助數組 有序數組A：3 8 9 11 [13] 有序數組B：1 5 8 10 [17 19 20 23] 輔助數組：1 3 5 8 8 9 10 11 因為 13 < 17，所以 13 加入輔助數組 有序數組A：3 8 9 11 13 有序數組B：1 5 8 10 [17 19 20 23] 輔助數組：1 3 5 8 8 9 10 11 13 因為數組A已經沒有比較元素，將數組B剩下的元素拼接在輔助數組后面。 結果：1 3 5 8 8 9 10 11 13 17 19 20 23 ``` ### 自頂向下歸并排序 時間復雜度為：`O(nlogn)`  <details> <summary>main.go</summary> ``` package main import "fmt" // 自頂向下歸并排序，排序范圍在 [begin,end) 的數組 func MergeSort(array []int, begin int, end int) { // 元素數量大于1時才進入遞歸 if end-begin > 1 { // 將數組一分為二，分為 array[begin,mid) 和 array[mid,high) mid := begin + (end-begin+1)/2 // 先將左邊排序好 MergeSort(array, begin, mid) // 再將右邊排序好 MergeSort(array, mid, end) // 兩個有序數組進行合并 merge(array, begin, mid, end) } } // 歸并操作 func merge(array []int, begin int, mid int, end int) { // 申請額外的空間來合并兩個有序數組，這兩個數組是 array[begin,mid),array[mid,end) leftSize := mid - begin // 左邊數組的長度 rightSize := end - mid // 右邊數組的長度 newSize := leftSize + rightSize // 輔助數組的長度 result := make([]int, 0, newSize) l, r := 0, 0 for l < leftSize && r < rightSize { lValue := array[begin+l] // 左邊數組的元素 rValue := array[mid+r] // 右邊數組的元素 // 小的元素先放進輔助數組里 if lValue < rValue { result = append(result, lValue) l++ } else { result = append(result, rValue) r++ } } // 將剩下的元素追加到輔助數組后面 result = append(result, array[begin+l:mid]...) result = append(result, array[mid+r:end]...) // 將輔助數組的元素復制回原數組，這樣該輔助空間就可以被釋放掉 for i := 0; i < newSize; i++ { array[begin+i] = result[i] } return } func main() { list := []int{5} MergeSort(list, 0, len(list)) fmt.Println(list) list1 := []int{5, 9} MergeSort(list1, 0, len(list1)) fmt.Println(list1) list2 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3} MergeSort(list2, 0, len(list2)) fmt.Println(list2) } ``` </details> <br/> ### 自底向上歸并排序 <details> <summary>main.go</summary> ``` package main import "fmt" // 自頂向下歸并排序，排序范圍在 [begin,end) 的數組 func MergeSort(array []int, begin int, end int) { // 元素數量大于1時才進入遞歸 if end-begin > 1 { // 將數組一分為二，分為 array[begin,mid) 和 array[mid,high) mid := begin + (end-begin+1)/2 // 先將左邊排序好 MergeSort(array, begin, mid) // 再將右邊排序好 MergeSort(array, mid, end) // 兩個有序數組進行合并 merge(array, begin, mid, end) } } // 歸并操作 func merge(array []int, begin int, mid int, end int) { // 申請額外的空間來合并兩個有序數組，這兩個數組是 array[begin,mid),array[mid,end) leftSize := mid - begin // 左邊數組的長度 rightSize := end - mid // 右邊數組的長度 newSize := leftSize + rightSize // 輔助數組的長度 result := make([]int, 0, newSize) l, r := 0, 0 for l < leftSize && r < rightSize { lValue := array[begin+l] // 左邊數組的元素 rValue := array[mid+r] // 右邊數組的元素 // 小的元素先放進輔助數組里 if lValue < rValue { result = append(result, lValue) l++ } else { result = append(result, rValue) r++ } } // 將剩下的元素追加到輔助數組后面 result = append(result, array[begin+l:mid]...) result = append(result, array[mid+r:end]...) // 將輔助數組的元素復制回原數組，這樣該輔助空間就可以被釋放掉 for i := 0; i < newSize; i++ { array[begin+i] = result[i] } return } func main() { list := []int{5} MergeSort(list, 0, len(list)) fmt.Println(list) list1 := []int{5, 9} MergeSort(list1, 0, len(list1)) fmt.Println(list1) list2 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3} MergeSort(list2, 0, len(list2)) fmt.Println(list2) } ``` </details> <br/>