计算机经典算法——锦标赛排序算法

关键词:二叉树
生活中的淘汰锦标赛:在单淘汰的锦标赛中,选手们两两比赛,胜者晋级,败者被淘汰。比如世界乒乓球锦标赛或者大满贯网球赛就是这么进行的。
这样一来,就可以把比赛的赛程和结果对应成一个二叉树。在树中每一个选手是二叉树中的一个叶子结点,每一场比赛就相当于两个数字在比大小,数字大的选手获胜进入下一轮,成为树干上的根。所以,进入到某一轮比赛的选手,其实都是某个子数干的根结点。最后的冠军就是整个二叉树的根结点。这种赛制的合理性需要一个假设:A>B, B>C --> 必然有A>C(输赢的传递性)


锦标赛排序法:对所有数字排序,复杂度是nlogn(和快速排序差不多)。特定的场合,它更快,如果只选第一名,则算法复杂度只有N,若需要选出第二名,则额外增加logn就可以了,对第三名也是如此。这种方法在从N个选手中选出K个选手的事情中特别快

工程中,要比较两个数字的大小
第一步:把所有的数字放到二叉树的叶子节点,然后按照锦标赛单淘汰的方式,两两比较选出最大
第二步:对于第二大的,从所有被最大的数字淘汰的数字中选择,以此类推选择对于第三、第四大的数字

高盛面试题

假定有25名短跑选手比赛竞争金银铜牌,赛场上有5条赛道,因此一次可以有5个人同时比赛。比赛不及时,只看相应的名次。假如选手的发挥是稳定的,也就是说如果约翰比张三跑的快,张三比凯利跑的快,那么约翰一定比凯利跑得快。最少需要几组比赛才能决出前3名?

第一步,将25名选手分成5组,每组5人。让每个组分别比赛,排出各组的名次来,假设他们的名字就是他们在小组中的编号。



第二步,让各组的第一名,也就是A1、B1、C1、D1、E1再比一次。假设A1在这次比赛中获胜,这样我们就知道了第一名。



第三步,A2和另外四个组的第一名竞争亚军,A2、B1、C1、D1、E1比一次,假设A2这一次赢了,他就是亚军。如果A2没有赢,另外4个组的某个第一名赢了,那个赢的人是亚军,就由那个组下一位选手递进,角逐第三名


第四步,如上图通过8次(5 +1 + 1 +1)选出的5人进行第三名的比赛,前3全部产生

更好的答案:
前6次比赛都是必须的,最佳答案的前2步和上述方案中的前2步是相同的。在第6组比赛(即5个第一名的比赛)结束之后,最后的2名已经没有资格角逐前3名了。

不妨假设那一次比赛从最快到最慢的结果是A1、B1、C1、D1、E1,在D1和E1之前已经有3名选手了,他们肯定不是前3名。
谁还会是第二名的候选呢?根据锦标赛排序的原则,直接输给第一名的人,也就是A2,以及最后附加赛输给他的B1,仅此两人而已。
谁会是第三名的候选呢?和A1在某一组比赛的第三名,他们是A3、C1,或者输给第二名候选人B1的人,即B2。

因此,第二、第三名的候选人一共只有5个, A2、A3、B1、B2和C1,刚好凑一组。这样加上前6次,只需要赛7组,这是最佳方法。


注:来自吴军老师得到课程

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 第一步:把所有的数字放到二叉树的叶子结点,然后按照锦标赛单淘汰的方式,两两比较选出最大的。第二步:对于第二大的,从...
    天雨流芳zhang阅读 1,363评论 0 0
  • 朋友们晚上好!先祝大家中秋节快乐。我社即将迎来大家期盼已久的炉石传说锦标赛,话不多说,让我们来看看这次比赛的规则吧...
    靳天阳阅读 303评论 0 0
  • 经历了复习及考试周后,我应该度过了最后一个自由而舒适的星期,怀揣着激动的心情,兴致高昂的来到学校。 在向蚊子贡献了...
    弓炜杰_三月阅读 1,068评论 18 9
  • 不管有没有爱过或被爱过,爱,对于我们来说都是一种发至内心的本能,不用刻意去模仿,也不用刻意去学习,一切...
    筱念凉阅读 1,058评论 8 3
  • 有一句话,叫你想珍惜时,ta已离去。经历到,才知道什么时是爱的真谛,感情已经放手,就像泼处去的水,那样不可收拾。...
    砂碩阅读 260评论 4 4