在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 代码。
一、朴素排序法
基本思路是先对数组排序，然后判断长度奇偶：奇数返回中间元素，偶数返回中间两个元素的平均值。代码实现如下：
- def findMedian(arr):
- n = len(arr)
- # First we sort the array
- arr.sort()
- # check for even case
- if n % 2 != 0:
- return arr[n // 2]
- return (arr[(n - 1) // 2] + arr[n // 2]) / 2.0
- if __name__ == '__main__':
- arr = [1, 3, 4, 2, 7, 5, 8, 6]
- ans = findMedian(arr)
- print(ans)
输出：
4.5
该示例中数组排序后为 [1, 2, 3, 4, 5, 6, 7, 8]，中间两个元素是 4 和 5，因此返回 4.5。时间复杂度为 O(n log n)，主要消耗在排序；辅助空间为 O(1)。注意 arr.sort() 是原地排序，会修改传入的列表，如果调用方不希望原数组被改变，需要先复制一份再传入。
二、随机快速选择法
随机快速选择的思路与快速排序分区类似：随机选择基准元素，将较小元素放到左侧、较大元素放到右侧。如果基准最终落在中间索引，就找到了中位数；否则递归处理左半部分或右半部分。偶数长度数组需要找到中间两个元素，再计算平均值。实现如下：
- import random
- def swap(arr, i, j):
- arr[i], arr[j] = arr[j], arr[i]
- def partition(arr, l, r):
- lst = arr[r]
- i = l
- j = l
- while j < r:
- if arr[j] < 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[0] = arr[partitionIndex]
- if a[0] != -1:
- return
- elif partitionIndex == k - 1: # a & b as middle element of arr[]
- a[0] = arr[partitionIndex]
- if b[0] != -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[0]
- else:
- medianUtil(arr, 0, n - 1, n // 2, a, b)
- return (a[0] + b[0]) / 2.0
- if __name__ == '__main__':
- arr = [12, 3, 6, 7, 4, 19]
- 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)。 |
发表于