思路
左部分排好序、右部分排好序、利用 merge 过程让左右整体有序
merge 过程：谁小拷贝谁，直到左右两部分所有的数字耗尽，拷贝回原数组
实现
测试链接：
递归实现
package main
import (
"bufio"
"os"
"strconv"
)
const (
// 题目没有说数据量，按道理是要说的
// 根据实验，长度500以内够用了
// 如果有一天牛客升级了数据量导致出错
// 把这个值改大即可
MAXN = 501
)
var ( // 全局静态变量
arr = [MAXN]int{}
help = [MAXN]int{}
n int
)
func main() {
input := bufio.NewScanner(os.Stdin)
// 设置自定义的分隔函数
input.Split(bufio.ScanWords)
out := bufio.NewWriterSize(os.Stdout, 4096)
for input.Scan() {
n, _ = strconv.Atoi(input.Text())
if n == 0 {
continue
}
for i := 0; i < n; i++ {
input.Scan()
arr[i], _ = strconv.Atoi(input.Text())
}
mergeSort(0, n-1)
out.WriteString(strconv.Itoa(arr[0]))
for i := 1; i < n; i++ {
out.WriteByte(' ')
out.WriteString(strconv.Itoa(arr[i]))
}
out.WriteByte('\n')
out.Flush()
}
}
func mergeSort(left, right int) {
if left == right {
return
}
mid := left + (right-left)>>1
mergeSort(left, mid)
mergeSort(mid+1, right)
merge(left, right, mid)
}
func merge(left, right, mid int) {
i := 0
l := left
r := mid + 1
for l <= mid && r <= right {
if arr[r] < arr[l] {
help[i] = arr[r]
r++
} else {
help[i] = arr[l]
l++
}
i++
}
for l <= mid {
help[i] = arr[l]
l++
i++
}
for r <= right {
help[i] = arr[r]
r++
i++
}
copy(arr[left:right+1], help[:right+1-left])
}master 公式 分析时间复杂度：，，时间复杂度为
非递归实现
以步长为一组进行 merge，步长每次乘二，直到覆盖数组长度
package main
import (
"bufio"
"os"
"strconv"
)
const (
// 题目没有说数据量，按道理是要说的
// 根据实验，长度500以内够用了
// 如果有一天牛客升级了数据量导致出错
// 把这个值改大即可
MAXN = 501
)
var ( // 全局静态变量
arr = [MAXN]int{}
help = [MAXN]int{}
n int
)
func main() {
input := bufio.NewScanner(os.Stdin)
// 设置自定义的分隔函数
input.Split(bufio.ScanWords)
out := bufio.NewWriterSize(os.Stdout, 4096)
for input.Scan() {
n, _ = strconv.Atoi(input.Text())
if n == 0 {
continue
}
for i := 0; i < n; i++ {
input.Scan()
arr[i], _ = strconv.Atoi(input.Text())
}
mergeSort()
out.WriteString(strconv.Itoa(arr[0]))
for i := 1; i < n; i++ {
out.WriteByte(' ')
out.WriteString(strconv.Itoa(arr[i]))
}
out.WriteByte('\n')
out.Flush()
}
}
func mergeSort() {
left, right, mid := 0, 0, 0
for step := 1; step < n; step <<= 1 {
left = 0
for left < n {
mid = left + step - 1
if mid+1 >= n {
// 已经没有右侧了
break
}
right = min(left+step<<1-1, n-1)
merge(left, right, mid)
left = right + 1
}
}
}
func merge(left, right, mid int) {
i := 0
l := left
r := mid + 1
for l <= mid && r <= right {
if arr[r] < arr[l] {
help[i] = arr[r]
r++
} else {
help[i] = arr[l]
l++
}
i++
}
for l <= mid {
help[i] = arr[l]
l++
i++
}
for r <= right {
help[i] = arr[r]
r++
i++
}
copy(arr[left:right+1], help[:right+1-left])
}
// 牛客 go 版本太低，没有内置的 min 函数
func min(a, b int) int {
if a < b {
return a
}
return b
}复杂度分析
- 时间复杂度：
- 空间复杂度：
- merge 时，需要辅助数组
归并排序为什么比 的排序快？因为比较行为没有浪费！
- 选择排序：每一轮比较，只获得了一个最小值
- 冒泡排序：每一轮比较，只将一个最大值移到了正确位置
- 插入排序：每一轮比较，只将一个值插到了正确位置（接下来的轮次没有用到这轮的比较结果，比较行为被浪费）
- 归并排序：每一轮比较，都使得数组部分有序，而这有序部分又为 merge 提供了便利（每一轮的比较行为都没有被浪费）
注意
有些资料说可以用原地归并排序，把额外空间复杂度变成 ，不要浪费时间去学
因为原地归并排序确实可以省空间，但是会让复杂度变成
归并分治
利用归并排序的便利性可以解决很多问题——归并分治
备注
有关排序更多的概念、注意点、闭坑指南，将在后续课程继续