最多7次相比较化解5个数的排序难点的解法

  版权申明:本文为博主窗户(Colin Cai)原创,欢迎转帖。如要转贴,必须注明原文网址

  http://www.cnblogs.com/Colin-Cai/p/7739917.html

  作者:窗户

  QQ:6679072

  E-mail:6679072@qq.com

  这一篇是上一篇《12(13)个球1个差别重量称3次称出的详细分析》的姐妹篇,解析手腕同出一辙,此题源于《算法导论》。

  和方面同样深入分析,5个数的排列总共有5!=120种,排序的实质是从那120种排列中规定里头的一种;而每回相比较会有三种结果,小于、大于等于。7次比较总共有27=128种结果,用最多128种相比结实去分辨120种排列,是有比十分的大可能率的。解答进度中充满着大量的排列组合总结以计算出各样采取所要分辨的大概性数量,总结起来大概并不自在。时刻要铭记一点,不断用消息论下界来消除也许,但音信论下界只可以用于破除,而望尘莫及完结一定。

  图片 1

图片 2

  用圈和叉代表数,八个数里面假使存在连线,代表线上边的数超越等于线下边包车型地铁数。

  每一步五个叉代表本步采用来比较的三个数。

  当5个数用一条线串在同步,当然就是排序结束。

  同一行大概有二种动静,笔者都标了出去。

相关文章