python快速选择

快速选择（QuickSelect）是一种基于快速排序思想的算法，用于在未排序的列表中查找第k小或第k大的元素。与快速排序不同的是，快速选择只需要对列表的一部分进行排序，从而实现更快的查找速度。

以下是一个Python实现快速选择的例子：

import random

def quick_select(nums, k):
    if len(nums) == 1:
        return nums[0]
    pivot = random.choice(nums)
    lows = [num for num in nums if num < pivot]
    highs = [num for num in nums if num > pivot]
    pivots = [num for num in nums if num == pivot]
    if k < len(lows):
        return quick_select(lows, k)
    elif k < len(lows) + len(pivots):
        return pivots[0]
    else:
        return quick_select(highs, k - len(lows) - len(pivots))

# 示例
nums = [3, 7, 2, 1, 8, 6, 5, 4]
k = 3
print(quick_select(nums, k)) # 输出：3

上述代码中，我们首先随机选择一个枢轴元素pivot，然后将列表分为三个部分：小于pivot的元素、等于pivot的元素和大于pivot的元素。接着，我们根据k与lows和pivots的长度的大小关系，递归地在lows或highs中查找第k小的元素。