可用分押宝游戏火热进行中...	专题改版：Java Web 专题

挑战性问题，怎么从一大堆大小顺序混乱的双精度数（比如500个）中快速选出12个较大值，并且把这个12个较大指按升序排出来

楼主flyintosky555（飞入蓝天）2005-08-04 08:43:08 在 VC/MFC / 基础类提问

如题？问题点数：50、回复次数：12Top

1 楼flyintosky555（飞入蓝天）回复于 2005-08-04 08:43:22 得分 0

？Top

2 楼vcmute（BCare4 H1Rest Good9!）回复于 2005-08-04 08:53:45 得分 10

先取头12个,取最小值
与下个比较,挤进挤出

若要快速,需加权重值
P.S.感觉有点像搜索Top

3 楼f26511314（我吃巧克力饼）回复于 2005-08-04 09:10:56 得分 0

用STL吧Top

4 楼dirdirdir3（风）回复于 2005-08-04 09:16:43 得分 10

先做个12个数的数组，然后开始比较，把前面12个数放入数组，排好序。
然后从13个开始逐个比，比12个大的就把12个去掉，放入新的，再与12数组里面
的数比，确定位置。这样只需要比较一遍就可以了。Top

5 楼billy145533（$_$）回复于 2005-08-04 09:23:52 得分 10

vcmute
方法可以，不过每次取最小值应该如何取，这些数本身还没有经过排序。而且取完12个值后势必还要进行一次排序。如果排好序再进行比较的话，势必会引起不少的变量值的交换。

我想还是用本人独创的沉铁球算法（随便说的），其实就是和冒泡排序相反，每次把最大的数放到数组的尾部。考虑到值交换比较费时，用交换排序的变体，取好前12位。Top

6 楼atm008（小小菜鸟）回复于 2005-08-04 09:24:42 得分 0

学习
加权重值？Top

7 楼f26511314（我吃巧克力饼）回复于 2005-08-04 09:27:29 得分 0

把这些双精度数依次添加到某个容器（vector 或者 set等等）中，然后让容器从大到小排序，取前12个Top

8 楼hyamw（林锋）回复于 2005-08-04 09:40:31 得分 10

问题主要是在如何提取12个最大的数。
先取前12个数，放入数组daResult中，然后对这12个数排序。从大到小的顺序，接着遍历剩下的所有数，依次与daResult里的12个数比较，如果大于等于第n个数，则把数组daResult中n后面的所有数(包括第n个数)往后移动一位，再把该数添到数组daResult中n的位置。
最后再按升序排一次。
//如果要省掉这一次，刚开始就要按升序排，而且比较移动数的时候就要按从后往前的顺序移动了Top

9 楼flyintosky555（飞入蓝天）回复于 2005-08-04 09:52:20 得分 0

大家不要光是说原理啊，简单写下代码啊，代码应该不会超过100行Top

10 楼f26511314（我吃巧克力饼）回复于 2005-08-04 10:01:34 得分 10

vector <double> vTemp;

for( ) //遍历数组，将每一个值放到vTemp中
{
double xxx;
...
vTemp.back_insert(xxx);
}

sort(vTemp.begin(),vTemp.end()); //排序

vector<double>::iterator iter=double.begin();
for(int i=0;iter!=vStkInfo.end(),i<12;++iter,i++) //前12个就是你想要的值
{

}

Top

11 楼alphapaopao（炮炮）回复于 2005-08-04 10:18:42 得分 0

对 500 排序，时间复杂度 log n
前面 12 个就是你要的

总体时间复杂度 log nTop

12 楼qaz1984（包弥）回复于 2005-08-04 10:38:09 得分 0

upTop