TopN算法与排行榜

TopN算法与排行榜2011-09-30 博客园 zhuweisky在系统中，我们经常会遇到这样的需求：将大量（比如几十万、甚至上百万）的对象进行排序，然后只需要取出最Top的前N名作为排行榜的数据，这即是一个TopN算法。常见的解决方案有三种：

（1）直接使用List的Sort方法进行处理。

（2）使用排序二叉树进行排序，然后取出前N名。

（3）使用最大堆排序，然后取出前N名。

第一种方案的性能是最差的，后两种方案性能会好一些，但是还是不能满足我们的需求。最主要的原因在于使用二叉树和最大堆排序时，都是对所有的对象进行排序，而不是将代价花费在我们需要的少数的 TopN上。为此，我自己实现了TopNOrderedContainer来解决这个问题。

思路是这样的，使用一个长度为N的数组，来存放最Top的N个对象，越Top的对象其在数组中的Index就越小。这样，每次加入一个对象时，就与Index最大的那个对象比较，如果比其更Top，则交换两个对象的位置。如果被交换的对象是数组中的最后一个对象（Index最大），则该对象会被抛弃。如此，可以保证容器中始终保持的都是最Top的N个对象。

接下来我们看具体的实现。

如果一个对象要参与TopN排行榜，则其必须实现IOrdered接口，表明其可以被Top排序。

    /// <summary>
    /// IOrdered 参与排行榜排序的对象必须实现的接口。
    /// </summary>
    /// <typeparam name="TOrderedObj">参与排行榜排序的对象的类型 </typeparam>
    public interface IOrdered<TOrderedObj>
    {
        bool IsTopThan（TOrderedObj other）;
    }

之所以使用泛型参数TOrderedObj，是为了避免派生类在实现IsTopThan方法时，需要将参数other进行向下转换。