有100万个浮点数，从中找出1万个最大的数。写一个高性能的算法 用C语言

Question

如题所述

Answer 1

给你个算法，C语言自己补上

1）以10000为堆的size，建立最小堆；
2）依次拿100W中的数跟堆顶元素比较；
3）如果小，转2）否则跟堆顶元素交换，再调整使之成为堆；
4）最终堆中剩余元素即为所求。追问

你好，能不能帮我写个程序啊，我的面试题，谢谢啊

追答

for (i=int(n/2); i>0; i--){
parent = i;
child = i+i;
while (child<=n){
if ( ((child+1) <= n) && (heap[child] < heap[child+1]) )
child++;

if (heap[child] < heap[parent])
break;

temp = heap[parent];
heap[parent] = heap[child];
heap[child] = temp;

parent = child;
child = parent+parent;
}
}

for (i=0; i<10000; i++){
print heap[1]

temp = heap[1];
heap[1] = heap[n-i];
heap[n-i] = temp;

parent = 1;
child = 2;
while (child<n-i){
if ( (child+1)<(n-i) && heap[child]<heap[child+1])
child++;
if (heap[child] < heap[parent])
break;

temp = heap[parent];
heap[parent] = heap[child];
heap[child] = temp;

parent = child;
child = parent+parent;
}
}

没编译，
自己再稍微改些小地方，应该就差不多。

Answer 2

可能这样做更为高效率(因为100W个浮点数占用差不多8M内存，完全可以在内存中完成):
1.使用快速排序将100W个数先按从大到小进行排序.
2.取排序后的前10000个数.
你可以几中办法都试试,
快速排序算法在C和C++库中提供了函数,C++中快速排序算法效率较高。
或者你也可以在网上找找快速排序的源码,很多的。本回答被提问者采纳

Answer 3

STL 中的 findkth函数：
取出数组中的第k大元素

其复杂度为O(n)，这是最高效率的了

Answer 4

稍等

Answer 5

神啊，谁出的面试题啊，你跟他说，他很有才。。。

这种大数据量当然存到数据库里面再 order by 就好了。还用C语言。。。神马都是浮云啊。