歸并排序的操作步驟如下:
- 首先將數(shù)組一份為二,分別為左數(shù)組和右數(shù)組
- 若左數(shù)組的長度大于1,那么對左數(shù)組實施歸并排序
- 若右數(shù)組的長度大于1, 那么對右數(shù)組實施歸并排序
- 將左右數(shù)組進(jìn)行合并
代碼如下:
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)
}