归并排序的操作步骤如下:
- 首先将数组一份为二,分别为左数组和右数组
- 若左数组的长度大于1,那么对左数组实施归并排序
- 若右数组的长度大于1, 那么对右数组实施归并排序
- 将左右数组进行合并
代码如下:
package main
import (
"fmt"
)
// mergerSort
func mergerSort(arr []int, a, b int) {
if b-a <= 1 {
return
}
c := (a + b) / 2
mergerSort(arr, a, c)
mergerSort(arr, c, b)
arrLeft := make([]int, c-a)
arrRight := make([]int, b-c)
copy(arrLeft, arr[a:c])
copy(arrRight, arr[c:b])
i := 0
j := 0
for k := a; k < b; k++ {
if i >= c-a {
arr[k] = arrRight[j]
j++
} else if j >= b-c {
arr[k] = arrLeft[i]
i++
} else if arrLeft[i] < arrRight[j] {
arr[k] = arrLeft[i]
i++
} else {
arr[k] = arrRight[j]
j++
}
}
}
func main() {
// 测试代码
arr := []int{9, 8, 7, 6, 5, 1, 2, 3, 4, 0}
fmt.Println(arr)
mergerSort(arr, 0, len(arr))
fmt.Println(arr)
}
有疑问加站长微信联系(非本文作者)