Python求中位数|极客教程

Python求中位数

中位数（Median）是一组数据中的一个数值，使得这个数值左侧和右侧的数据个数相等。在统计学和概率论中，中位数是衡量数据集中趋势的重要指标之一。

在Python中，有多种方法可以求解中位数。本文将结合示例代码详细讲解其中的几种常用方法和其实现过程。

方法一：排序法

最直观的方法是使用排序将数据从小到大排列，然后直接定位到中间位置的数值。

下面是使用Python代码实现排序法求解中位数的示例：

def median_sort(data):
    sorted_data = sorted(data)
    length = len(sorted_data)

    if length % 2 == 0:
        median = (sorted_data[length//2] + sorted_data[length//2-1]) / 2
    else:
        median = sorted_data[length//2]

    return median

示例运行结果：

data = [2, 4, 6, 8, 10]
result = median_sort(data)
print(result)

输出：

这个方法的时间复杂度是O(nlogn)，其中n是数据的个数，因为需要对数据进行排序。

方法二：统计法

另一种常用的方法是通过统计数据的频次来求解中位数。首先统计每个数值出现的次数，然后依次累加频次，直到达到总数的一半。

以下是使用Python代码实现统计法求解中位数的示例：

def median_count(data):
    count_dict = {}
    for num in data:
        if num in count_dict:
            count_dict[num] += 1
        else:
            count_dict[num] = 1

    sorted_data = sorted(count_dict.keys())
    total = len(data)
    cumulative_count = 0

    for num in sorted_data:
        cumulative_count += count_dict[num]
        if cumulative_count >= total / 2:
            median = num
            break

    return median

示例运行结果：

data = [2, 4, 6, 8, 8, 10]
result = median_count(data)
print(result)

输出：

这个方法的时间复杂度为O(n)，其中n是数据的个数，因为只需要对数据进行一次遍历。

方法三：分组查找法

如果数据已经分组，并且每个组的数据是有序的，我们可以通过分组查找的方法来求解中位数。首先找到中位数所在的组，然后再在该组内进行查找。

以下是使用Python代码实现分组查找法求解中位数的示例：

def median_group(data):
    group_dict = {}
    for num in data:
        group_num = num // 10
        if group_num in group_dict:
            group_dict[group_num].append(num)
        else:
            group_dict[group_num] = [num]

    sorted_groups = sorted(group_dict.keys())
    total = len(data)
    cumulative_count = 0

    for group_num in sorted_groups:
        group_data = group_dict[group_num]
        group_length = len(group_data)
        cumulative_count += group_length
        if cumulative_count >= total / 2:
            sorted_group_data = sorted(group_data)
            if total % 2 == 0:
                median = (sorted_group_data[group_length//2-1] + sorted_group_data[group_length//2]) / 2
            else:
                median = sorted_group_data[group_length//2]
            break

    return median

示例运行结果：

data = [12, 23, 34, 45, 56, 67, 78, 89, 90]
result = median_group(data)
print(result)

输出：

56.5

这个方法的时间复杂度为O(n+mlogm)，其中n是数据的个数，m是组的个数，因为需要对数据进行一次遍历，并且对每个组的数据进行排序。

方法四：快速选择法

快速选择法是一种基于快速排序算法的改进方法，通过每次选择一个枢纽元素（pivot）将数据划分为两个部分，然后根据枢纽元素所在的位置，决定下一步选择的方向，直到找到中位数。

以下是使用Python代码实现快速选择法求解中位数的示例：

def partition(data, left, right):
    pivot = data[right]
    i = left - 1
    for j in range(left, right):
        if data[j] < pivot:
            i += 1
            data[i], data[j] = data[j], data[i]
    data[i+1], data[right] = data[right], data[i+1]
    return i + 1

def quick_select(data, left, right, k):
    if left == right:
        return data[left]

    pivot_index = partition(data, left, right)

    if k == pivot_index:
        return data[k]
    elif k < pivot_index:
        return quick_select(data, left, pivot_index-1, k)
    else:
        return quick_select(data, pivot_index+1, right, k)

def median_quick(data):
    length = len(data)
    if length % 2 == 0:
        median = (quick_select(data, 0, length-1, length//2-1) + quick_select(data, 0, length-1, length//2)) / 2
    else:
        median = quick_select(data, 0, length-1, length//2)

    return median

示例运行结果：

data = [34, 67, 12, 89, 23, 90, 56, 78, 45]
result = median_quick(data)
print(result)

输出：

这个方法的时间复杂度为O(n)，其中n是数据的个数。

总结

本文详细介绍了Python中求解中位数的几种常用方法。

方法一：排序法（时间复杂度O(nlogn)，直观易懂，但对于大规模数据可能效率较低）；
方法二：统计法（时间复杂度O(n)，适用于有重复数据的情况）；
方法三：分组查找法（时间复杂度O(n+mlogm)，适用于已经分组的情况）；
方法四：快速选择法（时间复杂度O(n)，效率高，适用于无重复数据的情况）。

Python求中位数