达内Android培训技术专家认为：以前在音乐做过一些实时投票，积分排名；单曲、专辑等排行榜；游戏中也有类似的战斗力排行；SNS的游戏又有好友排行等，对于此类的排行算法在此做个总结。
算法简单，利用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)。
以后，每次用户积分有变化所需要更新的区间数量和积分变化量有关系，积分变化越小更新的区间层次越低。总体上，每次所需要更新的区间数量是用户积分变量的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)，整个累加过程完成，得出排名！
达内Android培训技术专家表示：虽然，本算法的更新和查询都涉及到若干个操作，但如果我们为区间的from_score和to_score建立索引，这些操作都是基于键的查询和更新，不会产生表扫描，因此效率更高。另外，本算法并不依赖于关系数据模型和SQL运算，可以轻易地为NoSQL等其他存储方式，而基于键的操作也很容易引入缓存机制进一步优化性能。进一步，我们可以估算一下树形区间的数目大约为2,000,000，考虑每个结点的大小，整个结构只占用几十M空间。所以，我们完全可以在内存建立区间树结构，并通过user_score表在O(n)的时间内初始化区间树，然后排名的查询和更新操作都可以在内存进行。一般来讲，同样的算法，从数据库到内存算法的性能提升常常可以达到10^5以上；因此，本算法可以达到非常高的性能。
优点：结构稳定，不受积分分布影响；每次查询或更新的复杂度为积分最大值的O(log(n))级别，且与用户规模无关，可以应对海量规模；不依赖于SQL，容易为NoSQL或内存数据结构。
达内Android培训技术专家认为：实现方案四的时候，发现代码比较复杂，调试起来特别不方便。游戏这边有个同事也实现了个，代码地址：
于是就想到的跳表，发现用这个实现起来比较简单；用hashmap来存储具体的对象；用skiplist用来排序。也可以简单的用一个map和set来实现。Map内面存具体对象，set用来排序。
关于skip list这里简单介绍下：skip list是链表的一种特殊形式，对链表的一种优化；INSERT和REMOVE操作是O(logn)，而通用链表的复杂度为O(n);
后来看redis发现redis的zset天生是用来做排行榜的、好友列表,去重,历史记录等业务需求。接口使用非常简单。接口非常丰富，基本上需要的实现都能满足，说明如下：
达内Android培训技术专家认为：来实现排行榜的方法很多，可以根据自己的具体需求，参考选用。
本文由325游戏 （www.325qp.net）整理发布