查看原文
其他

诸葛亮 vs 司马懿,排序算法大战谁能笑到最后?

The following article is from 编程技术宇宙 Author 轩辕之风O

(给算法爱好者加星标,修炼编程内功

来源:编程技术宇宙/轩辕之风 (本文来自作者投稿)

阵前对峙

公元234年,蜀汉丞相诸葛孔明再度北伐。

一日,与司马仲达所率魏军两军相峙,二人阵前舌战。

司马曰:“诸葛村夫,吾与汝相斗数年,斗兵斗阵斗谋略,均已疲乏。今日,何不一改陈规,斗点新奇玩意?”

诸葛轻抚羽扇,言道:“仲达今日想比试些什么?”

“你我各遣相等数量兵士,立作一排,再互派一人至对方军前,看谁派遣之人先将这一排兵士按身高从低到高排序,谁就取胜,三局两胜制,输者撤军五十里,如何?”

诸葛不答,只是一边微笑,一边慢摇羽扇。

司马问道:“怎么?怕了?”

诸葛笑曰:“为将者,不通天文,不识地理,不知奇门,不晓阴阳,不明兵势, 不学算法,庸才耳。此乃小儿游戏,何怕之有?”

司马亦笑曰:“匹夫休要狂言,且比来一看。”

第一轮:插入 VS 选择

双方各自部署,第一轮,双方皆出十人,少倾,列队完毕。

蜀营王平:“丞相,末将请求出战,以插入排序法破之”

魏营孙礼:“大都督,末将愿往,以选择排序法取之”

待信令一出,王平孙礼皆开始重整队伍。

司马观王平策略,只见王平来到队伍起始,依次唤后一人出列,空出其位,随后将其与前面之人相比,若矮于前面之人,则继续向前,直到寻出比之更矮之人,则将出列之人置于其后,原来位置之人依次后移。多次重复后,队伍已逐渐呈自低向高之势排列

而另一侧,魏将孙礼之法,却有不同。只见其从第一人开始,记录为最矮之人,随后从第二人开始,将其身高与最矮之人身高相比,一旦发现比最矮之人还小,则更新最矮之人编号为当前之人,一趟下来直至队伍末尾,便知晓谁是整个队伍最矮之人,将其与队伍第一位置交换,最矮之人便来到队伍最前面。接着从第二位置重复以上过程,逐步获取次矮之人,不多时,队伍亦逐渐呈自低向高之势排列

两人几乎同时完成整个队伍的排序,然蜀将王平以微小优势领先完成,此一轮,蜀胜。

第二轮:冒泡 VS 希尔

第二轮,双方皆出百人,少倾,列队完毕。

蜀营魏延请命:“丞相,末将请求出战,以快速排序法定能取胜”

诸葛曰:“杀鸡焉用牛刀,区区百人之队,冒泡排序法足矣,此一轮还是让马岱出战吧”

魏延面露不悦。

蜀营派马岱出战,魏营遣郭淮出战。

待信令一出,二人皆开始调整队伍。

马岱来到队首,只见其从第一人开始,比较第一人与第二人之高矮,若第一人高于第二人,则交换两人站位。继续比较第二人与第三人,一趟结束,最末尾之人便为队伍中最高之人。接着来到队伍开头,故技重施,不断交换,一直将队伍中次高之人交换到倒数第二的位置。

司马观之,叹曰:“诸葛亮徒有虚名,竟派马岱使用冒泡排序法,大量交换费时费力,我军稳操胜券了”

此刻,魏延大急:“丞相,那郭淮使的什么方法,像插入法又不像插入法,眼看就要完成了,丞相真该派我出战”

诸葛不语,一旁王平言道:“上将军,依末将愚见,此貌似缩小增量排序法,又名希尔排序法,由插入排序法改进而来,早年由西域传入中原”。

片刻之后,郭淮率先完成队伍排列,此一轮,魏胜。

第三轮:归并 VS ??

第三轮,双方队列增至千人。

蜀营魏延再次请求出战。

诸葛问魏延:“文长(魏延,字文长)啊,你打算以何算法破之?”

魏延答:“丞相,末将方才已经告知,予以快速排序法破之”

诸葛摇头,“不可”

魏延不解,“有何不可?”

诸葛复曰:“我观司马懿此一轮必遣其子司马昭出战,司马昭此人我素有耳闻,同样擅使快速排序法,若你二人均以此法上阵,你可有把握胜之?”

魏延摇头:“倘若如此,末将并无十足把握”

诸葛轻挥羽扇,“此一局不宜使用快速排序法,姜维过来,本相另有良策传授与你”

魏延愤懑不平:“丞相为何视我为无物,末将不服”。

诸葛笑曰:“文长休急,本相另有重任相托”。

魏延大喜。

另一方魏营,司马昭曰:“父亲,孩儿研习快速排序法多年,此一轮愿请出战”

仲达怒斥:“军中无父子!”

昭大惊,改口:“是,大都督”

仲达缓捋长须,曰:“此一轮,不可用快速排序法

昭不明:“这是为何?”

快速排序法之要害,在于选择基准参考,并将队伍划分为矮于基准之人部分和高于基准之人部分。再缩小范围,复用此法,直至整个队伍有序。

昭曰:“父亲,,,大都督所言不错,可为何不能使用此法?”

仲达指着队伍,言道:“诸将请看,千人之队,必有大量身高相等之人,若以快速排序法,势必做大量无用位置交换,徒耗不少功夫。快速排序法名曰快速,切不可纸上谈兵,还需审时度势,灵活变通才是”

司马昭点头,深以为然:“还是大都督老谋深算,末将虽研习多年,尤未可及也”

仲达于司马昭耳畔窃言数语,随即遣之出战。


司马昭来到队伍前面,将队伍分作两半,又将每一半继续分作两半,直至无可再分。接着按照大小合并每一个细分的部分为有序队伍,又进一步将这些有序队伍合并成更大的有序队伍,直至合并所有兵士为整体的有序队伍

司马问道:“孔明,你可识得我儿司马昭所用排序之法?”

诸葛笑答:“别说是我,我蜀中三尺孩童也识得,此乃归并排序法,是也不是?”

司马未露声色,回看姜维,一不留神,姜维所排队伍竟已近尾声。

诸葛察之,问道:“仲达可识得姜维所用排序之法?”

司马细细观之,只见姜维从队首至队尾,依次询问所有人身高,并记录整个队伍之最矮与最高者,最终得最矮者六尺二寸,最高者八尺三寸。随即从六尺二寸、六尺三寸、六尺四寸,直至八尺二寸、八尺三寸共划分为二十二组。随后将所有人依次分入各组,再将各组依序合并。千人之队,不待半个时辰,竟将完成。

片刻之后,姜维完成队列排序,此一轮,蜀胜。

司马仍未露声色,悄然返回军中,谓之左右曰:“诸葛亮果然有些本事,我不如也”

三局两胜,司马失利,依约后撤五十里,高挂免战牌,自此坚守不出。

彩蛋

撤军路上,昭问仲达:“大都督,蜀将姜维所用何法,竟能如此神速?”

不待仲达开口,前方一哨骑回报:“报~,大都督,蜀将魏延趁两军对峙,亲率两万铁骑攻我大营,我守将不备,大营给,给丢了”

司马怒目圆睁,摔下马去。

- EOF -

推荐阅读  点击标题可跳转

1、面试官爱问的 10 大经典排序算法,20+ 张图来搞定

2、图解排序算法:归并排序

3、排序算法:Heap Sort 堆排序与 Top K 问题


觉得本文有帮助?请分享给更多人

关注「算法爱好者」加星标,修炼编程内功

点赞和在看就是最大的支持❤️

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存