参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series
本笔记包括了随机快速排序和随机选择算法的原理与实现，涵盖了荷兰国旗问题优化、时间复杂度分析等内容，包括了class023 -> class024的内容

023【必备】随机快速排序

快速排序的基本思想

快速排序是一种高效的分治排序算法，其核心思想是：

选择基准元素（pivot）：从数组中选择一个元素作为基准值pivot
数组划分：将数组重新排列，使得所有小于基准值的元素放在基准值前面，所有大于基准值的元素放在基准值后面
递归排序：对基准值两侧的子数组递归地应用快速排序

随机化的重要性

为什么需要随机化？

普通快速排序：固定选择位置（如最右元素）作为基准，最坏情况时间复杂度为O(n²)
随机快速排序：随机选择基准元素，期望时间复杂度为O(n log n)

1 2	# 随机选择基准元素是关键 x = arr[random.randint(l, r)] # 在[l,r]范围内随机选择

测试链接 ：https://www.luogu.com.cn/problem/P1177

经典快速排序实现（不推荐）

def quickSort1(l, r):
    # l == r，只有一个数
    # l > r，范围不存在，不用管
    if l >= r:
        return
    # 随机这一下，常数时间比较大
    # 但只有这一下随机，才能在概率上把快速排序的时间复杂度收敛到O(n * logn)
    # l......r 随机选一个位置，x这个值，做划分
    x = arr[random.randint(l, r)]
    mid = partition1(l, r, x) #会返回x的下标即index
    quickSort1(l, mid - 1)
    quickSort1(mid + 1, r)

# 已知arr[l....r]范围上一定有x这个值
# 划分数组 <=x放左边，>x放右边
# 并且确保划分完成后<=x区域的最后一个数字是x
def partition1(l, r, x):
    # a : arr[l....a-1]范围是<=x的区域
    # xi : 记录在<=x的区域上任何一个x的位置，哪一个都可以
    a = l            # 初始化指针a，表示<=x区域的右边界，初值为l
    xi = 0           # 初始化xi，用于记录<=x区域内某一个x的位置（后面需要与a-1交换）
    for i in range(l, r + 1):   # 从l遍历到r，依次考察每个元素，每一步都会i++（重要，所以这里的代码没有显式写i++）
        if arr[i] <= x:         # 如果当前元素小于等于x
            swap(a, i)          # 把当前元素交换到a位置（即<=x区的后面）
            if arr[a] == x:     # 如果新放到a位置的元素等于x
                xi = a          # 记录下这个位置为xi
            a += 1              # <=x区往右扩展一位
    swap(xi, a - 1)             # 把<=x区域里某个x与区域最后一个元素交换，保证x落在最后
    return a - 1                # 返回<=x区域的最后一个下标（即x最终所在的位置）

def swap(i, j):
    tmp = arr[i]        # 先把arr[i]暂存到tmp
    arr[i] = arr[j]     # arr[i]赋值为arr[j]
    arr[j] = tmp        # arr[j]赋值为tmp，实现arr[i]和arr[j]交换

经典版本的问题：

经典快排每次只排掉一个等于pivot的元素，重复元素多时递归深度大，容易爆栈突变为，pivot 只确定了它自己的最终位置，如果有很多元素等于 pivot，只有一个会归位，剩下的还在“乱序”的子区间里。

荷兰国旗问题优化版（推荐）

荷兰国旗问题是快速排序的重要优化，将数组分为三个区域：

1	[小于x的区域] [等于x的区域] [大于x的区域]

能够一次处理所有等于pivot的元素，递归层数大大降低，所以不会爆栈，每次把所有等于pivot的数都一次性放到中间，只对小于和大于pivot的区间递归

核心优势

一次性处理所有相等元素：将所有等于pivot的元素都放到正确位置
减少递归层数：只需要对小于和大于pivot的区域递归
避免栈溢出：特别适合处理有大量重复元素的数组

实现代码

def quickSort2(l, r):
    if l >= r:
        return
    # 随机这一下，常数时间比较大
    # 但只有这一下随机，才能在概率上把快速排序的时间复杂度收敛到O(n * logn)
    x = arr[random.randint(l, r)]
    partition2(l, r, x)
    # 为了防止底层的递归过程覆盖全局变量
    # 这里用临时变量记录first、last
    left = first[0]
    right = last[0]
    quickSort2(l, left - 1)
    quickSort2(right + 1, r)

# 荷兰国旗问题
first = [0]  # 用list模拟全局变量
last = [0]

# 已知arr[l....r]范围上一定有x这个值
# 划分数组 <x放左边，==x放中间，>x放右边
# 把全局变量first, last，更新成==x区域的左右边界
def partition2(l, r, x):
    first[0] = l
    last[0] = r
    i = l
    while i <= last[0]:
        if arr[i] == x:
            i += 1
        elif arr[i] < x:
            swap(first[0], i)
            first[0] += 1
            i += 1
        else:
            swap(i, last[0])
            last[0] -= 1 #i不变的原因是交换后 i 位置上的新元素还没考察过
#前两种情况i++的原因是x作为基准，在i位置上，顶着左边区域向右推进，此外快速排序算法不需要随机元素的index

荷兰国旗问题详细演示

以数组 [7, 2, 6, 3, 1, 5, 4]，pivot=3 为例：

初始状态：

1 2	arr = [7, 2, 6, 3, 1, 5, 4] first = 0, last = 6, i = 0

Step 1：arr[0] = 7 > 3

与 arr[6] 交换：[4, 2, 6, 3, 1, 5, 7]
last = 5，i 不变

Step 2：arr[0] = 4 > 3

与 arr[5] 交换：[5, 2, 6, 3, 1, 4, 7]
last = 4，i 不变

Step 3：arr[0] = 5 > 3

与 arr[4] 交换：[1, 2, 6, 3, 5, 4, 7]
last = 3，i 不变

Step 4：arr[0] = 1 < 3

与 arr[0] 交换（自己）：不变
first = 1，i = 1

Step 5：arr[1] = 2 < 3

与 arr[1] 交换（自己）：不变
first = 2，i = 2

Step 6：arr[2] = 6 > 3

与 arr[3] 交换：[1, 2, 3, 6, 5, 4, 7]
last = 2，i 不变

Step 7：arr[2] = 3 == 3

i = 3，此时 i > last，循环结束

最终结果：

arr = [1, 2, 3, 6, 5, 4, 7]
[0, 1]: 小于3的区域 [1, 2]
[2, 2]: 等于3的区域 [3]
[3, 6]: 大于3的区域 [6, 5, 4, 7]

时间复杂度分析

随机快速排序的复杂度

时间复杂度：O(n log n) （期望）

每层的划分操作需要O(n)时间
随机选择使得平均递归深度为O(log n)
总时间复杂度：O(n) × O(log n) = O(n log n)

空间复杂度：O(log n) （期望）

来自递归调用栈的深度
最好情况：每次平分，深度为O(log n)
最坏情况：退化为链式递归，深度为O(n)

与普通快速排序对比

普通快速排序

普通快速排序的时间复杂度O(n^2)：固定流程考虑最坏情况（极端不平衡，每次都选到最小或最大元素为主元），每次只能划分出一个元素，剩下的 n-1 继续递归；额外空间复杂度O(n)取得是最坏情况递归的栈的深度。
最好情况：T(n) = 2 * T(n/2) + O(n) = O(n * logn),空间是O(logn)取得是递归的栈的深度。
因为固定流程的话，可以构造出特定的数据，导致每次固定取最右最左的元素都是最差情况。

随机快速排序

随机快速排序，时间复杂度O(n * logn)随机取得是期望理论上每次能比较均匀划分为两半，递归深度约为 log𝑛，每一层的划分操作需要 O(n) 时间。额外空间复杂度O(logn)取得是递归的栈的深度，运气好每次都是区间二分，参考中序二叉树
取期望，每个位置取1/N的权重，最后能证明期望时间复杂度是O(n * logn)，额外空间复杂度O(logn)
关于复杂度的分析，进行定性的说明，定量证明略，因为证明较为复杂，算法导论-7.4.2有详细证明

算法类型	时间复杂度（平均）	时间复杂度（最坏）	空间复杂度（平均）	空间复杂度（最坏）
普通快排	O(n log n)	O(n²)	O(log n)	O(n)
随机快排	O(n log n)	O(n log n)*	O(log n)	O(log n)*

*期望意义下

024【必备】随机选择算法

问题描述

无序数组中第K大的元素问题：

给定整数数组 nums 和整数 k
返回数组中第 k 个最大的元素
要求时间复杂度为 O(n)

关键转换：第K大 = 第(len-k)小（python中）。事实上，若下标从0开始时，第K大等于第(len-k)小（即下标为len-k的元素）；如果下标从1开始，则用len+1-k

随机选择算法原理

随机选择算法是快速排序的变种，核心思想：

只关心目标位置：不需要完全排序，只需要找到第K大的元素
单侧递归：每次只需要在包含目标位置的一侧继续查找
随机化优化：通过随机选择pivot避免最坏情况

测试链接 ：https://leetcode.cn/problems/kth-largest-element-in-an-array/

实现代码

class RandomizedSelect:
    first = 0  # 等于区域的左边界
    last = 0   # 等于区域的右边界

    @staticmethod
    def findKthLargest(nums, k):
        """找第K大元素"""
        # 转换为找第(len-k)小的元素
        return RandomizedSelect.randomizedSelect(nums, len(nums) - k)

    @staticmethod
    def randomizedSelect(arr, i):
        """
        连递归都没用，所以时间复杂度是O(n)左右的量级
        在数组中找到如果排序后在位置i的元素
        时间复杂度：O(n)
        """
        ans = 0
        l = 0
        r = len(arr) - 1
        
        while l <= r:#不断二分的过程中，l和r上是仍然有范围的，直到没有范围才终止
            # 随机这一下，常数时间比较大
            # 但只有这一下随机，才能在概率上把时间复杂度收敛到O(n)
            pivot = arr[l + int(random.random() * (r - l + 1))]
            
            # 使用荷兰国旗问题进行划分
            RandomizedSelect.partition(arr, l, r, pivot)
            
            # 因为左右两侧只需要走一侧
            # 所以不需要临时变量记录全局的first、last，直接用即可
            # 等于的区域即first，last包住的位置，i小于first则去左侧，i大于last则去右侧
            if i < RandomizedSelect.first:
                r = RandomizedSelect.first - 1  # 目标在左侧，pivot左边变成r
            elif i > RandomizedSelect.last:
                l = RandomizedSelect.last + 1   # 目标在右侧，pivot右边变成l
            else:
                ans = arr[i]  # 找到目标
                break
                
        return ans

    @staticmethod
    def partition(arr, l, r, x):
        """荷兰国旗问题划分"""
        RandomizedSelect.first = l
        RandomizedSelect.last = r
        i = l
        
        while i <= RandomizedSelect.last:
            if arr[i] == x:
                i += 1
            elif arr[i] < x:
                RandomizedSelect.swap(arr, RandomizedSelect.first, i)
                RandomizedSelect.first += 1
                i += 1
            else:
                RandomizedSelect.swap(arr, i, RandomizedSelect.last)
                RandomizedSelect.last -= 1

    @staticmethod
    def swap(arr, i, j):
        """交换数组元素"""
        arr[i], arr[j] = arr[j], arr[i]

算法执行示例

以数组 [7, 2, 6, 3, 1, 5, 4]，查找第4小元素（下标为3）为例：

第一轮：

随机选择 pivot = 3
划分后：[1, 2, 3, 6, 5, 4, 7]
等于区域：first = 2, last = 2
目标下标3 > last=2，继续在右侧 [6, 5, 4, 7] 查找

第二轮：

在右侧区域随机选择 pivot = 4
划分后相对位置：[4, 5, 6, 7]（实际在原数组的3,4,5,6位置）
等于区域：first = 3, last = 3
目标下标3 == first == last，找到答案 arr[3] = 4

时间复杂度证明（定性分析）

为什么是O(n)？

每次划分后，下一次只需要处理一侧的数据：

第一次处理：n个元素
第二次处理：n/2个元素（期望）
第三次处理：n/4个元素（期望）
…

总时间：n + n/2 + n/4 + n/8 + ... ≈ 2n

因此期望时间复杂度为 O(n)。

与其他算法的比较

算法	时间复杂度	空间复杂度	特点
完全排序	O(n log n)	O(1)	简单但过度
堆排序K次	O(n + k log n)	O(1)	适合K很小的情况
随机选择	O(n)	O(1)	最优解
BFPRT算法	O(n)	O(log n)	理论最优但常数大

实际应用场景

Top-K问题：找出数组中最大/最小的K个元素
中位数查找：快速找到数组的中位数
分位数计算：统计学中的百分位数计算
数据分析：快速找到数据集中的特定排名元素

关键要点总结

随机化的重要性：
- 避免最坏情况的发生
- 使算法在期望意义下达到最优复杂度
荷兰国旗问题的优势：
- 一次性处理所有相等元素
- 减少递归/迭代次数
- 提高算法稳定性
单侧处理的效率：
- 与完全排序不同，只需要处理包含目标的一侧
- 大大减少了计算量
工程实践建议：
- 对于一般规模的数据，随机选择算法是首选
- 当需要多次查询不同K值时，可以考虑先排序
- 在对稳定性要求极高的场合，可以考虑BFPRT算法

这两个算法（随机快速排序和随机选择）是分治算法的经典应用，展示了随机化在算法设计中的重要作用。掌握这些算法不仅有助于解决实际问题，也为理解更复杂的分治算法奠定了基础。

Blog of AgioPan

数据结构与算法自学笔记（7）- 随机排序&随机选择算法

023【必备】随机快速排序

快速排序的基本思想

随机化的重要性

经典快速排序实现（不推荐）

荷兰国旗问题优化版（推荐）

核心优势

实现代码

荷兰国旗问题详细演示

时间复杂度分析

随机快速排序的复杂度

与普通快速排序对比

024【必备】随机选择算法

问题描述

随机选择算法原理

实现代码

算法执行示例

时间复杂度证明（定性分析）

与其他算法的比较

实际应用场景

关键要点总结