Python 中位数算法详解及高效实现161

中位数是统计学中一个重要的概念，它代表着将一组数据排序后处于中间位置的数值。对于包含偶数个元素的数据集，中位数是中间两个数值的平均值。在 Python 中，计算中位数的方法多种多样，本文将深入探讨几种常见的算法，并分析其时间复杂度和空间复杂度，最终提供高效的 Python 代码实现。

一、基本方法：排序后取中间值

最直观的方法是先将数据排序，然后根据数据长度的奇偶性直接获取中位数。这种方法易于理解，但效率较低，时间复杂度为 O(n log n)，其中 n 为数据元素个数，主要取决于排序算法的效率。常用的排序算法包括内置的 `sorted()` 函数（基于 Timsort 算法）和 `()` 方法（原地排序，效率更高）。import statistics
def median_by_sorting(data):
"""计算中位数，通过排序实现。
Args:
data: 一个可迭代对象，包含数值型数据。
Returns:
数据集的中位数。
"""
sorted_data = sorted(data)
n = len(sorted_data)
if n % 2 == 1:
return sorted_data[n // 2]
else:
mid1 = sorted_data[n // 2 - 1]
mid2 = sorted_data[n // 2]
return (mid1 + mid2) / 2
data = [1, 3, 5, 2, 4]
median = median_by_sorting(data)
print(f"中位数 (排序方法): {median}") # 输出：3

二、利用 `statistics` 模块

Python 的 `statistics` 模块提供了一个内置函数 `()`，它可以高效地计算中位数。该函数内部实现可能使用了更优化的算法，例如基于快速选择算法的变体，其平均时间复杂度为 O(n)，在大多数情况下效率更高。import statistics
data = [1, 3, 5, 2, 4]
median = (data)
print(f"中位数 (statistics 模块): {median}") # 输出：3

三、快速选择算法 (Quickselect)

快速选择算法是寻找第 k 个最小元素的一种高效算法，它的平均时间复杂度为 O(n)，最坏情况下为 O(n²)，但可以通过随机化来降低最坏情况出现的概率。 我们可以利用快速选择算法找到中间位置的元素，从而获得中位数。import random
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j]

2025-06-11

上一篇：Python 文件读写函数详解：高效处理文本与二进制数据

下一篇：Python字符串拼接：高效处理中文文本的技巧与最佳实践