简述计算无序数组中的第 k k 大元素（基于 partition ） ？

计算无序数组中的第 k 大元素可以使用快速选择算法（QuickSelect），它是基于快速排序算法中的分区（partition）操作。快速选择算法的平均时间复杂度为 O(n)，最坏情况下的时间复杂度为 O(n^2)，但在实际应用中，通过随机化枢轴元素（pivot element）的选择，可以将其最坏情况的发生概率降低到几乎可以忽略不计。

以下是快速选择算法的基本步骤：

1. 选择一个枢轴元素（pivot element），并将数组分为两部分：小于枢轴的元素和大于枢轴的元素。这个操作称为分区（partition）。
2. 计算枢轴元素的索引。如果枢轴元素的索引等于 k-1（注意，索引从 0 开始），那么枢轴元素就是第 k 大的元素。
3. 如果枢轴元素的索引小于 k-1，那么第 k 大的元素在枢轴元素的右侧。在右侧子数组中递归执行快速选择算法。
4. 如果枢轴元素的索引大于 k-1，那么第 k 大的元素在枢轴元素的左侧。在左侧子数组中递归执行快速选择算法。

以下是使用 Python 实现的快速选择算法：

import random

def partition(arr, low, high):
    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(arr, k, low, high):
    if low == high:
        return arr[low]

    pivot_index = partition(arr, low, high)

    if k - 1 == pivot_index:
        return arr[k - 1]
    elif k - 1 < pivot_index:
        return quickselect(arr, k, low, pivot_index - 1)
    else:
        return quickselect(arr, k, pivot_index + 1, high)

def find_kth_largest(arr, k):
    return quickselect(arr, k, 0, len(arr) - 1)

# 示例
arr = [3, 2, 1, 5, 6, 4]
k = 2
print(find_kth_largest(arr, k))  # 输出 5

在这个示例中，我们定义了一个无序数组 arr 和一个整数 k，然后调用 find_kth_largest 函数来找到第 k 大的元素。find_kth_largest 函数内部调用了 quickselect 函数来执行快速选择算法。partition 函数用于执行分区操作。