快速选择算法与BFPRT算法

题目描述
快速选择算法用于在未排序数组中找到第k小/大的元素，平均时间复杂度O(n)。BFPRT算法是其确定性版本，最坏情况下也能保证O(n)时间复杂度。我将详细讲解这两个算法的原理、区别和实现。

知识讲解

1. 问题定义

   • 输入：包含n个元素的数组arr，整数k（1 ≤ k ≤ n）
   • 输出：数组中第k小的元素（若找第k大，可转换为找第n-k+1小）
   • 要求：高效实现，避免完整排序的O(nlogn)复杂度

2. 快速选择算法原理

   • 基于快速排序的分治思想，但只需处理包含目标的一侧
   • 步骤：
     a. 随机选取枢轴（pivot）
     b. 分区：将数组分为小于、等于、大于枢轴的三部分
     c. 判断：若k落在枢轴左侧，递归处理左段；若在右侧，递归处理右段
   • 示例：在[3,2,1,5,4]中找第3小
     • 选枢轴3 → 分区得[1,2 | 3 | 5,4]
     • 左段长度2 < 3，说明目标在右段 → 在[5,4]中找第1小（因3-2-1=1）

3. BFPRT算法改进

   • 解决快速选择最坏情况O(n²)的问题（如每次选极值作枢轴）
   • 核心：确定性选择枢轴，保证每次至少淘汰30%元素
   • 五元中位数分组：
     a. 将数组每5个分组，最后不足5个自成一组
     b. 每组内部排序取中位数，形成中位数数组
     c. 递归调用BFPRT求中位数数组的中位数作为枢轴

代码实现

import random

def quick_select(arr, k):
    """快速选择算法"""
    if len(arr) == 1:
        return arr[0]
    
    pivot = random.choice(arr)  # 随机选择枢轴
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    if k <= len(left):
        return quick_select(left, k)
    elif k <= len(left) + len(mid):
        return pivot
    else:
        return quick_select(right, k - len(left) - len(mid))

def bfprt_select(arr, k):
    """BFPRT算法"""
    if len(arr) <= 5:  # 小规模直接排序返回
        return sorted(arr)[k-1]
    
    # 五元分组取中位数
    medians = []
    for i in range(0, len(arr), 5):
        group = arr[i:i+5]
        medians.append(sorted(group)[len(group)//2])
    
    # 递归求中位数的中位数作为枢轴
    pivot = bfprt_select(medians, len(medians)//2 + 1)
    
    # 分区操作
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    if k <= len(left):
        return bfprt_select(left, k)
    elif k <= len(left) + len(mid):
        return pivot
    else:
        return bfprt_select(right, k - len(left) - len(mid))

复杂度分析

• 快速选择：
  • 平均情况：每次分区后问题规模减半，T(n) = T(n/2) + O(n) → O(n)
  • 最坏情况：T(n) = T(n-1) + O(n) → O(n²)
• BFPRT：
  • 递归式：T(n) ≤ T(n/5) + T(7n/10) + O(n)
  • 主定理可得T(n) = O(n)，且系数小于20

应用场景

• 快速选择：数据随机分布时效率高，实现简单
• BFPRT：对时间复杂度有严格要求的场景（如实时系统）

通过对比可见，BFPRT以稍大的常数系数换取了稳定的线性时间复杂度，适合需要保证最坏情况性能的场景。