package main import ( "fmt" ) var tmp [len(src)]int var src = [7]int{2, 4, 9, 7, 6, 1, 9} //对排序好的分数组进行合并 func Merge(left, m, right int) { i := left j := left //标示把排序好的数放到临时数组的那个index w := m + 1 //比较,把比较小的数字放到临时数组中去 for i <= m && w <= right { if src[i] >= src[w] { tmp[j] = src[w] w += 1 } else { tmp[j] = src[i] i += 1 } j += 1 } //把剩余数组中的数字依次copy到临时数组中去 for i <= m { tmp[j] = src[i] i += 1 j += 1 } for w <= right { tmp[j] = src[w] w += 1 j += 1 } //把临时数组的数据copy到原数组中 for left <= right { src[left] = tmp[left] left += 1 } } func MergeSort(left, right int) { if left >= right { return } m := (left + right) / 2 MergeSort(left, m) MergeSort(m+1, right) Merge(left, m, right) } func main() { MergeSort(0, len(src)-1) fmt.Println(src) }
归并排序是经典的divide conquer算法。基本思想很简单,但是写代码的时候,要小心各种边界值和index的变换。
有疑问加站长微信联系(非本文作者)