在 a[n] 无序数组找第 K 大的数

Question

在无序数组 a[n] 中找到第 K 大的数可以使用快速选择（QuickSelect）算法来解决。快速选择算法是一种改进的快速排序算法，它可以在平均情况下线性时间复杂度内找到第 K 大的数。

快速选择算法的基本思想是通过分区（Partition）操作将数组划分为两个部分，并且其中一个部分包含了第 K 大的数。具体步骤如下：

1. 选取数组 a 的一个元素作为 pivot（基准元素）。
2. 定义两个指针 left 和 right 分别指向数组的起始和末尾位置。
3. 通过不断交换 left 和 right 指针所指的元素，将数组分为两个部分。左边部分中的所有元素都小于等于 pivot，右边部分中的所有元素都大于等于 pivot。
4. 如果 K 等于左边部分的元素个数加一，则 pivot 就是第 K 大的数。
5. 如果 K 小于左边部分的元素个数加一，则在左边部分递归地调用快速选择算法。
6. 如果 K 大于左边部分的元素个数加一，则在右边部分递归地调用快速选择算法。

下面是使用 Python 实现的快速选择算法的代码：

def quick_select(a, left, right, k):
    # 划分数组
    pivot = partition(a, left, right)

    # 如果 pivot 正好是第 k 大的数，直接返回
    if pivot == k - 1:
        return a[pivot]
    # 如果 pivot 在左边部分，递归调用快速选择算法
    elif pivot > k - 1:
        return quick_select(a, left, pivot - 1, k)
    # 如果 pivot 在右边部分，递归调用快速选择算法
    else:
        return quick_select(a, pivot + 1, right, k)

def partition(a, left, right):
    # 选择最右边的元素为 pivot
    pivot = a[right]

    # 初始化左右指针
    i = left - 1
    j = left

    # 划分数组
    while j < right:
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
        j += 1

    # 将 pivot 放到正确的位置
    a[i + 1], a[right] = a[right], a[i + 1]

    # 返回 pivot 的位置
    return i + 1

可以使用上述代码来求解示例数组 a 中第 K 大的数，其中 a = [10, 7, 8, 9, 1, 5] ， K = 3 ：

a = [10, 7, 8, 9, 1, 5]
K = 3

result = quick_select(a, 0, len(a) - 1, K)
print(result)  # 输出：8

以上代码中， quick_select 函数实现了快速选择算法， partition 函数用于划分数组。