求中位数 - webdancer's Blog

2011山大免试研究生机试题

shuffling(洗牌)

求中位数

webdancer posted @ 2011年10月13日 00:09 in 算法 with tags c 算法 , 1989 阅读

在统计学中,中位数代表一个样本中的一个数值，其可将数值集合划分为相等的上下两部分。

实数 $$x_1,x_2,......,x_n$$ 按大小顺序（升序，降序皆可）排列为 $$x_1^,,x_2^,,......,x_n^,$$ ，实数数列的中位数 $Q_\frac{1}{2}(x)$ 为：

$Q_\frac{1}{2}(x)$ = $\lfloor\frac{(n+1)}{2}\rfloor$

明确了概念后我们可以来解决怎么找中位数了。

算法1：按照定义所说的，首先排序，然后直接返回 $Q_\frac{1}{2}(x)$ 即可。

算法2：在《算法导论》中介绍了如何可以在期望线性时间找到中位数。

思想是：1.按照快排的思想，不断的随机分割。

2.如果随机分割的返回值恰是我们找的，可以返回该位置的数。

3.如果不满足，比较一下返回值与我们找的位置的大小，递归的进行下去，直到满足1.

算法3:

思想是： 1.利用快速排序的思想，不断的的分割。不过没有用递归。

用python实现了一下上面的算法，结果：

algorithm1(ms)	algorithm2(ms)	algorithm3(ms)
0	0	0
9	19	20
140	120	70
2149	1689	780
27480	21479	12480

参考：

1.http://zh.wikipedia.org/wiki/%E4%B8%AD%E4%BD%8D%E6%95%B0

2.算法导论。

[回复]

Liwovosa 说:
2021年5月08日 20:05

You make so many great points here that I read your article a couple of times. Your views are in accordance with my own for the most part. This is great content for your readers. 123movies

[回复]

move In & move out c 说:
2021年9月24日 01:26

Maids may help you to handle all of these tasks. You could hire them for under this move-in sort of service if that may be all you want. On the opposite hand, you could hire them an extra chance after you could have moved set for long-term, regular care of your home. As a new busy specialized, you will not have the time for it to put into this procedure yourself, but you'll be able to still find help to the cleanup a great deal more quickly than you already know.