admin管理员组

文章数量:1516870

5个元素排序

一到作业题，原题是：

给定5个元素，给出一种算法确定这5个元的排序，最坏比较次数为7，并证明以比较为基础的算法中7次是最优的。


证明：考虑算法对应的二叉树，5个元素一共有5!=120种排列，能区分这些排列对应的二叉树最小层数为7（2^7=128），故7次是最优的。

算法：想了会没想出来，详见.

设他们是abcde,不妨设a<b,c<d,比较bd,不妨设b<d,则有a<b<d,c<d,用二分插入将e插入到abd中，需要2次比较，分为两种情况：1是e<d,则用二分插入将c插入到abe中；2是e>d,则用二分插入将c插入到ab中。总共7次。


看了这个解答恍然大悟——妙哉妙哉！此方法出自于“ H.B.Demuth 于 1956 的博士论文”。不愧为博士，就是牛。

仔细思考了一下，之前一直想的是比较bc，用5次确定4个数的序，然后插入e，共8次。

╮(╯▽╰)╭

看来博士还有很长的路要走。

本文标签： 5个元素排序

版权声明：本文标题：5个元素排序 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.betaflare.com/biancheng/1708506112a748506.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。