如何找到8个元素进行排序,并证明有没有更好的办法(没有更有效的方法)的最好方法?

可能重复:
最快的那种固定长度的6 int数组的

我们的任务是找到一种方法,与8比较(不操作)内最少数目的随机数进行排序。 我想到的是我必须使用的qsort(一半除以一个数组,排序,然后合并等..它必须是快速排序,我认为)。 对于8个元素的比较数字是17,我已经证明是没有办法进行排序与​​16(N减1)的比较乱阵。

谢谢

无论如何..所以一定是最糟糕的还...我在第一年,如果研究,所以我不认为我们必须做一些平凡的(我学习数学吧)..和种排序我用的是归并! 提前致谢

--------------解决方案-------------

归并排序/合并插入排序将需要对n = 8,这是比较的最小最坏情况数目16比较。

http://oeis.org/A001768(对归并的比较的数量)

http://oeis.org/A036604(一般比较最小数目)

又见数组排序与比较的最小数量

编辑:假设没有“随机数”的范围限制的整数。 如果你能做出的取值范围的假设,那么有替代品。

基数排序不需要比较所有:)

分类:算法 时间:2015-03-15 人气:1
本文关键词: 算法,分类
分享到:

相关文章

Copyright (C) 55228885.com, All Rights Reserved.

55228885 版权所有 京ICP备15002868号

processed in 0.468 (s). 10 q(s)