从100万数据中找出最大10条的最优算法

var collection = new int[] { 1, 5, 9, 3, 4, 6, 2, 4, 8,44,99,33,22 ............ };

var top = 10;

int[] result = new int[top];

foreach (var item in collection)
{
//判断当前值是否大于结果集中的最小值.
if (item > result[0])
{
//将当前值插入结果集
for (int i = 0; i < top + 1; i++)
{
if (i == top || item < result[i])
{
//顺移结果集中小于当前值的值.
for (int j = 0; j < i - 1; j++)
{
result[j] = result[j + 1];
}
result[i - 1] = item;
break;
}
}
}
}

return result; //返回结果.

这个东西叫顺序统计学，有个线性时间的递归算法叫randomize-select，有点像快速排序。

你查一下文献，很快就可以掌握了

用堆排序是o(nlgn)，random-select线性时间就可以做到。。。。用排序是顺序统计学的上界，而且顺序统计学是in place的，不占空间，拜托不懂不要瞎说

快速排序是原地排序，空间复杂度主要是在递归栈上，平均深度是n(lgn)，最坏情况递归深度o(n)，你觉得空间复杂度大么。100w数据o(n)也不算大吧，你的排序算法时间复杂度是o(nlgn)。

问题是顺序统计学不是快速排序，有点类似，也是递归。如果你用chosen-pivot算法，floyd的pivot选择法，可以把最坏事件情况也控制在o(n)内，而且顺序统计学只是递归一半，空间复杂度是绝对的n(lgn)。

我面试的时候有问到过，因为数据量很大，所以要同时考虑空间问题。标准答案是采用堆排序。

具体做法是：
构建一个只有10个元素的min－heap，那么根结点就是这10个数中最小的数，然后开始遍历数组，如果遇到的数比min－heap的根结点还小，直接跳过，遇到比min－heap根结点大的数，就替代根结点，然后对这个min－heap进行维护（也就是排序，保证heap的特征）。那么遍历完数组后，这个min－heap的10个元素就是最大的10个数。

关于堆排序的代码应该不难找