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

脚本专家

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

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

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

2. def findMedian(arr):
3.     n = len(arr)
4.     # First we sort the array
5.     arr.sort()
6.     # check for even case
7.     if n % 2 != 0:
8.         return arr[n // 2]
9.     return (arr[(n - 1) // 2] + arr[n // 2]) / 2.0
11. if __name__ == '__main__':
12.     arr = [1, 3, 4, 2, 7, 5, 8, 6]
13.     ans = findMedian(arr)
14.     print(ans)

复制代码

输出：
4.5

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

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

2. import random
4. def swap(arr, i, j):
5.     arr[i], arr[j] = arr[j], arr[i]
7. def partition(arr, l, r):
8.     lst = arr[r]
9.     i = l
10.     j = l
11.     while j < r:
12.         if arr[j] < lst:
13.             swap(arr, i, j)
14.             i += 1
15.         j += 1
16.     swap(arr, i, r)
17.     return i
19. def randomPartition(arr, l, r):
20.     n = r - l + 1
21.     pivot = random.randint(0, n - 1)
22.     swap(arr, l + pivot, r)
23.     return partition(arr, l, r)
25. def medianUtil(arr, l, r, k, a, b):
26.     if l <= r:
27.         partitionIndex = randomPartition(arr, l, r)
29.         # find the median of odd number element in arr[]
30.         if partitionIndex == k:
31.             b[0] = arr[partitionIndex]
32.             if a[0] != -1:
33.                 return
34.         elif partitionIndex == k - 1:  # a & b as middle element of arr[]
35.             a[0] = arr[partitionIndex]
36.             if b[0] != -1:
37.                 return
39.         # index in first half of the arr[]
40.         if partitionIndex >= k:
41.             medianUtil(arr, l, partitionIndex - 1, k, a, b)
42.         # find the index in second half of the arr[]
43.         else:
44.             medianUtil(arr, partitionIndex + 1, r, k, a, b)
46. def findMedian(arr):
47.     a = [-1]
48.     b = [-1]
49.     n = len(arr)
51.     if n % 2 == 1:
52.         medianUtil(arr, 0, n - 1, n // 2, a, b)
53.         return b[0]
54.     else:
55.         medianUtil(arr, 0, n - 1, n // 2, a, b)
56.         return (a[0] + b[0]) / 2.0
58. if __name__ == '__main__':
59.     arr = [12, 3, 6, 7, 4, 19]
60.     print(findMedian(arr))

复制代码

输出：
6.5

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

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

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

热心网友2

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

热心网友4

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

热心网友5

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