原文：

1.与数组相关的算法：

快速排序（分治思想的应用）：不是任何情况都适用，数据量小的话，还不如冒泡快，但快排的确很优秀。

堆排序：可用于做游戏排行榜前多少多少名，根据求最大的K个数还是最小的K个数来建最大堆和最小堆，再将最大/小堆的根节点和最后一个子叶节点交换，最后调整堆，重复刚才那两个步骤，直到得到K个数。当然，这种题也可以用红黑树实现的set来做。

二分查找：用于查找出分数为多少多少的玩家

2.与树有关的算法

四叉树、八叉树可用来检测大量物体之间的碰撞总次数。

3.与图有关的算法

1.小型游戏可以用的简单的寻路算法：

随机寻路算法：当NPC不管是遇到障碍物还是遇到了边界（利用碰撞检测），都会随机选取一个前进的方向，继续行走

跟踪算法：当游戏中的主角进入到NPC的“警戒区域”后，游戏的AI可轻易获得目标的位置，然后控制NPC对象移向被跟踪的对象

闪避算法：和跟踪算法完全相反，也就是当游戏中的主角进入到NPC的“警戒区域”后，主角可以去追着NPC跑

2.大型游戏一般使用A寻路算法：使用最广泛的一种寻路算法，简单说一下A寻路算法：

公式：f(n)=g(n)+h(n)，g(n)表示从起点到任意点n的实际直线距离，h(n)表示任意顶点n到目标点的估算距离（常用曼哈顿距离公式用于估算h(n)：|x1- x2|+|y1- y2|）

把待处理的方格A存入一个”开启列表”，开启列表就是一个等待检查方格的列表；”关闭列表”中存放的都是不需要再次检查的方格。

每次从OPEN列表中选择 f(n)最小的节点将其加入CLOESE列表中，同时扩展相邻节点并将它们加入OPEN列表，可把OPEN列表看成一个优先队列，key值为 f(n)，优先级最高的先出。

最后直到把终点加入OPEN列表中，计算出指针指向就完事了。所以最后的路径就是，从终点开始沿着父指针不断往起点走，最后回到起始点，这样最短路径就找到了：

二、一个TOPN排行榜问题的算法

问题描述：在游戏等场景中，实时维护分数排行榜并返回TOPN列表成为关键需求。实现此功能时，选择合适的数据结构至关重要。

通常，使用SQL查询或者Redis的Zset可快速获取数据。然而，对于本地内存实现，采用链表与字典组合，可实现快速响应。链表负责维护用户分数排名，字典用于快速查找uid对应位置。取TOPN操作简单，仅需从链表头部取N个元素。更新数据时，可采用冒泡排序，平均时间复杂度为O(K)。

面对本地内存解决方案，考虑使用优先队列（堆）优化效率。通过两个堆结构，一个维护TOPN名单（小顶堆），一个存放其余名单（大顶堆）。需确保小顶堆元素数不超过TOPN，且小顶堆元素大于大顶堆任意元素。堆内元素附带时间戳用于版本控制，确保数据更新的准确性。

数据更新时，比较插入元素与小顶堆堆顶元素大小，决定放入小顶堆或大顶堆。为维护堆结构，可能需进行堆的调整。此过程通过延迟删除技术实现，允许元素id重复，并通过字典记录最新版本。push操作更新字典，top时检查元素版本，确保返回最新数据。

小优化包括：仅在小顶堆内容未更新时，复用之前生成的TOPN列表，节省计算资源。当延迟的元素占用内存过大时，可手动清理失效元素。

时间复杂度方面，取TOPN操作复杂度为O(nlogn)，即排序TOPN的时间复杂度。更新数据的复杂度为O(logM)，其中M为元素总数。此算法适用于快速维护和生成分数排行榜的TOPN名单，克服了链表算法在处理较大排名变动时效率低下的问题。

然而，该方法无法快速查找特定uid的排名或给定排名对应的uid。在实际应用中，可根据需求权衡效率与功能。

附上代码示例，此代码在GCC9.3环境下通过验证。

三、梦幻西游手游里的排行榜综合实力是怎么计算的

综合实力计算方法：人物的评分+宠物的评分(宠物评分取最高的那只）

人物评分计算标准：

1、装备评分：每件装备都会有评分显示，目前一共有6件装备。

2、宝石评分：1级宝石增加12点评分，60之后可携带12个宝石。

3、修练评分：1级修炼增加15点评分，人物有4个修炼。

4、技能评分：1级技能增加1点评分，一共有8个技能。

5、强身冥想评分：1级增加1点评分

6、等级评分：每次提升等级增加66分。

宠物评分与宠物技能个数、技能类型、宠物资质、宠物成长有关，越值钱的魔决加的评分越多，成长、资质、技能个数也占据一定评分比例，具体算法没有详细公布）

综合实力查看：在游戏界面的右下角的排行榜可以查看人物的综合实力。

小提示：在排行榜下方可以看到自己的排名，综合实力最高的玩家将会获得三界第一高手的称号。

扩展资料：

人物评分误区

造成一个玩家高评分低实力，或者高实力低评分的最大因素，恐怕就是“修炼”和“装备”了。出于省钱的考量，宠物抗封修炼是暂时不用去学习的，但是宠物抗封修炼每提升一级，人物评分就会提升12点。也就是说，当你修到20级的时候，你就会比不修的玩家多240点评分。虽然在实战中这一修炼价值不大，但是这却是想要凑高排名的玩家必修项目。

除此之外，玩家的装备质量同样影响了评分，而其中影响最大的就是“是否携带特技特效”。不少装备虽然有额外属性加成，但是依旧没有上珍品线，但是有特技特效的装备则必定能上，所以有时候觉得一个人高评分，但是输出不够防御也不行，可能就是他携带了太多的特技装备牺牲了自己的属性。

宠物评分误区

影响宠物评分的最大原因，就是宠物的技能格。两个宠物也许种类相同，某一个宠物的资质、成长都优于另外一个宠物，但是后者却能够比它评分高上200~300甚至更高。这其中的原因就是它比前者多了技能格，或者被打上了高级兽诀。不管这些技能是否和宠物自身资质搭配，只要是高级技能，就能大大提升宠物的评分。

所以利用这一点，可以把一些垃圾宠物打上高级技能书挂到摆摊中去卖掉。当然这其中也有例外，比如说鬼将，由于它是稀有宠物，所以即便达不到同携带等级中其他宠物的珍品线，它也能挂到摆摊上去。