O(n)算法查找数字集合的中位数

def find_median(nums):
    n = len(nums)
    k = (n + 1) // 2  # 中位数的位置

    def partition(left, right):
        pivot = nums[right]  # 选择最右边的元素作为枢轴
        i = left - 1

        for j in range(left, right):
            if nums[j] <= pivot:
                i += 1
                nums[i], nums[j] = nums[j], nums[i]

        nums[i + 1], nums[right] = nums[right], nums[i + 1]
        return i + 1

    def quick_select(left, right):
        if left == right:
            return nums[left]

        pivot_index = partition(left, right)

        if k == pivot_index + 1:
            return nums[pivot_index]
        elif k < pivot_index + 1:
            return quick_select(left, pivot_index - 1)
        else:
            return quick_select(pivot_index + 1, right)

    return quick_select(0, n - 1)