&合并排序

Java的家伙们把最坏的情况换成了平均情况,正如你可能知道的,在最坏的情况下,快速排序可能运行在O(n^2)中。。

您可以在API中读取,对链表进行就地排序更为复杂n^2log(n)

合并排序是稳定的,这对于快速排序的有效版本是不正确的。 (这在排序对象时可能非常重要+许多程序员在使用Collections.sort()时都认为这是理所当然的)

该算法保证了n-log(n)的性能。

合并排序没有快速排序的病理案例

与快速排序相比,合并排序的另一个优点是合并排序是稳定的;快速排序通常是不稳定的(很明显只要你付出足够的努力 制作 它是稳定的,但我认为这样做相对昂贵。)

对数性能 那是因为试图

能够 看看列表是否实现了 RandomAccess 如果是这样的话,就分类,但是 随机存取

我相信选择mergesort的主要原因是因为它是稳定的。

其他人提到的n logn最坏情况保证是一种优势,但它可能不是主要原因。如果你看看 Arrays.sort Object[] 使用合并排序。这是因为稳定排序对原语不重要;相等的原语不能相互区分。

• 合并排序保证了O(n logn)行为。快速排序的最坏性能为O(n^2)。所以在某些情况下,合并排序更快,而且它有更好的上界。

• 正如您引用的那样,像quick sort这样的就地排序在链表上不起作用。为了可预测地适用于所有类型的集合,需要一个副本。

• 快速排序本身并不稳定。稳定性有时是需要的,API应该提供一些东西。