在数据处理和图像分析中，中位数常常被用于数据的去噪、前景背景分割等任务。计算中位数的常见方法有两种：直方图方法 和 直接排序方法。每种方法有不同的实现原理，并适用于不同类型的数据。本文将详细介绍这两种方法的工作原理，并对其时间复杂度和空间复杂度进行分析。
一、直方图方法
直方图方法通过统计数据中每个数值的出现频率，利用频率分布来计算中位数。这种方法特别适用于数值范围较小的情况，以下是直方图方法的具体步骤：
1. 统计频率
首先，对所有数据进行遍历，统计每个数值出现的次数。数据集中的每个数值对应一个频率，这些频率值组成一个 频率数组。如果数据的取值范围很大，可能需要为每个可能的数值创建一个数组或哈希表来存储其频率。
2. 计算累计频率（CDF）
接下来，我们根据频率数组计算累计频率。累计频率表示从最小数值到当前数值所有数值的总和。累计频率数组的每个元素代表了该数值及之前所有数值的频率总和。
3. 查找中位数
最终，通过扫描累计频率数组，找到累计频率值等于数据总数一半的位置。中位数对应于这个位置的数值。
时间复杂度与空间复杂度
时间复杂度：计算频率数组需要遍历数据集一次，因此为 O(N)，其中 N 是数据的数量。计算累计频率需要扫描频率数组，复杂度为 O(m)，其中 m 是不同数据值的数量。查找中位数需要遍历累计频率数组一次，复杂度为 O(m)<