快速排序利用分治思想：

  1. 确定分界点 x；
    • 可取左边界 l、右边界 r、中间点，也可以随机取。
    • x 点指向的数叫作 pivot。
  2. 用 x 将原先区间划分为两个区间，左区间的值都 <= x，右区间的值都 >= x；
    1. 指针 pl 先开始从左往右移动；
    2. pl 移动到 >= x 的数停住；
      • 必须要有 =
    3. 指针 pr 开始从右往左移动；
    4. pr 移动到 <= x 的数停住；
      • 必须要有 =
    5. 交换 pl 和 pr 指向的两个数；
    6. pl 和 pr 继续按照这一规则移动；
    7. 终止条件是 pl >= pr（双指针交汇），这时 pl 左边的数都 <= x，pr 右边的数都 >= x。
      • 每一步操作后都满足 pr 右边的数 >= x，双指针交汇后 pl 也就没必要继续右移去做检查；同理 pr 也无需继续左移。
  3. 继续递归处理左右两个区间。
    • 递归终止条件是 l >= r，意味着区间里没有数或只有一个数。
    • 递归终止条件满足时，排序已完成。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

func qs (nums []int, l, r int) {
    if l >= r {
        return
    }
    
    // l-1 和 r+1 这样的初始化赋值，使得无需对一次进入循环做特判
    pivot, pl, pr := nums[(l+r)/2], l-1, r+1
    for pl < pr {
        pl++
        // 模板注意点：内层两个 for 循环的比较都不能有等于
        for nums[pl] < pivot {
            pl++
        }
        pr--
        for nums[pr] > pivot {
            pr--
        }
        // 这个判断必须要，否则不需要交换的时候也发生了交换（边界分析）
        if pl < pr {
            nums[pl], nums[pr] = nums[pr], nums[pl]
        }
    }
    
    // 模板注意点
    // [l, pr] 对应 [pr+1, r]，pivot = nums[(l+r)/2]
    // [l, pl-1] 对应 [pl, r]，pivot = nums[(l+r+1)/2]
    qs(nums, l, pr)
    qs(nums, pr+1, r)
}
func quickSort(nums []int) {
    qs(nums, 0, len(nums)-1)
}
func main() {
    var n int
    fmt.Scanf("%d", &n)
    nums := make([]int, n)
    for i := range nums {
        fmt.Scanf("%d", &nums[i])
    }
    
    quickSort(nums)
    for _, n := range nums {
        fmt.Printf("%d ", n)
    }
    fmt.Println()
}

边界点分析：

  1. 原区间包含两个数 [1, 2]，递归区间就是 [l, pr] 对应 [pr+1, r]，此时 pivot 不能取到右边界 r，pivot = nums[(l+r)/2]；
    • 若取到右边界 1（(l+r+1)/2 == 1），此时 pivot == 2；
    • 初始时，l == 0，r == 1；
    • 第一次递归前，pl == 1，pr 未移动，pr == 1（不满足 pl < pr，两个数无需交换）；
    • 接着进行递归，qs(nums, 0, 1) 导致了死循环，而 qs(nums, 2, 1) 没有问题。
  2. 原区间包含两个数 [1, 2]，递归区间就是 [l, pl-1] 对应 [pl, r]，此时 pivot 不能取到左边界 r，pivot = nums[(l+r+1)/2]。
    • 若取到左边界 0（(l+r)/2 == 0），此时 pivot == 1；
    • 初始时，l == 0，r == 1；
    • 第一次递归前，pl 未移动，pl == 0，pr == 0（不满足 pl < pr，两个数无需交换）；
    • 接着进行递归，qs(nums, 0, -1) 没问题，而 qs(nums, 0, 1) 就导致了死循环。

快速选择算法（第 k 个数）利用快速排序算法的思想，每次只需要选半边递归。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

func qs(nums []int, l, r, k int) int {
    // 输入保证 k 一定是合法的，所以区间长度为 1 时对应的数就是答案
    if l == r {
        return nums[l]
    }
    
    pivot, pl, pr := nums[(l+r)/2], l-1, r+1
    for pl < pr {
        pl++
        for nums[pl] < pivot {
            pl++
        }
        pr--
        for nums[pr] > pivot {
            pr--
        }
        if pl < pr {
            nums[pl], nums[pr] = nums[pr], nums[pl]
        }
    }
    
    // 左半区间数的个数
    leftNums := pr-l+1
    if k <= leftNums {
        // 递归左半区间
        return qs(nums, l, pr, k)
    }
    // 递归右半区间
    return qs(nums, pr+1, r, k-leftNums)
}
func quickSelect(nums []int, k int) int {
    return qs(nums, 0, len(nums)-1, k)
}
func main() {
    var n, k int
    fmt.Scanf("%d %d", &n, &k) // 1 ≤k ≤n
    nums := make([]int, n)
    for i := range nums {
        fmt.Scanf("%d", &nums[i])
    }
    
    fmt.Println(quickSelect(nums, k))
}

References