锦标赛算法

思路: K阶锦标赛算法
例如:一个赛马场有100匹马,5条赛道,至少要比赛多少场才能选出跑得最快的10匹马?
步骤:
1. 将100匹马分成20次比赛,每次5匹马,并保存每次比赛的结果(即第1名到第5名的顺序)
2. 从胜利的20匹马分成4次比赛,每次5匹马,并保存每次比赛的结果(即第1名到第5名的顺序)
3. 对最后的4匹马进行比赛,并保存每次比赛的结果(即第1名到第4名的顺序)
即通过以上3个步骤,其实已经建立一个4层的树结构。并且已经得到第1名A
4. 在4层树结构中,挑出与A比过赛的且失败的,且是第2名的马(不超过5位),挑选出第2名B
在此过程中,可以想象将A删除,并在比较过程中恢复树结构
依次轮推,直至找出前10名
总的比较次数为:
选出第一名:20+4+1
选出第二名:1
选出第三名:1
...
选出第十名:1
总次数:34次

原文地址:https://www.cnblogs.com/allenzhaox/p/3201807.html