问Java & Merge排序

EN

Java专家在最坏的情况下使用了avg，正如您可能知道的那样，在最坏的情况下，快速排序可能会运行O(n^2)。

您可以读入API，就地对链表进行排序更加复杂n^2log(n)

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

我认为选择mergesort的主要原因是因为它很稳定。

其他人提到的n log n最坏情况保证是一个优势，但它可能不是主要原因。如果查看Arrays.sort方法，就会发现原语上的所有排序都使用quicksort，而Object[]上的排序使用mergesort。这是因为稳定的排序对于基元来说并不重要；相等的基元彼此之间不能区分。

• 合并排序保证了O(n log n)行为。快速排序的最坏情况性能为O(n^2)。所以在某些情况下，合并排序速度更快，并且有更好的上限。
• 像快速排序这样的就地排序在链表上不起作用，正如你的引言所提到的那样。若要对所有类型的集合进行可预测的工作，需要一个副本。
• 快速排序本身并不稳定。稳定性有时是可取的，也是API应该提供的东西。