桶排序在排行榜问题中的应用

基本思路

1. 将集合的值的范围分割成n个桶，极端情况下一个值一个桶；
2. 遍历集合，每个值入桶；
3. 桶内用其他方式如快速排序排序。

适用场景

集合总体取值范围较小的场景

应用

在总排名这种场景中经常使用，一个例子：

针对陌陌争霸我们是这样做的：

陌陌争霸中用于排名的分数区间不大，也就是 0 分到 5000 分。而参与排名的人数众多，数以百万计。对百万用户做插入排序，每个插入即使是 O(N) 的也不可接受。可事实是大量玩家的分数相同，都是并列排名的。所以我们只需要做 5000 个桶，每个桶里仅记录这个分数有多少个人就可以了。

当玩家分数变迁，把原来的桶减一，新的桶加一。这个操作就是 O(1) 的。

而排行榜的查询仅需要把当前分数靠前的桶累加，就能获知查询者的名次。对于上百万玩家，看到哪些人和你并列的人的名字是没有意义的。这个查询虽然是 O(n) 复杂度，但 n 只有区区 5000 ，还可以做 cache 以应对查询频率远高于更新频率的情况。

真正需要精确知道人名的是榜单的前 200 个人，而对前 200 个人做插入排序也很快，所以并不会造成性能问题。

我们在系统的单点做排行榜的维持，完全没有外部数据库操作，它只是一小段操作普通内存结构的 c 代码。而这个单点远远成为不了整个系统的热点。

我们在系统临时退出时，把已经排好的榜单落地，下次启动的时候恢复。但也不必完全信任落地的数据，可以用离线脚本检索整个数据库重新生成一份正确的榜单。所以数据库中的榜单只是被 cache 起来而已，系统运行期间是不需要写入数据库的，也不用担心数据丢失。

一个分值一个桶，给一个玩家计算排名时，统计他所在桶之前所有桶的玩家数即可。这不是一个精确的值，因为同分的没有计算在内。

同样的思路也可以用在 在线时长排名 等类似场景，只要：

1. 集合取值范围不大；
2. 不要求精确，因为不计入得分并列的人数