Python利用快速排序思想查找数组第k大元素

阿麦

发布时间：2026-10-12| 2人浏览过

原创

本文介绍一种基于快速排序Partition思想的Python算法，用于高效查找数组中任意第k大的数字。该方法通过递归缩小搜索范围，避免了对整个数组进行完整排序，从而在平均情况下达到O(n)的时间复杂度。文中提供了完整的代码示例及运行结果分析，适合需要处理大规模数据排序或统计场景的开发者参考。

本文分享一个使用Python编写的算法示例，旨在解决从数组中查找任意第k大数字的问题。该方案可供读者参考学习。

算法核心模仿了快速排序中的Partition过程。具体逻辑为：当分区点索引high等于low且小于k时，说明目标值位于后半部分，需在后半段继续搜索；当high等于low且大于k时，说明目标值位于前半部分，需在前半段继续搜索。与标准快排不同，此方法每次递归仅处理包含目标值的那一半区间，从而减少了不必要的排序操作。

def partitionOfK(numbers, start, end, k):
  if k < 0 or numbers == [] or start < 0 or end >= len(numbers) or k > end:
    return None
  low = start
  high = end
  key = numbers[start]
  while low < high:
    while low < high and numbers[high] >= key:
      high -= 1
    numbers[low] = numbers[high]
    while low < high and numbers[low] <= key:
      low += 1
    numbers[high] = numbers[low]
  numbers[low] = key
  if low < k:
    return partitionOfK(numbers, start + 1, end, k)
  elif low > k:
    return partitionOfK(numbers, start, end - 1, k)
  else:
    return numbers[low]
numbers = [3,5,6,7,2,-1,9,3]
print(sorted(numbers))
print(partitionOfK(numbers, 0, len(numbers) - 1, 5))

程序执行后，输出结果为数组中第五大的数值。