大家都出来动动脑子

hyrish

一共有n个数据，先读读入n/5个数据到内存，然后按从小到大排序，再写入文件
然后重复以上操作排序数据并写入文件，然后取每个n/5数据块的最小数据（即第一个数）同时从文件中删除，并对它们组成的新的数据序列从小到大排序并写入一个单独的文件中，重复上一步操作，直到处理完所有的数据，这个新生成的文件中存放的数据即是排序好的数据，要取中间数只需进行一个判断，如果n为偶数取第n/2-1个数，如果为奇数则取n/2个数（除法中是取整数）

fzy8888cn

原帖由 hyrish 于 2007-11-2 10:44 发表
一共有n个数据，先读读入n/5个数据到内存，然后按从小到大排序，再写入文件
然后重复以上操作排序数据并写入文件，然后取每个n/5数据块的最小数据（即第一个数）同时从文件中删除，并对它们组成的新的数据序列 ...

这个办法行的通, 但是引入了外部文件, 有没有其他的办法

yuanchengjun

先计算好，如果有小到大，第几个是要的数。
扫一遍，留下最小的1/5，最大的那个a1；（前1/5）
扫一遍，留下最小的1/5，但都要比a1大；最大的那个a2；（前2/5）
扫一遍，留下最小的1/5，但都要比a2大。（前3/5）。
在第三遍里面，计算一下第几个。

gaocheng

感觉类似外部排序问题~~

tianqio

这个题必须要先排序吧，个人感觉，原因如下：假设已经读完i个数，现在要读i+1个数，这个第i+1个数会让你先前对i个数的处理结果产生i种变化，所以线性的扫描应该是做不出来的。只有先分别对1/5的数据进行排序，然后在操作

emacsnw

每次读入5个数，留下它们的中数。最后内存中是这 n/5 个中数，然后返回这些数的中数。
谁能分析一下当n很大的时候，这样做平均误差不超过多少？呵呵。

ypxing

先将原数组均分为5份,分别排序
然后,按每组的中位数将组排序
例如下面
a1...am
b1...bm
c1...cm
d1...dm
e1...em

a组的中位数小于b组的中位数...

这样a组的前半部分和e组的后半部分就可以去掉了

将剩余的a组的后半部分和e组的前半部分拼成一组
这样还剩4组,对这4组重复前面的过程...

lovesaka

原帖由 yuanchengjun 于 2007-11-2 16:29 发表
先计算好，如果有小到大，第几个是要的数。
扫一遍，留下最小的1/5，最大的那个a1；（前1/5）
扫一遍，留下最小的1/5，但都要比a1大；最大的那个a2；（前2/5）
扫一遍，留下最小的1/5，但都要比a2大。（前3/ ...

这个方法可以

hyrish

楼上的方法很难实施的
“扫一遍，留下最小的1/5”不怎么容易
内存只能容纳1/5的数据，能给出实现方法吗？

konggexian

1. 任取一数a, 把其它所有数与a比较, 记录有多少数大于a或小于a,(分别用count1和count2表示);
2. 如count1==count2或count2-count1==1,则a即为所找的中位数;
3. 如没有找到就换另一数重复1.

其中有很多地方可以优化:
如count1 < count2, 取下一数可以把比a小的都排除;
如count1 > count2, 取下一数可以把比a大的都排除;
如abs(count1 -count2) < n/5, 可快速根据abs(count1 -count2) 的值得到所找中位数;

最差的情况就是比较n*n次