算法设计：从一个很大很大的数组里找前N个最大数的思路之一

这里先讲一种类似于快速排序的方法。注意题目要求，不要求完全排序，只要求最快解决问题！这个题是我面试NI公司时，对方问我的。原话是从1亿个数据里，找出前一百个最大的。

首先看源码吧：

void main（int a[], int start, int end, int N）//从数组a里，找出前N个最大的。如果是a[100],则start = 0， end = 99.注意这个索 引问题

{
int mid = (start + end)/2;

int i = start, j = end;

while(i<j)

{
while(i<j && a[i]<=a[mid])

i++;

while(i<j && a[j]>=a[mid])

j--;

swap(a[i], a[j]);

}
/*注意这个while出来之后，i一定是等于j的，且从i 到 end是较大的那一端*/

if(end-i+1 == N)

return;

if(end - i+1 > N)

findMaxN(a, i, end, N);

else

findMaxN(a, start, i, N - (end -i +1));

}
再来详细说说思路，如果您看懂了快速排序对此一定不会陌生。首先拿a[mid] 做基准值，然后让i， j从两端开始遍历，如果索引小的那一端数据小于基准值a[mid], 就往前遍历，如果 左边的大于了a[mid], while循环会跳出，记住这时的a[i] 是大于a[mid],

然后类似的思路，从j那一端遍历，当右边的数据a[j ] 小于基准值a[mid],则小while循环会跳出。然后会运行swap（）这个函数，将两个值进行交换 。 这样最外面的while循环出来之后，i一定是等于j的，注意这里i 和j不一定等于当前域中的mid。而且从i到end都是较大的，然后看看较大的那一端的数据有多少个，然后进行遍历。

如果已经等于要找的N个，则跳出函数。如果大于N，则要从i到end为区间内接着找；如果小于N，比如说要找前50个最大的，结果end-i+1才等于20，也就是从i到end有20个较大的数，这就需要从 start（第一次时，可以认为是0）到i 区间内再找50-20 = 30个最大的。

至于swap的函数，利用引用实现如下：

void swap（int &a， int &b）

{

int temp = a；

a = b；

b= temp；}

最后说说，如果这个函数执行完毕了，我怎么访问找到的最大的N个数呢？ 很简单，假设数组长度为n， 从a[n-1], a[n-2]。。。顺序取N个数，就是找到的最大的前N个数据了！这个算法的最大情况时间复杂度是o(n的平方），最好情况是o(n), 平坦下来也是o(n).

等我空我介绍第二种思路，上面代码是即兴写的，源码我一会上传。
http://download.csdn.net/detail/yanzi1225627/4684046