寻找未排序数组中第k小元素的最优算法及实现咨询

Quickselect算法实现 #

Quickselect是快速排序的变种，核心通过分区操作缩小查找范围，无需完全排序数组。平均时间复杂度O(n)，最坏情况O(n²)，但通过随机选择基准元素（pivot）可将最坏情况概率降到极低。

实现步骤 #

1. 随机选一个基准元素，将数组分成三部分：小于基准、等于基准、大于基准的元素。
2. 根据基准位置判断第k小元素的分区：
   • 若小于基准的元素数量≥k，递归处理左分区
   • 若小于+等于基准的元素数量<k，递归处理右分区，调整k为k - (小于+等于的数量)
   • 否则，基准元素就是第k小元素

Python代码示例 #

针对示例数组[12, 3, 5, 7, 19]，查找第3小元素（结果为7）：

import random

def quickselect(arr, k):
    # k从1开始计数
    if not arr:
        return None
    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]
    
    len_left = len(left)
    len_mid = len(mid)
    
    if k <= len_left:
        return quickselect(left, k)
    elif k > len_left + len_mid:
        return quickselect(right, k - len_left - len_mid)
    else:
        return pivot

# 测试示例
arr = [12, 3, 5, 7, 19]
print(quickselect(arr, 3))  # 输出7

原地版本（节省内存，适合大数据集）：

import random

def partition(arr, low, high):
    pivot_idx = random.randint(low, high)
    arr[pivot_idx], arr[high] = arr[high], arr[pivot_idx]
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1

def quickselect_inplace(arr, k, low=0, high=None):
    # k从1开始计数
    if high is None:
        high = len(arr) - 1
    if low == high:
        return arr[low]
    
    pivot_pos = partition(arr, low, high)
    target_idx = k - 1  # 转换为0索引位置
    if pivot_pos == target_idx:
        return arr[pivot_pos]
    elif pivot_pos > target_idx:
        return quickselect_inplace(arr, k, low, pivot_pos - 1)
    else:
        return quickselect_inplace(arr, k - (pivot_pos - low + 1), pivot_pos + 1, high)

# 测试示例
arr = [12, 3, 5, 7, 19]
print(quickselect_inplace(arr, 3))  # 输出7

更优替代方案 #

1. Introselect算法 #

Quickselect的最坏O(n²)仍有概率发生，Introselect解决了这个问题：先尝试Quickselect，若递归深度超过阈值（如log n），则切换到中位数的中位数算法（保证最坏O(n)）或堆排序。Python标准库heapq.nsmallest在k较大时，底层会切换到Introselect，兼顾平均性能和最坏情况稳定性。

使用示例：

import heapq

arr = [12, 3, 5, 7, 19]
print(heapq.nsmallest(3, arr)[-1])  # 输出7

k远小于数组长度时，时间复杂度O(n log k)，比Quickselect稍差但实现简单；k接近数组长度时，退化为O(n)算法。

2. 中位数的中位数算法 #

通过分组取中位数，递归取中位数的中位数作为基准，确保分区后左右子数组大小不超过3/4n，保证最坏O(n)复杂度。但常数因子大，实际性能通常不如带随机pivot的Quickselect，仅用于对最坏情况有严格要求的场景。

边缘情况与注意事项 #

• k的合法性：必须满足1 ≤ k ≤ len(arr)，否则应抛出异常或返回无效值，避免逻辑错误。
• 重复元素：分区逻辑需正确处理等于基准的元素，防止遗漏或无限递归。
• 空数组：处理前先判断数组是否为空，避免索引越界或递归错误。
• 大数据集：优先选择原地版本Quickselect，避免子数组占用过多内存；内存不足时需考虑外部排序结合索引查找。
• 最坏情况规避：禁止固定选首尾元素作为基准，必须用随机pivot或中位数的中位数，防止有序/逆序数组上出现O(n²)性能退化。

内容的提问来源于stack exchange，提问作者Sihal Fernando