排序在最坏情况下O（n * log（n））

Question

是否有一种工作在O（n * log（n））最坏情况时间复杂度的数组？

我在维基百科看到有类似的，但它们是unstable，这是什么意思？有没有办法在低空间复杂性？

是否有最佳排序算法？

Answer 1

只需要O（1）额外内存（因此允许修改输入数组）的算法通常被描述为“in-place”，并且这是最低的空间复杂度。

根据当输入中有两个元素时，将排序描述为“稳定”或不是，其中比较等同，但在某种程度上是可区分的。例如，假设您有一堆带有整数字段和字符串字段的记录，并将它们排序在整数字段上。问题是，如果两个记录具有相同的整数值但字符串值不同，那么输入中第一个记录的输出中的第一个也会先出现在输出中，还是有可能会颠倒？稳定的排序是保证比较相同但不相同的元素顺序的排序。

这是很难做出比较排序是就地，和稳定，和达到O(n log n)最坏情况下的时间复杂度。我有一个模糊的想法，不知道它是否可能，但我没有及时更新它。

上次有人问这个话题，我发现一对夫妇的相关论文，但这个问题并不等同于这样一个问题：

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

至于“最佳”之类的关注 - 一些排序策略利用了这样一个事实，即总体来说，通过大量的应用程序，计算机花费大量的时间对未被随机洗牌的数据进行排序，它具有一定的结构。 Timsort是一种利用通常遇到的结构的算法。它在很多实际应用中表现非常好。你不能把它描述成“最好”的类型，因为它是一种似乎在实践中表现良好的启发式方法，而不是对先前算法的严格改进。但是，将它作为默认排序的人（Python，Java 7，Android）认为它是“最好的”。您可能不会将其描述为“低空间复杂度”，但它并不比标准的合并排序更好。

Answer 2

你可以检查mergesort，quicksort或heapsort之间的所有很好描述here。

还有基数排序，其复杂度是O（kN），但它充分利用了额外的内存消耗。

您还可以see，对于较小的集快速排序是速度较快，但随后归并牵头，但所有的这情况下专用的，所以把你的时间来研究所有4种算法

Answer 3

对于这个问题最好算法中，简单的答案是，这取决于。它取决于设置要进行排序，这取决于你的requirement.Say的数据的大小，冒泡排序有最坏情况和平均复杂度都О（N ） ，其中n是正在排序的项目的数量。存在许多排序算法，具有明显更好的O（n log n）的最坏情况或平均复杂度。甚至其他的排序算法（例如插入排序）的其他排序算法倾向于具有比气泡排序更好的性能。因此，当n很大时，冒泡排序不是一种实用的排序算法。

在简单平均情况Θ（N ）算法，选择排序几乎总是优于冒泡排序，但一般是由插入排序胜过。

选择排序大大上较大的阵列由Θ优于作为归并例如（N log n）的分而治之算法。但是，插入排序或选择排序对于小型阵列通常都更快。

同样，您可以根据自己的要求自己选择最佳排序算法。

Answer 4

已证实O（n log n）是排序通用项目的下界。也证明了O（n）是排序整数的下界（至少需要读取输入:)）。

问题的具体实例将决定什么是最适合您需求的算法，即。排序1M字符串与在2MB RAM中排序2M 7位整数不同。

另外考虑到除了渐近的运行时复杂性之外，实现还有很多不同，以及可用内存和缓存策略的数量。我可以在python的1行中实现快速排序，大致保持O（n log n）的复杂性（对于关键点有一些警告），但是Big-Oh表示法并没有提到与常量项相关的内容，这也是相关的。这是30倍〜比Python慢​​内置的排序，这很可能是用C语言编写的BTW）：

qsort = lambda a: [] if not a else qsort(filter(lambda x: x<a[len(a)/2], a)) + filter(lambda x: x == a[len(a)/2], a) + qsort(filter(lambda x: x>a[len(a)/2], a)) 

对于有关稳定/不稳定分类讨论，请看这里http://www.developerfusion.com/article/3824/a-guide-to-sorting/6/。

你可能想要一本好的算法书（即Cormen或Skiena）。

Answer 5

• Heapsort，也许randomized quicksort
• stable sort
• 为他人已经提到：没有没有。例如，你可能想要并行化你的排序算法。这导致了完全不同的排序算法..

Answer 6

关于你的问题意味着稳定，让我们考虑以下因素：我们有一类与年龄相关的儿童：

Phil, 10 
Hans, 10 
Eva, 9 
Anna, 9 
Emil, 8 
Jonas, 10 

现在，我们要排序的儿童按年龄递增（没有别的）。然后，我们看到菲尔，汉斯和乔纳斯都已经有10岁了，所以我们不清楚我们要点什么顺序，因为我们只按年龄排序。

现在来稳定：如果我们排序稳定我们排序菲尔，汉斯和乔纳斯在他们以前的顺序，即我们把菲尔先，然后汉斯，最后，乔纳斯（只是因为他们在这个顺序在原始序列中，我们只考虑年龄作为比较标准）。同样的，我们必须在安娜之前把伊娃（都是同一个年龄段，但是伊娃在安娜之前的原始序列）。

所以，其结果是：

Emil, 8 
Eva, 9 
Anna, 9 
Phil, 10 \ 
Hans, 10 | all aged 10, and left in original order. 
Jonas, 10/

为了把它在一个概括地说：稳定性意味着，如果两个元素是相等的（WRT所选择的排序标准），所述一个来首先在原始序列在结果序列中仍然排在第一位。

注意，您可以轻松地将任何排序算法到一个稳定的排序算法：如果您原来的序列持有n元素：e1, e2, e3, ..., en，您只需连接一个计数器每个：(e1, 0), (e2, 1), (e3, 2), ..., (en, n-1)。这意味着您为每个元素存储其原始位置。

如果现在两个元素相等，您只需比较它们的计数器并首先将计数器值较低的那个计数器。这增加了运行时（和内存）O(n)，这是渐近没有恶化，因为最佳（比较）排序算法需要已经O(n lg n)。