我们知道快速排序是最快的排序算法。JDK6的collections.sort使用归并排序算法，而不是快速排序。但Arrays.sort使用快速排序算法。为什么Collections.sort使用归并排序而不是快速排序呢？
为什么Collections.sort使用归并排序而不是快速排序？
110
- MayurB
10
3除非你能找到一个JDK开发人员来回答，否则你只能得出猜测结果。这不是一个真正的问题。 - user207421
4@EJP 说得好，但是“无建设性”可能是正确的关闭原因。对我来说，这里的问题很明显。 - Duncan Jones
6一个猜测：快速排序不稳定，归并排序是稳定的。对于基本类型，稳定/不稳定排序无关紧要，但对于对象来说可能会有影响（或者至少，您可能会收到针对不稳定排序的错误报告）。 - parsifal
3@EJP，JDK 作者的意图没有被公开之前存在障碍。一旦公开，我们不需要作者本人来回答。实际上，即使没有 JDK 作者的回答，也有可能得到一个超越猜测的答案。 - Pacerier
2想了解关于这个问题的信息，谷歌把我引到这里。但是这个问题因为“不是一个真正的问题”而被关闭了。在 Stack Exchange 中还有其他地方可以进行这种讨论吗？ - Shamal Karunarathne
显示剩余5条评论
1个回答
205
很有可能是来自Josh Bloch的§：
我写了这些方法，所以我想我有资格回答。确实，没有单一最佳的排序算法。与归并排序相比，快速排序有两个主要缺点：
1. 它不稳定（正如parsifal所指出的）。 2. 它不能保证n log n的性能；在某些特殊输入情况下，性能可能会退化为二次方。
对于原始类型来说，稳定性不是问题，因为没有身份的概念与（值）相等性不同。而且，Bentely和McIlroy的实现（或者随后的Dual Pivot Quicksort）被认为在实践中不会出现二次方行为的问题，这就是为什么这些快速排序变种被用于原始类型排序的原因。
当对任意对象进行排序时，稳定性是一个重要问题。例如，假设你有表示电子邮件的对象，并且你首先按日期，然后按发件人对它们进行排序。你希望它们在每个发件人内按日期排序，但只有在排序是稳定的情况下才会成立。这就是为什么我们选择提供一个稳定的排序（归并排序）来对对象引用进行排序的原因。（严格来说，多个连续的稳定排序会导致按排序的逆序对键进行词典排序：最后一次排序决定了最重要的子键。）
归并排序有一个好处，它无论输入是什么，都能保证n log n的性能。当然，也有一个缺点：快速排序是一种“原地”排序，它只需要log n的外部空间（用于维护调用栈）。而归并排序则需要O(n)的外部空间。在Java SE 6中引入的TimSort变种如果输入数组几乎有序，则需要更少的空间（O(k)）。
此外，以下内容是相关的：
java.util.Arrays.sort和（间接地）java.util.Collections.sort使用的算法是“修改的归并排序（如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并）”。它是一种相对快速的稳定排序，保证O(n log n)的性能，并需要O(n)的额外空间。在它的时代（由Joshua Bloch于1997年编写），它是一个很好的选择，但是现在我们可以做得更好。
自2003年以来，Python的列表排序使用了一种称为timsort的算法（由Tim Peters编写）。它是一种稳定的、自适应的、迭代的归并排序，在部分排序的数组上运行时，比n log(n)的比较次数要少得多，同时在随机数组上的性能与传统的归并排序相当。像所有合适的归并排序一样，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 Sort进行Arrays.Sort方法的排序？。
并没有一个单一的“最佳”选择。就像许多其他事情一样，这是一个权衡的问题。
我写了这些方法，所以我想我有资格回答。确实，没有单一最佳的排序算法。与归并排序相比，快速排序有两个主要缺点：
1. 它不稳定（正如parsifal所指出的）。 2. 它不能保证n log n的性能；在某些特殊输入情况下，性能可能会退化为二次方。
对于原始类型来说，稳定性不是问题，因为没有身份的概念与（值）相等性不同。而且，Bentely和McIlroy的实现（或者随后的Dual Pivot Quicksort）被认为在实践中不会出现二次方行为的问题，这就是为什么这些快速排序变种被用于原始类型排序的原因。
当对任意对象进行排序时，稳定性是一个重要问题。例如，假设你有表示电子邮件的对象，并且你首先按日期，然后按发件人对它们进行排序。你希望它们在每个发件人内按日期排序，但只有在排序是稳定的情况下才会成立。这就是为什么我们选择提供一个稳定的排序（归并排序）来对对象引用进行排序的原因。（严格来说，多个连续的稳定排序会导致按排序的逆序对键进行词典排序：最后一次排序决定了最重要的子键。）
归并排序有一个好处，它无论输入是什么，都能保证n log n的性能。当然，也有一个缺点：快速排序是一种“原地”排序，它只需要log n的外部空间（用于维护调用栈）。而归并排序则需要O(n)的外部空间。在Java SE 6中引入的TimSort变种如果输入数组几乎有序，则需要更少的空间（O(k)）。
此外，以下内容是相关的：
java.util.Arrays.sort和（间接地）java.util.Collections.sort使用的算法是“修改的归并排序（如果低子列表中的最高元素小于高子列表中的最低元素，则省略合并）”。它是一种相对快速的稳定排序，保证O(n log n)的性能，并需要O(n)的额外空间。在它的时代（由Joshua Bloch于1997年编写），它是一个很好的选择，但是现在我们可以做得更好。
自2003年以来，Python的列表排序使用了一种称为timsort的算法（由Tim Peters编写）。它是一种稳定的、自适应的、迭代的归并排序，在部分排序的数组上运行时，比n log(n)的比较次数要少得多，同时在随机数组上的性能与传统的归并排序相当。像所有合适的归并排序一样，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 Sort进行Arrays.Sort方法的排序？。
并没有一个单一的“最佳”选择。就像许多其他事情一样，这是一个权衡的问题。
- NPE
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接