快速排序及其拓展应用

一句话总结快速排序

先将一个元素排好序，然后再将剩下的元素排好序。

快速排序的过程其实就是一颗二叉搜索树构造的过程。

可以对比归并排序：归并排序及其拓展应用

快速排序是二叉树的前序遍历，归并排序是二叉树的后序遍历。

相关题目：
912. 排序数组
215. 数组中的第K个最大元素

# 快速排序
import random

class Quick:
    @staticmethod
    def sort(nums: List[int]):
        Quick.shuffle(nums)  # 为了避免出现耗时的极端情况，先随机打乱
        Quick.sort_helper(nums, 0, len(nums) - 1)  # 排序整个数组（原地修改）

    @staticmethod
    def sort_helper(nums: List[int], low: int, high: int):
        if low >= high:
            return
        p = Quick.partition(nums, low, high)  # 对 nums[lo..hi] 进行切分
        Quick.sort_helper(nums, low, p - 1)  # 排序 nums[lo..p-1]
        Quick.sort_helper(nums, p + 1, high)  # 排序 nums[p+1..hi]

    @staticmethod
    def partition(nums: List[int], low: int, high: int) -> int:
        pivot = nums[low]  # 这里先取最低位作为枢纽元
        i, j = low + 1, high  # 将枢纽元和第一个元素交换后，i 指针指向第二个元素，j 指针指向最后一个元素
        while i <= j:
            while i < high and nums[i] <= pivot:
                i += 1  # 找到第一个大于 pivot 的元素（i 指针停在上一个比 pivot 大的元素处）
            while j > low and nums[j] > pivot:
                j -= 1  # 找到第一个小于等于 pivot 的元素（j 指针停在上一个比 pivot 小或等于的元素处）
            if i >= j:
                break
            Quick.swap(nums, i, j)  # 交换左右两个位置上的元素
        Quick.swap(nums, low, j)  # 将备份的枢纽元移动到正确的位置上
        return j  # j 为划分完成后正确位置的枢纽元

    @staticmethod
    def shuffle(nums: List[int]):
        rng = random.Random()  # 随机数生成器
        for i in range(len(nums)):
            r = i + rng.randrange(len(nums) - i)  # 在剩余的元素中随机选择一个索引
            Quick.swap(nums, i, r)  # 交换这两个元素

    @staticmethod
    def swap(nums: List[int], i: int, j: int):
        nums[i], nums[j] = nums[j], nums[i]  # 交换两个位置上的元素


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

# 215. 数组中的第K个最大元素
from typing import List
import random

def findKthLargest(nums: List[int], k: int) -> int:
    shuffle(nums)
    lo, hi = 0, len(nums) - 1
    k = len(nums) - k
    while lo <= hi:
        p = partition(nums, lo, hi)
        if p < k:
            lo = p + 1
        elif p > k:
            hi = p - 1
        else:
            return nums[p]
    return -1


def partition(nums: List[int], lo: int, hi: int) -> int:
    # 见前文
    pass


def shuffle(nums: List[int]) -> None:
    # 见前文
    pass


def swap(nums: List[int], i: int, j: int) -> None:
    # 见前文
    pass
    
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