排序n个数字：确切需要多少个查询？

假设我有n整数。对于每个查询，我可以选择两个并进行比较。准确地说，我需要多少个查询来将它们从最小到最大排序？排序n个数字：确切需要多少个查询？

当然，答案将是O(n log n)。但我想要一个确切的答案。

让a(n)为需要查询的数字。那么很明显，a(n) >= log_2(n!)（或者说，比这更大的最小整数）。平等是否发生？这似乎是n<=5，但我一般不确定。

编辑：我想出了一种排序算法，它接近以下内容。很明显，如果您知道a_1, ..., a_i的订单，并且想要找出a_{i+1}适合的位置，则需要log_2(i+1)查询。这时你可以先进行排序a_1, a_2，然后加入a_3（将于log_2(3)查询），再加入a_4（将于log_2(4)查询），...，然后加入a_n（将于log_2(n)查询）。总共需要<= log_2(n!)+n查询。顺便说一句，有没有人知道这个排序算法的名称？

来源

2014-04-19 Solaris

什么样的，你使用？作为一个例子，请看这个链接的幻灯片50：http://pkqs.net/~tre/talks/2013_icalp_quicksort.pdf，其中概述了各种快速排序算法所需的交换和比较的总数。我绝不是理论计算机科学方面的专家，但这些幻灯片集的作者是，他们似乎甚至不能提出确切的答案。也许我正在反思这一点。 –

我对平均数不感兴趣，我对最坏的情况感兴趣。看到上面的一个排序算法，它接近我描述的下限。 – Solaris

您的编辑似乎是插入排序，它使用二进制搜索来查找a_（i + 1）的正确位置。 –

基于比较的分类有一个确定的理论结果下界，它是Omega(n lg n)。证明使用决策树非常简单。下面是一些解释的链接，但您可以通过简单搜索“分拣下界”找到关于谷歌更多的理论工作：

http://en.wikipedia.org/wiki/Comparison_sort#Lower_bound_for_the_average_number_of_comparisons

来源

2014-04-19 04:31:08 noobProgrammer

谢谢。我并没有要求一个渐近的答案;就像我在问题中提到的那样，我意识到'欧米茄（欧米茄）'的束缚。该链接讨论了这个问题（请参阅http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list）。显然答案是未知的，并且对于n = 13，下限log_2（n！）不是尖锐的。 – Solaris

排序n个数字：确切需要多少个查询？

回答

相关问题