诸葛亮vs司马懿,排序算法大战谁能笑到最后?
阵前对峙
公元234年,蜀汉丞相诸葛孔明再次北伐。
一日,与司马仲达所率魏军两军相峙,二人阵前舌战。
司马曰:“诸葛村夫,吾与汝相斗数年,斗兵斗阵斗谋略,均已疲乏。今日,何不一改陈规,斗点新奇玩意?”
诸葛轻抚羽扇,言道:“仲达今日想比试些什么?”
“你我各遣相等数量兵士,立作一排,再互派一人至对方军前,看谁派遣之人先将这一排兵士按身高从低到高排序,谁就取胜,三局两胜制,输者撤军五十里,如何?”
诸葛不答,只是一边微笑,一边慢摇羽扇。
司马问道:“怎么?怕了?”
诸葛笑曰:“为将者,不通天文,不识地理,不知奇门,不晓阴阳,不明兵势, 不学算法,庸才耳。此乃小儿游戏,何怕之有?”
司马亦笑曰:“匹夫休要狂言,且比来一看。”
第一轮:插入 VS 选择
双方各自部署,第一轮,双方皆出十人,少倾,列队完毕。
蜀营王平:“丞相,末将请求出战,以插入排序法
破之”
魏营孙礼:“大都督,末将愿往,以选择排序法
取之”
待信令一出,王平孙礼皆开始重整队伍。
司马观王平策略,只见王平来到队伍起始,依次唤后一人出列,空出其位,随后将其与前面之人相比,若矮于前面之人,则继续向前,直到寻出比之更矮之人,则将出列之人置于其后,原来位置之人依次后移。多次重复后,队伍已逐渐呈自低向高之势排列。
而另一侧,魏将孙礼之法,却有不同。只见其从第一人开始,记录为最矮之人,随后从第二人开始,将其身高与最矮之人身高相比,一旦发现比最矮之人还小,则更新最矮之人编号为当前之人,一趟下来直至队伍末尾,便知晓谁是整个队伍最矮之人,将其与队伍第一位置交换,最矮之人便来到队伍最前面。接着从第二位置重复以上过程,逐步获取次矮之人,不多时,队伍亦逐渐呈自低向高之势排列。
两人几乎同时完成整个队伍的排序,然蜀将王平以微小优势领先完成,此一轮,蜀胜。
第二轮:冒泡 VS 希尔
第二轮,双方皆出百人,少倾,列队完毕。
蜀营魏延请命:“丞相,末将请求出战,以快速排序法
定能取胜”
诸葛曰:“杀鸡焉用牛刀,区区百人之队,冒泡排序法
足矣,此一轮还是让马岱出战吧”
魏延面露不悦。
蜀营派马岱出战,魏营遣郭淮出战。
待信令一出,二人皆开始调整队伍。
马岱来到队首,只见其从第一人开始,比较第一人与第二人之高矮,若第一人高于第二人,则交换两人站位。继续比较第二人与第三人,一趟结束,最末尾之人便为队伍中最高之人。接着来到队伍开头,故技重施,不断交换,一直将队伍中次高之人交换到倒数第二的位置。
司马观之,叹曰:“诸葛亮徒有虚名,竟派马岱使用冒泡排序法
,大量交换费时费力,我军稳操胜券了”
此刻,魏延大急:“丞相,那郭淮使的什么方法,像插入法又不像插入法,眼看就要完成了,丞相真该派我出战”
诸葛不语,一旁王平言道:“上将军,依末将愚见,此貌似缩小增量排序法,又名希尔排序法
,由插入排序法改进而来,早年由西域传入中原”。
片刻之后,郭淮率先完成队伍排列,此一轮,魏胜。
第三轮:归并 VS ??
第三轮,双方队列增至千人。
蜀营魏延再次请求出战。
诸葛问魏延:“文长(魏延,字文长)啊,你打算以何算法破之?”
魏延答:“丞相,末将方才已经告知,予以快速排序法
破之”
诸葛摇头,“不可”
魏延不解,“有何不可?”
诸葛复曰:“我观司马懿此一轮必遣其子司马昭出战,司马昭此人我素有耳闻,同样擅使快速排序法
,若你二人均以此法上阵,你可有把握胜之?”
魏延摇头:“倘若如此,末将并无十足把握”
诸葛轻挥羽扇,“此一局不宜使用快速排序法
,姜维过来,本相另有良策传授与你”
魏延愤懑不平:“丞相为何视我为无物,末将不服”。
诸葛笑曰:“文长休急,本相另有重任相托”。
魏延大喜。
另一方魏营,司马昭曰:“父亲,孩儿研习快速排序法
多年,此一轮愿请出战”
仲达怒斥:“军中无父子!”
昭大惊,改口:“是,大都督”
仲达缓捋长须,曰:“此一轮,不可用快速排序法
”
昭不明:“这是为何?”
“快速排序法
之要害,在于选择基准参考,并将队伍划分为矮于基准之人部分和高于基准之人部分。再缩小范围,复用此法,直至整个队伍有序。”
昭曰:“父亲,,,大都督所言不错,可为何不能使用此法?”
仲达指着队伍,言道:“诸将请看,千人之队,必有大量身高相等之人,若以快速排序法
,势必做大量无用位置交换,徒耗不少功夫。快速排序法
名曰快速,切不可纸上谈兵,还需审时度势,灵活变通才是”
司马昭点头,深以为然:“还是大都督老谋深算,末将虽研习多年,尤未可及也”
仲达于司马昭耳畔窃言数语,随即遣之出战。
司马昭来到队伍前面,将队伍分作两半,又将每一半继续分作两半,直至无可再分。接着按照大小合并每一个细分的部分为有序队伍,又进一步将这些有序队伍合并成更大的有序队伍,直至合并所有兵士为整体的有序队伍。
司马问道:“孔明,你可识得我儿司马昭所用排序之法?”
诸葛笑答:“别说是我,我蜀中三尺孩童也识得,此乃归并排序法
,是也不是?”
司马未露声色,回看姜维,一不留神,姜维所排队伍竟已近尾声。
诸葛察之,问道:“仲达可识得姜维所用排序之法?”
司马细细观之,只见姜维从队首至队尾,依次询问所有人身高,并记录整个队伍之最矮与最高者,最终得最矮者六尺二寸,最高者八尺三寸。随即从六尺二寸、六尺三寸、六尺四寸,直至八尺二寸、八尺三寸共划分为二十二组。随后将所有人依次分入各组,再将各组依序合并。 千人之队,不待半个时辰,竟将完成。
片刻之后,姜维完成队列排序,此一轮,蜀胜。
司马仍未露声色,悄然返回军中,谓之左右曰:“诸葛亮果然有些本事,我不如也”
三局两胜,司马失利,依约后撤五十里,高挂免战牌,自此坚守不出。
彩蛋
撤军路上,昭问仲达:“大都督,蜀将姜维所用何法,竟能如此神速?”
不待仲达开口,前方一哨骑回报:“报~,大都督,蜀将魏延趁两军对峙,亲率两万铁骑攻我大营,我守将不备,大营给,给丢了”
司马怒目圆睁,摔下马去。
文中动图来源
《十大经典排序算法(动图演示)》:https://www.cnblogs.com/onepixel/articles/7674659.html
作者:一像素