Python使用Quicksort、Quickselect与选择排序计算有序数组中位数

计算中位数的核心逻辑和选用的排序算法无关，统一规则如下：

1. 对待计算的数组完成升序排序
2. 数组长度n为奇数时，中位数为排序后数组索引n//2位置的元素
3. 数组长度n为偶数时，中位数为排序后数组索引n//2 - 1和n//2位置元素的算术平均值

基于Quicksort（快速排序）的实现 #

快速排序是分治思路的排序算法，以下实现选择数组中间元素作为基准值，能降低有序输入场景下触发最坏时间复杂度的概率，排序完成后直接按规则提取中位数即可，平均时间复杂度为O(nlogn)，适合绝大多数常规数据量场景。

def quicksort(arr):
    # 递归边界：数组长度不超过1时本身有序
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left_part = [x for x in arr if x < pivot]
    equal_part = [x for x in arr if x == pivot]
    right_part = [x for x in arr if x > pivot]
    return quicksort(left_part) + equal_part + quicksort(right_part)

def calc_median_quicksort(arr):
    if not arr:
        raise ValueError("输入数组不能为空")
    sorted_arr = quicksort(arr)
    n = len(sorted_arr)
    mid_pos = n // 2
    if n % 2 == 1:
        return sorted_arr[mid_pos]
    return (sorted_arr[mid_pos - 1] + sorted_arr[mid_pos]) / 2

简单测试示例：

print(calc_median_quicksort([3,1,2,5,4]))  # 奇数长度数组，输出3
print(calc_median_quicksort([1,3,2,4]))    # 偶数长度数组，输出2.5

基于Selection sort（选择排序）的实现 #

选择排序逻辑非常直观，不需要递归逻辑：每一轮遍历未排序的数组区间，找到区间内的最小值，交换到未排序区间的起始位置，循环直到整个数组有序。它的时间复杂度稳定为O(n²)，仅适合数组长度极小的场景，优势是实现简单、调试成本低。

def selectionsort(arr):
    # 拷贝原数组，避免修改输入的原始数据
    work_arr = arr.copy()
    n = len(work_arr)
    for i in range(n):
        min_index = i
        # 遍历未排序区间找最小值索引
        for j in range(i + 1, n):
            if work_arr[j] < work_arr[min_index]:
                min_index = j
        # 交换最小值到已排序段的末尾
        work_arr[i], work_arr[min_index] = work_arr[min_index], work_arr[i]
    return work_arr

def calc_median_selectionsort(arr):
    if not arr:
        raise ValueError("输入数组不能为空")
    sorted_arr = selectionsort(arr)
    n = len(sorted_arr)
    mid_pos = n // 2
    if n % 2 == 1:
        return sorted_arr[mid_pos]
    return (sorted_arr[mid_pos - 1] + sorted_arr[mid_pos]) / 2

两种实现的简单对比 #

• 快速排序版本：平均运行效率更高，递归写法在数组长度极大时可能触发递归深度限制，可根据需求改写为原地快排+尾递归优化适配更大数据量
• 选择排序版本：无递归开销，代码逻辑直白不容易写错，但数据量超过1000量级后运行速度会明显变慢，仅适合小规模数据场景

注意：以上两个实现都保留了原始输入数组不被修改，如果不需要保留原数组，选择排序版本可以去掉拷贝步骤直接在原数组上操作，进一步降低内存占用。

内容的提问来源于stack exchange，提问作者Shuvo31