可能重复：   最快的排序固定长度的6 int数组的

的任务是找到一种方法，8随机数比较（不操作）的最少数量进行排序。我想到的是我必须使用的qsort（减半分阵列，排序，然后合并等..它必须是快速排序，我认为）。对于8种元素的比较次数是17，和我有证明有没有办法进行排序随机阵列16（N减1）的比较。

The task is to find a way to sort 8 random numbers with LEAST NUMBER OF COMPARISONS (not operations). I expect that I have to use qSort (divide an array by half, sort and then merge and so on.. it must be quicksort i think). For 8 elements number of comparisons is 17, and i have to prove that there is no way to sort random array with 16 (n minus 1) comparisons.

感谢

无论如何..所以一定是最糟糕的还..我在第一年的学习，所以我不认为我们必须做一些平凡的（我是学数学吧）..和种排序我用的是归并！在此先感谢

any case.. so must be worst also.. i'm in first year if studies so i don't think we have to do something extraordinary (i study math not it).. and kind of sort i use is mergesort! Thanks in advance

推荐答案

归并排序/合并插入排序将需要N = 8，这是比较的最低最坏的情况下16号的比较。

Mergesort/merge-insertion sort will require 16 comparisons for n=8, which is the minimum worst case number of comparisons.

http://oeis.org/A001768 （对于归并比较数字）

http://oeis.org/A001768 (number of comparisons for mergesort)

http://oeis.org/A036604 （一般比较的最小数量）

http://oeis.org/A036604 (minimum number of comparisons in general)

又见 Sorting与比较最小数量的数组

编辑：没有假设随机数的范围限制的整数。如果你可以对值​​范围的假设，那么还有其他选择。

without assuming "random numbers" are range restricted integers. If you can make assumptions about the range of values, then there are alternatives.