[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/>