主体思路
基于分治思想的归并排序
注意细节
【归排与快排的不同】
- 归并稳定,快排不
- 归并要mid,快排只要数组中一个数
- 归并先递归左右,快排后递归左右
- 归并需要额外的数组tmp,快排不用
标准代码
package main
import (
"bufio"
"os"
"fmt"
)
var (
n int
nums, tmp []int
in = bufio.NewReader(os.Stdin)
out = bufio.NewWriter(os.Stdout)
)
func mergeSort(l, r int) { // 核心:归并排序
if l >= r { return }
mid := l + (r - l) >> 1
mergeSort(l, mid)
mergeSort(mid + 1, r)
k, i, j := 0, l, mid + 1
for i <= mid && j <= r {
if nums[i] <= nums[j] {
tmp[k] = nums[i]
k += 1; i += 1
} else {
tmp[k] = nums[j]
k += 1; j += 1
}
}
for i <= mid { // 如果左边还有剩,继续放
tmp[k] = nums[i]
k += 1; i += 1
}
for j <= r { // 如果右边还有剩,继续放
tmp[k] = nums[j]
k += 1; j += 1
}
for i, j := l, 0; i <= r; i, j = i + 1, j + 1 { nums[i] = tmp[j] } // 把临时数组里的数据复制回数组
}
func main() {
fmt.Fscan(in, &n)
nums, tmp = make([]int, n),
for i := 0; i < n; i++ { fmt.Fscan(in, &nums[i]) }
mergeSort(0, n - 1)
for i := 0; i < n; i++ { fmt.Fprintf(out, "%d ", nums[i]) }
out.Flush()
}