正文

如何用python语言求中位数

小六 /20 浏览量
0819

在Python中，找出中位数可以通过以下几种方法实现：

排序法

对列表进行排序，然后根据列表长度是奇数还是偶数来计算中位数。

```python

def median_sort（data）:

data.sort（）

n = len（data）

if n % 2 == 1:

return data[n // 2]

else:

return （data[n // 2 - 1] + data[n // 2]） / 2

堆排序法
使用两个堆（大顶堆和小顶堆）来维护中位数。大顶堆存放较小的一半数，小顶堆存放较大的一半数。```python
from heapq import *
class MedianFinder:
 def __init__（self）:
 self.small = [] 大顶堆，存放较小的一半数
 self.large = [] 小顶堆，存放较大的一半数
 def addNum（self, num: int） -> None:
 if len（self.small） >= len（self.large）:
 heappush（self.large, -heappushpop（self.small, -num））
 else:
 heappush（self.small, -heappushpop（self.large, num））
 def findMedian（self） -> float:
 if len（self.small） == len（self.large）:
 return （-self.small + self.large） / 2
 return self.large if len（self.large） > len（self.small） else -self.small

快速选择法

使用快速选择算法找到中位数，该算法基于快速排序的partition过程。

```python

def partition（arr, low, high）:

pivot = arr[high]

i = low - 1

for j in range（low, high）:

if arr[j] <= pivot:

i += 1

arr[i], arr[j] = arr[j], arr[i]

arr[i + 1], arr[high] = arr[high], arr[i + 1]

return i + 1

def quick_select（arr, k）:

if len（arr） == 1:

return arr

low, high = 0, len（arr） - 1

while True:

pivot_index = partition（arr, low, high）

if pivot_index == k:

return arr[pivot_index]

elif pivot_index < k:

low = pivot_index + 1

else:

high = pivot_index - 1

def median_quick_select（arr）:

n = len（arr）

if n % 2 == 1:

return quick_select（arr, n // 2）

else:

return 0.5 * （quick_select（arr, n // 2 - 1） + quick_select（arr, n // 2））

以上方法都可以用来计算中位数，选择哪一种方法取决于具体的应用场景和对效率的要求。如果需要实时计算中位数，堆排序法是一个较好的选择，因为它的时间复杂度为O（log n）。如果数据量不是特别大，排序法也是一个简单有效的解决方案。快速选择法可以在平均情况下达到O（n）的时间复杂度。请告诉我您是否需要进一步的帮助或有其他问题

-- 展开阅读全文 --