原理
1丶设置第一个元素为标记数
2、将小于标记数的放在标记数的左边，大于中间数的放在中间数的右边
3、左边所有元素执行1操作做，右边所有元素执行1操作
Go代码
package main
import (
"fmt"
)
func main() {
arr := []int{4, 3, 9, 6}
sort(arr)
}
func sort(arr []int) {
merge(arr, 0, len(arr)-1)
}
func merge(arr []int, start int, end int) {
if start >= end {
return
}
key := arr[start]
li := start
ri := end
for li != ri {
for li < ri && arr[ri] >= key {
ri--
}
for li < ri && arr[li] <= key {
li++
}
if li < ri {
arr[li], arr[ri] = arr[ri], arr[li]
}
}
arr[li], arr[start] = key, arr[li]
merge(arr, start, li-1)
merge(arr, li+1, end)
}
