快速选择算法求数列中位数的代码

快速选择算法是一种基于分治思想的查找算法，用来在未排序的数组中找到第k小（或大）的元素，它的核心原理是在每次划分阶段选出一个“pivot”作为划分点，使得大部分元素都在pivot的一个范围内。如果k等于pivot的位置，则找到了中位数；如果不是，可以根据k与pivot的关系进一步缩小搜索范围。

以下是一个简单的Python版本的快速选择算法来求解数列的中位数：

import random

def quickselect(arr, k):
    if len(arr) == 1:
        return arr[0]
    
    pivot_index = random.randint(0, len(arr)-1)
    pivot = arr[pivot_index]
    arr[pivot_index], arr[-1] = arr[-1], arr[pivot_index]  # Move pivot to the end
    
    lows = [el for el in arr[:-1] if el < pivot]
    highs = [el for el in arr[:-1] if el >= pivot]

    if k < len(lows):
        return quickselect(lows, k)
    elif k < len(arr) - len(highs):  # If k is between pivot and the last element
        return arr[-1]
    else:
        return quickselect(highs, k - len(arr) + len(highs))

# 使用示例
arr = [3, 7, 4, 1, 9, 2, 8, 5, 6]
k = len(arr) // 2  # 如果不知道数组长度，这里可以用中间索引来代替
median = quickselect(arr, k)
print("Median:", median)