为什么Collections.sort使用合并排序而不是快速排序？

Question

我们知道快速排序是最快的排序算法.

collections.sort使用合并排序算法而不是快速排序.但是Arrays.sort使用快速排序.

Collections.sort使用合并排序而不是快速排序的原因是什么？

Answer 1

从乔希布洛赫极有可能§:

我确实写过这些方法,所以我想我有资格回答.确实没有单一的最佳排序算法.与mergesort相比,QuickSort有两个主要缺陷:

1. 它不稳定(正如parsifal指出的那样).

2. 它不保证 n log n性能; 它可以降低到病理输入的二次性能.

稳定性对于原始类型来说不是问题,因为没有不同于(值)平等的身份概念.并且,对于Bentely和McIlroy的实现(或随后的Dual Pivot Quicksort),二次行为的可能性在实践中被认为不是问题,这就是为什么这些QuickSort变体被用于原始类型的原因.

排序任意对象时,稳定性是一个大问题.例如,假设您有表示电子邮件的对象,并且您首先按日期对其进行排序,然后按发件人对它们进行排序.您希望它们在每个发件人中按日期排序,但只有在排序稳定时才会生效.这就是我们选择提供稳定排序(Merge Sort)来排序对象引用的原因.(从技术上讲,多个顺序稳定排序会导致按照与排序相反的顺序对键进行字典排序:最终排序决定了最重要的子键.)

无论输入是什么,Merge Sort都能保证 n log n(时间)性能,这是一个很好的附带好处.当然有一个缺点:快速排序是一种"就地"排序:它只需要记录外部空间(以维护调用堆栈).另一方面,合并,排序需要O(n)外部空间.如果输入数组几乎排序,则TimSort变体(在Java SE 6中引入)需要的空间(O(k))要少得多.

此外,以下是相关的:

java.util.Arrays.sort和(间接)java.util.Collections.sort用于排序对象引用的算法是"修改后的mergesort"(如果低子列表中的最高元素小于,则省略合并)高子列表中的最低元素.)" 它是一种相当快速稳定的排序,可确保O(n log n)性能并需要额外的O(n)空间.在它的日子里(它是由Joshua Bloch在1997年写的),它是一个很好的选择,但今天我们可以做得更好.

自2003年以来,Python的列表排序使用了一种称为timsort的算法(在Tim Peters之后编写).它是一个稳定的,自适应的迭代合并输出,在部分排序的阵列上运行时需要远远少于n log(n)的比较,同时在随机阵列上运行时提供与传统mergesort相当的性能.像所有正确的mergesorts一样,timsort是稳定的并且在O(n log n)时间内运行(最坏的情况).在最坏的情况下,timsort需要临时存储空间来进行n/2个对象引用; 在最好的情况下,它只需要很小的恒定空间.将此与当前实现进行对比,当前实现总是需要额外的空间用于n个对象引用,并且仅在几乎排序的列表上击败n log n.

Timsort在这里有详细描述:http://svn.python.org/projects/python/trunk/Objects/listsort.txt .

Tim Peters最初的实现是用C编写的.Joshua Bloch将它从C移植到Java并最终测试,基准测试和调整得到的代码.生成的代码是java.util.Arrays.sort的替代品.在高度有序的数据上,此代码的运行速度最高可达当前实现的25倍(在HotSpot服务器VM上).在随机数据上,新旧实现的速度是可比的.对于非常短的列表,新的实现比旧的甚至随机数据快得多(因为它避免了不必要的数据复制).

另外,请参阅Java 7使用Tim排序方法Arrays.Sort吗？.

没有一个"最佳"选择.与许多其他事情一样,这是关于权衡.