一个简单的算法题

Question

有100万个整数，现在只需要其中的最大的10个，除了冒泡（效率感觉太低了）外还有什么好的方法没

Answer 1

bitmap 算法。top k 算法。

Answer 2

bitmap 排序：http://blog.csdn.net/xgdofull/archive/2010/03/28/5424611.aspx
top k 算法：http://blog.donews.com/jiji262/2011/03/baidu_top_k_interview/

Answer 3

你可以尝试下 LINQ 的 OrderBy 和 Take，应该是为 top k 优化的。

Answer 4

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {        
        static void Main(string[] args)
        {
            int[] array = new int[1000000];
            for (int i = 0; i < 1000000; i++)
            {
                array[i] = i;
            }
            var top10 = array.AsParallel().OrderByDescending(x => x).Take(10);
            top10.ToList().ForEach(x => Console.WriteLine(x));
        }
    }
}

Answer 5

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {        
        static void Main(string[] args)
        {
            int[] array = new int[1000000];
            Random r = new Random();
            for (int i = 0; i < 1000000; i++)
            {
                array[i] = r.Next(0, 2147483647);
            }
            var top10 = array.AsParallel().OrderByDescending(x => x).Take(10);
            top10.ToList().ForEach(x => Console.WriteLine(x));
        }
    }
}

Answer 6

事实上不用排序。不过我对 LINQ 的性能太满意了。硬算都是足够快的。

Answer 7

http://blog.donews.com/jiji262/2011/03/baidu_top_k_interview/连接地址上就有堆排序，正在理解中...