algorithm - 在 O(n*log(n)) 最坏情况下排序

Question

是否有一种数组可以在 O(n*log(n)) 最坏情况时间复杂度下工作？

我在维基百科上看到有类似的东西，但是它们不稳定，这是什么意思？有没有办法在低空间复杂度下做？

是否有最佳排序算法？

Answer 1

只需要 O(1) 额外内存(因此允许修改输入数组)的算法通常被描述为“就地”，这是最低的空间复杂度。

一种排序被描述为“稳定”与否，取决于当输入中有两个元素比较相等时发生的情况，但在某种程度上是可区分的。例如，假设您有一堆包含一个整数字段和一个字符串字段的记录，并且您在整数字段上对它们进行排序。问题是，如果两个记录具有相同的整数值但不同的字符串值，那么在输入中排在第一位的记录是否也会在输出中排在第一位，或者它们是否有可能颠倒过来？稳定排序是一种保证保留比较相同但不相同的元素顺序的排序。

很难进行就地比较排序，和稳定，和最差O(n log n) -案例时间复杂度。我有一个模糊的想法，不知道它是否可能，但我没有跟上它的最新进展。

上次有人问这个问题，我找到了几篇相关论文，尽管那个问题与这个问题不一样:

How to sort in-place using the merge sort algorithm?

就“最佳”排序而言 - 一些排序策略利用了这样一个事实，即总体而言，在大量应用程序中，计算机会花费大量时间对未随机打乱的数据进行排序，它有一些结构。 Timsort是一种利用常见结构的算法。它在很多实际应用中表现非常出色。您不能将其描述为“最佳”排序，因为它是一种在实践中似乎表现良好的启发式算法，而不是对先前算法的严格改进。但在将其作为默认类别(Python、Java 7、Android)发布的人们看来，它是总体上“最好的”。您可能不会将其描述为“低空间复杂度”，但它并不比标准归并排序好。