algorithm - n 个数字的排序时间是否取决于数字的排列？

Question

考虑这个问题:

A comparison-based sorting algorithm sorts an array with n items. For which fraction of n! permutations, the number of comparisons may be cn where c is a constant?

我知道对包含任意项的数组进行排序的最佳时间复杂度是 O(nlogn) 并且它不依赖于任何顺序，对吧？因此，没有导致 cn 比较的分数。如果我错了，请指导我。

Answer 1

这取决于您使用的排序算法。

Optimized Bubble Sort例如，比较数组的所有相邻元素，并在左侧元素大于右侧元素时交换它们。重复此操作，直到没有执行交换为止。

当你给冒泡排序一个排序数组时，它不会在第一次迭代中执行任何交换，因此在 O(n) 中排序。

另一方面，Heapsort将采用独立于输入顺序的 O(n log n)。

编辑:

要针对给定的排序算法回答您的问题，可能并不简单。 n中只有一个!排列已排序(为简单起见，假设没有重复项)。但是，对于 bubblesort 的示例，您可以(从排序数组开始)交换每对相邻元素。此输入将采用 Bubblesort 两次迭代，这也是 O(n)。