package main // 归并排序 func main() { var a = []int{29, 10, 14, 37, 25, 18, 30} // 创建数组的简写声明 MergeSort(a, 0, len(a)-1) for _, i2 := range a { print(i2, "\t") // 输出每一个值 } } /** MergeSort 实现归并排序(前提列表有序) 包含:分解 + 合并 */ func MergeSort(li []int, low, high int) { if low < high { mid := (low + high) / 2 MergeSort(li, low, mid) MergeSort(li, mid+1, high) Merge(li, low, mid, high) } } /** Merge 归并 */ func Merge(li []int, low, mid, high int) { i, j, lt, t := low, mid+1, make([]int, len(li)), 0 for i <= mid && j <= high { // 将结果拼接到新的数组 if li[i] < li[j] { lt[t], i, t = li[i], i+1, t+1 } else { lt[t], j, t = li[j], j+1, t+1 } } for i <= mid { lt[t], i, t = li[i], i+1, t+1 } for j <= high { lt[t], j, t = li[j], j+1, t+1 } for i, j := low, 0; i <= high; i, j = i+1, j+1 { // 因为存在递归,将数值填回数组 li[i] = lt[j] } }