社区首页 › 编程脚本 › Python数组中位数算法：排序法与随机快速选择实现

脚本专家 发表于 4 天前

Python数组中位数算法：排序法与随机快速选择实现

在Python算法题和日常脚本开发中，求数组中位数是一个高频需求。中位数的定义取决于数组长度 n：n 为奇数时，取排序后中间位置的元素；n 为偶数时，取排序后中间两个元素的平均值。例如 arr = ，排序后为 ，元素个数为奇数，中位数为第 4 个元素 7。再如 arr = ，排序后为 ，元素个数为偶数，中位数为 (5 + 7) / 2 = 6。

下面按实现复杂度从低到高，整理三种常见思路：排序法、随机快速选择，以及基于顺序统计量的最坏情况线性时间方法。前两种给出可直接运行的 Python 代码。

一、朴素排序法
基本思路是先对数组排序，然后判断长度奇偶：奇数返回中间元素，偶数返回中间两个元素的平均值。代码实现如下：


def findMedian(arr):
    n = len(arr)
    # First we sort the array
    arr.sort()
    # check for even case
    if n % 2 != 0:
      return arr
    return (arr[(n - 1) // 2] + arr) / 2.0

if __name__ == '__main__':
    arr =
    ans = findMedian(arr)
    print(ans)


输出：
4.5

该示例中数组排序后为 ，中间两个元素是 4 和 5，因此返回 4.5。时间复杂度为 O(n log n)，主要消耗在排序；辅助空间为 O(1)。注意 arr.sort() 是原地排序，会修改传入的列表，如果调用方不希望原数组被改变，需要先复制一份再传入。

二、随机快速选择法
随机快速选择的思路与快速排序分区类似：随机选择基准元素，将较小元素放到左侧、较大元素放到右侧。如果基准最终落在中间索引，就找到了中位数；否则递归处理左半部分或右半部分。偶数长度数组需要找到中间两个元素，再计算平均值。实现如下：


import random

def swap(arr, i, j):
    arr, arr = arr, arr

def partition(arr, l, r):
    lst = arr
    i = l
    j = l
    while j < r:
      if arr < lst:
            swap(arr, i, j)
            i += 1
      j += 1
    swap(arr, i, r)
    return i

def randomPartition(arr, l, r):
    n = r - l + 1
    pivot = random.randint(0, n - 1)
    swap(arr, l + pivot, r)
    return partition(arr, l, r)

def medianUtil(arr, l, r, k, a, b):
    if l <= r:
      partitionIndex = randomPartition(arr, l, r)

      # find the median of odd number element in arr[]
      if partitionIndex == k:
            b = arr
            if a != -1:
                return
      elif partitionIndex == k - 1:# a & b as middle element of arr[]
            a = arr
            if b != -1:
                return

      # index in first half of the arr[]
      if partitionIndex >= k:
            medianUtil(arr, l, partitionIndex - 1, k, a, b)
      # find the index in second half of the arr[]
      else:
            medianUtil(arr, partitionIndex + 1, r, k, a, b)

def findMedian(arr):
    a = [-1]
    b = [-1]
    n = len(arr)

    if n % 2 == 1:
      medianUtil(arr, 0, n - 1, n // 2, a, b)
      return b
    else:
      medianUtil(arr, 0, n - 1, n // 2, a, b)
      return (a + b) / 2.0

if __name__ == '__main__':
    arr =
    print(findMedian(arr))


输出：
6.5

该示例排序后为 ，中间两个元素是 6 和 7，因此结果为 6.5。这里用 a 和 b 分别记录中间两个位置的值，初始值为 -1 作为未找到标记。时间复杂度方面：最佳情况为 O(1)，平均情况为 O(n)，最坏情况为 O(n^2)；辅助空间为 O(n)。随机化能降低遇到极端分区概率，但并不能从理论上完全消除最坏情况。

三、最坏情况线性时间方法：顺序统计量
这种方法的思路与 quickSelect() 类似，但通过选择能够平衡分割数组的枢轴点，避免一侧元素极少、另一侧元素过多，从而在理论上实现最坏情况线性时间复杂度。数组被平衡分割后，再按照 quickSelect() 的步骤决定从枢轴点左侧还是右侧继续选择。相关实现细节可参考“无序数组中第 K 个最小/最大元素 | 最坏情况下的线性时间复杂度”。原文也指出，虽然该方法理论上表现不错，但前面的随机快速选择方法在实践中通常效果更好。

总结
如果追求代码简洁、数据规模不大，直接排序后取中位数最直观；如果希望平均情况下更快，并且允许修改数组，可以使用随机快速选择；如果关注理论上的最坏情况线性时间，可以进一步研究顺序统计量方法。实际脚本开发中，随机快速选择在平均性能与实现复杂度之间较为均衡，但需要注意它依赖随机分区，最坏情况仍为 O(n^2)。

热心网友2 发表于 4 天前

Re: Python数组中位数算法：排序法与随机快速选择实现

感谢分享，整体脉络很清楚，从排序法到随机快速选择再到理论最坏线性，奇偶情况的例子也讲得很直观。排序法那段很实用，尤其提醒 arr.sort() 会原地修改原数组；如果不想动原数组，用 sorted(arr) 再取中间值会更省心。 随机快速选择这段，贴出来的代码好像有些地方下标被吞掉了：swap 里 arr, arr = arr, arr 没有完成交换，partition 里 if arr < lst 也不太像能跑的比较，b = arr 和 a = arr 看起来也应该是取 partitionIndex 位置的元素。建议把代码再检查或重新贴一遍，不然读者直接复制可能会踩坑。 总结部分很认同：数据量不大直接排序最直观，随机快速选择适合平均性能，第三种理论很好但实现复杂。期待后续补全或修正。

热心网友4 发表于 4 天前

Re: Python数组中位数算法：排序法与随机快速选择实现

这个总结挺清楚的，三种思路的适用场景和复杂度都点到了。排序法那段最直观，代码也完整，提醒 arr.sort() 会原地修改原数组这点很实用。随机快速选择部分思路讲得明白，不过贴出的代码里有些地方看起来像是复制或转义时漏了下标：swap 里两个 arr 直接互换，partition 里判断 arr 和 lst 时也像是少了索引，medianUtil 里给 a、b 记录中间值时同样像是 arr 后面没写下标。实际运行前把这些补上会更稳妥。最坏情况线性时间的方法虽然只给了思路，但提到随机快速选择实践中往往更好，对选型很有帮助。感谢分享，期待后面把第三种的实现也补上。

热心网友5 发表于 4 天前

Re: Python数组中位数算法：排序法与随机快速选择实现

楼主整理得挺清楚，尤其排序法的奇偶判断和两个例子很直观。我这边看随机快速选择那段代码时，有两个地方建议再检查下：swap 函数里写的是 arr, arr = arr, arr，这样没有真正交换下标 i 和 j 的元素；partition 里判断用了 arr &lt; lst，而且 lst 和 arr 指向同一列表，实际运行时分区逻辑可能不会按预期走。帖子里的 &lt; 应该也是转义显示问题。思路和复杂度总结没问题，排序法 O(n log n) 最省心，随机快速选择平均 O(n) 但最坏 O(n^2)，顺序统计量理论线性、实现更复杂。对日常脚本来说，如果数据量不大，直接排序确实最稳；要上随机快速选择的话，最好把交换和分区边界再验一遍。

查看完整版本: Python数组中位数算法：排序法与随机快速选择实现