锦标赛排序算法
先前分享了二叉树这个数据结构,或者说应用工具,那么今天介绍的一个经典计算机算法,是跟二叉树数据结构相关联的,叫做「锦标赛排序算法」。
顾名思义,从这个算法的名字出发,它是受到体育比赛的启发想出来的。
在单淘汰的锦标赛中,选手们两两比赛,胜者晋级,败者被淘汰。比如世界乒乓球锦标赛或者大满贯网球赛就是这么进行的。这样一来,就可以把比赛的赛程和结果对应成一个二叉树。下图就是2017年美国公开赛的赛程安排,它和二叉树长得一模一样。在树中每一个选手是二叉树中的一个叶子结点,每一场比赛就相当于两个数字在比大小。数字大的选手获胜进入下一轮,也就是说比大小,大的那个选手,进入上一层,成为枝干上的根。
所以,进入到某一轮比赛的选手,其实都是某个子树干的根结点。最后的冠军自然就是整个二叉树的根结点。当然,这种赛制的合理性来自下面一个假设:如果张三赢了李四,李四赢了王五,那么张三一定能赢王五。
也就是说:A>B,B>C,那么必然是A>C,这种合理的假设不如称呼为“输赢的传递性”。只要这种胜负的传递性成立,通过这种比赛的结果得到冠军,一定是最好的选手,同时在淘汰赛过程中,每个节点大小的排序也就是固定了。
这种有单淘汰性质的体育比赛可以引入到计算机世界里去,在计算机工程中借鉴这个特性,如果要对比两个数字的大小,总不能说哪个数字最后被最大的比下去,就是第二了吧。
一般采用类似锦标赛的方式排除第一、第二、第三名,第一名永远都是最后一次产生,那么第二大的是除了比第一数字以外的更大,也就是说第二大的数字,需要从所有与最大数字比较过来被淘汰的数字中,再次比较选择才能确定。
当第二大数字确定之后,那么用类似的方法找到第三大的数字,收到锦标赛的启发,因此可以把这种算法叫做“锦标赛排序法”。
总结一下这种方法,锦标赛排序算法分为两步:第一步,把所有的数字放到二叉树的叶子结点,然后按照锦标赛单淘汰的方式,两两比较选出最大的。
第二步,对于第二大的,从所有被最大的数字淘汰的数字中选择。比如在某次比赛中,被小德淘汰的分别是纳达尔、费德勒、穆雷等人,那么这些人再进行单淘汰,选亚军。对于第三、第四大的数字,可以以此类推。
这种算法的时间复杂度为N乘以Log N,其实是和快速排序差不多,它比较适合某一类场景排序,是在特定场合下,它会比快速排序更快。
通过介绍锦标赛排序算法,我们需要学会掌握工具,善于利用工具,然后碰到特定的问题场景下去用工具来帮助我们解决问题,提高效率。特别是在一些需要用结构化排序,将无序变成有序等方面,善用信息。
最后,也是在应用工具过程中,解决不同的问题,本质还是抽象出结构,发现本质,培养和锻炼自我的抽象思维。
前一篇文章:二叉树数据结构
365 天,每天坚持写作之 144/365,爱上自己的每一天!
我在「知识星球」上开了个专栏,名字叫做“第二身份试验场”,主旨是每个人应该多在自己身上投资,不断挖掘培养自身优势,打造第二收入。同时,我会记录我每日的成长经历与感悟,希望在2019年的每一天里跟大家一起共同精进:发生、记录、感悟、反思、分享。
