python代码用分治法计算序列的第 k 大的元素

下面是使用分治法计算序列的第 k 大的元素的 Python 代码：

def find_kth_largest(nums, k):
    # 定义递归函数，寻找第 k 大的元素
    def quick_select(left, right, k):
        # 选取一个随机的枢纽元素
        pivot_index = random.randint(left, right)
        pivot = nums[pivot_index]
        # 把枢纽元素放到最右边
        nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
        # 进行 partition 操作
        i = left - 1
        for j in range(left, right):
            if nums[j] >= pivot:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]
        i += 1
        nums[i], nums[right] = nums[right], nums[i]
        # 如果找到了第 k 大的元素，直接返回
        if i == k - 1:
            return nums[i]
        # 如果第 k 大的元素在左边，递归左半部分
        elif i > k - 1:
            return quick_select(left, i - 1, k)
        # 如果第 k 大的元素在右边，递归右半部分
        else:
            return quick_select(i + 1, right, k)

    # 调用递归函数
    return quick_select(0, len(nums) - 1, k)

这个算法的时间复杂度为 $O(n)$，因为每次 partition 操作都会把序列分成两个部分，其中一个部分的大小不超过原序列的一半。