比较排序算法的复杂度对比

Question

为什么基于比较的排序算法时间复杂度的下限是O(n log n)？

- JC.

Answer 1

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

我认为这很好地回答了那个问题。

- meriton

Answer 2

简而言之，因为您必须查看每个元素，这是O(n)。对于您查看的每个元素，您必须找出它是否按正确顺序排列，这最多需要O(log n)（例如二分查找）。因此，总和变为O(n log n)。

- Brad