以前在音乐做过一些实时投票，积分排行;单曲、专辑等排行榜;游戏中也有类似的战斗力排名;SNS的游戏又有好友排名等，对于这种的排名算法在此做个总结。
需求背景：
查看前top N的排行用户
查看自己的排行
用户积分变更后，排名及时更新
方案一：
利用MySQL来实现，存放一张用户积分表user_score，结构如下：
取前top N，自己的排行都可以通过简单的sql句子搞定。
算法简单，利用sql的功能，不需要其他复杂逻辑，对于数据量比较少、性能要求不高，可以使用。但是对于海量数据，性能是难以接受的。
方案二：积分排行链表实现
如有1百万用户进行排行，就用一个大小为1，000，000的链表表示积分和排行的对应关系，其中rank[s]表示积分s所对应的排行。初始化时，rank链表可以由user_score表在O(n)的复杂度内估算而至。用户排行的查询和更新基于这个链表来进行。查询积分s所对应的排行直接返回rank[s]即可，复杂度为O(1);当用户积分从s变为s+n，只须要把rank[s]到rank[s+n-1]这n个元素的值降低1即可，复杂度为O(n)。
方案三：用GCC的pb_ds库中有assoc_container来进行实现。
参考如下：tree_order_statistics.cc
存取效率都可以达到O(log(n))，不足就是程序重启后数据会遗失。
方案四：自己实现排序树
大致实现思路如下：
我们可以把[0, 1,000,000)作为一级区间;再把一级区间分为两个2级区间[0, 500,000), [500,000, 1,000,000)，然后把二级区间二分为4个3级区间[0, 250,000), [250,000, 500,000), [500,000, 750,000), [750,000, 1,000,000)，依此类推，最终我们会得到1,000,000个21级区间[0,1), [1,2) … [999,999, 1,000,000)。这实际上是把区间组织成了一种平衡二叉树结构，根结点代表一级区间，每个非叶子结点有两个子结点，左子结点代表低分区间，右子结点代表高分区间。树形分区结构须要在更新时保持一种不变量，非叶子结点的count值总是等于其左右子结点的count值之和。
以后，每次用户积分有变化所须要更新的区间数目和积分变化量有关系，积分变化越小更新的区间层次越低。总体上，每次所须要更新的区间数目是用户积分变量的log(n)级别的，也就是说假如用户积分一次变化在百万级，更新区间的数目在二十这个级别。在这些树状分区积分表的辅助下查询积分为s的用户排行，实际上是一个在区间树上由上至下、由粗到细一步步明晰s所在位置的过程。比如，对于积分499,000，我们用一个年率为0的排行变量来做累加;首先，它属于1级区间的左子树[0, 500,000)，那么该用户排行应当在右子树[500,000, 1,000,000)的用户数count以后，我们把该count值累加到该用户排行变量，进入下一级区间;其次，它属于3级区间的[250,000, 500,000)，这是2级区间的右子树，所以不用累加count到排行变量快手热门算法，直接步入下一级区间;再次，它属于4级区间的…;直到最后我们把用户积分精确定位在21级区间[499,000, 499,001)，整个累加过程完成，得出排行!
虽然，本算法的更新和查询都涉及到若干个操作快手热门算法，但假如我们为区间的from_score和to_score构建索引，这些操作都是基于键的查询和更新，不会形成表扫描，因此效率更高。另外，本算法并不依赖于关系数据模型和SQL运算，可以轻易地改建为NoSQL等其他储存方法，而基于键的操作也很容易引入缓存机制进一步优化性能。进一步，我们可以计算一下树状区间的数量大概为2,000,000，考虑每位结点的大小，整个结构只占用几十M空间。所以，我们完全可以在显存构建区间树结构，并通过user_score表在O(n)的时间内初始化区间树，然后排行的查询和更新操作都可以在显存进行。一般来讲，同样的算法，从数据库到显存算法的性能提高往往可以达到10^5以上;因此，本算法可以达到十分高的性能。
算法特性
优点：结构稳定，不受积分分布影响;每次查询或更新的复杂度为积分最大值的O(log(n))级别，且与用户规模无关，可以应对海量规模;不依赖于SQL，容易改建为NoSQL或显存数据结构。
缺点：算法相对更复杂。
方案五：skiplist的实现
实现方案四的时侯，发现代码比较复杂，调试上去非常不方便。游戏那边有个朋友也实现了个，代码地址：
于是就想到的跳表，发现用这个实现上去比较简单;用hashmap来储存具体的对象;用skiplist拿来排序。也可以简单的用一个map和set来实现。Map内面存具体对象，set拿来排序。
关于skip list这儿简单介绍下：skip list是数组的一种特殊方式，对数组的一种优化;保证INSERT和REMOVE操作是O(logn)，而通用数组的复杂度为O(n);
优点：实现较简单，效率基本上O(log(N))
缺点：当达到亿级别时的数据时，性能会大幅增长
方案六：基于redis的 sort set的实现
后来看redis发觉redis的zset天生是拿来做排行榜的、好友列表, 去重, 历史记录等业务需求。接口使用十分简单。接口十分丰富，基本上须要的实现都能满足，说明如下：
ZAdd/ZRem是O(log(N))，ZRangeByScore/ZRemRangeByScore是O(log(N)+M)，N是Set大小，M是结果/操作元素的个数。
ZSET的实现用到了两个数据结构：hash table 和 skip list(跳跃表)，其中hash table是具体使用redis中的dict来实现的，主要是为了保证查询效率为O(1) ，而skip list(跳跃表)主要是保证元素有序并才能保证INSERT和REMOVE操作是O(logn)的复杂度。
音乐如今的通用投票排行系统就是基于redis来实现的，运行还不错。
优点：基于redis开发，速度快;使用redis相关特点
缺点：当达到亿级别时的数据时，性能会大幅增长
来实现排行榜的方式好多，可以依照自己的具体需求，参考选用。
