前置知识：分析随机行为的时间复杂度
随机快速排序
测试链接：
经典随机快速排序（不推荐）
在数组中随机选一个位置，把整个数组划分为 <= 这个数的部分（左侧）和 > 这个数的部分（右侧），把左侧最后一位换成这个数（这个位置的这个数排序到了正确的位置），继续在除最后一位的左侧和右侧进行递归过程
partition：划分、分区
package main
import (
"bufio"
"math/rand"
"os"
"strconv"
"time"
)
const (
MAXN = 100000
)
var (
arr = [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())
for i := 0; i < n; i++ {
input.Scan()
arr[i], _ = strconv.Atoi(input.Text())
}
quickSort(0, n-1)
out.WriteString(strconv.Itoa(arr[0]))
for i := 1; i < n; i++ {
out.WriteByte(' ')
out.WriteString(strconv.Itoa(arr[i]))
}
}
out.Flush()
}
func quickSort(left, right int) {
if left >= right {
return
}
// 牛客 go 版本为 1.14，小于 1.20，没有 globalRand，需要手动加
rand.Seed(time.Now().UnixNano())
r := rand.Intn(right-left+1) + left
mid := partition(left, right, arr[r])
quickSort(left, mid)
quickSort(mid+1, right)
}
func partition(left, right, x int) int {
// arr[left:a] 是 <= x 的范围
a := left
// 记录在 <= x 的区域上任何一个 x 的位置，哪一个都可以
xi := 0
for i := left; i <= right; i++ {
if arr[i] <= x {
arr[i], arr[a] = arr[a], arr[i]
if arr[a] == x {
xi = a
}
a++
}
}
// 把左侧最后一位换成 x
arr[xi], arr[a-1] = arr[a-1], arr[xi]
return a - 1
}荷兰国旗问题优化随机快速排序（推荐）
划分时，划分成三个部分：<x、=x、>x
递归 <x 和 >x 部分，=x 部分全部都在正确位置了
荷兰国旗问题的优化点：选出一个数字 x，数组在划分时会搞定所有值是 x 的位置
package main
import (
"bufio"
"math/rand"
"os"
"strconv"
"time"
)
const (
MAXN = 100000
)
var (
arr = [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())
for i := 0; i < n; i++ {
input.Scan()
arr[i], _ = strconv.Atoi(input.Text())
}
quickSort(0, n-1)
out.WriteString(strconv.Itoa(arr[0]))
for i := 1; i < n; i++ {
out.WriteByte(' ')
out.WriteString(strconv.Itoa(arr[i]))
}
}
out.Flush()
}
func quickSort(left, right int) {
if left >= right {
return
}
// 牛客 go 版本为 1.14，小于 1.20，没有 globalRand，需要手动加
rand.Seed(time.Now().UnixNano())
r := rand.Intn(right-left+1) + left
l, r := partition(left, right, arr[r])
quickSort(left, l)
quickSort(r, right)
}
func partition(left, right, x int) (int, int) {
// [left, l) 是 < x 的范围
l := left
// (r, right] 是 > x 的范围
r := right
for i := left; i <= r; {
if arr[i] < x {
arr[i], arr[l] = arr[l], arr[i]
l++
i++
} else if arr[i] > x {
arr[i], arr[r] = arr[r], arr[i]
r--
} else {
i++
}
}
return l - 1, r + 1
}时空复杂度分析
核心点：怎么选择数字？
-
选择的数字是当前范围上的固定位置，比如范围上的最右数字，那么就是普通快速排序
-
选择的数字是当前范围上的随机位置，那么就是随机快速排序
-
普通快速排序：时间复杂度 ，额外空间复杂度
-
随机快速排序：时间复杂度 ，额外空间复杂度
空间复杂度：递归压栈的空间
取随机值是一个常数时间比较大的常数操作，直接取固定位置从常数时间来看要更优，但是为什么最后的复杂度相反？且差距这么大？
- 普通快速排序：总能写出最差情况的数据输入，使划分的左侧或右侧部分为空，算法时间复杂度退化为 ，空间复杂度退化为
- 随机快速排序：没法列出最差情况，因为是随机过程，结合来看每一次选中的位置，从概率期望上来说会趋向“平分”左右侧
概率期望证明较为复杂，算法导论-7.4.2 有详细证明