我们知道快速排序是最快的排序算法。
JDK6 collections.sort使用归并排序算法而不是快速排序。但数组。Sort使用快速排序算法。
集合的原因是什么?排序使用归并排序而不是快速排序?
极有可能来自Josh Bloch §;
我确实写了这些方法，所以我想我有资格回答。它是的确，没有单一的最佳排序算法。快速排序了与合并排序相比，有两个主要缺陷:
不稳定(如parsifal所述)
它不保证 n log n性能;在病态输入下，它可以退化到二次性能。
对于基本类型来说，稳定性不是问题，因为没有区别于(价值)平等的同一性。以及在实践中，二次元行为被认为不是问题Bentely和McIlroy的实现(或随后的Dual Pivot)快速排序)，这就是为什么这些快速排序变体被用于基本排序。
在对任意对象排序时，稳定性是一个大问题。例如,假设您有表示电子邮件消息的对象，并对其进行排序先按日期，再按发件人。你希望它们被排序日期在每个发送者内，但只有当排序为时才会成立稳定。这就是为什么我们选择提供一个稳定的排序(归并排序)排序对象引用。(从技术上讲，多重顺序类中的键按字典顺序排序排序的反向顺序:最后的排序决定最多的重要的注册表子项。)
归并排序保证 n log n (time)性能无论输入是什么。当然，这也有不好的一面:快速排序是一种"就地"排序:它只需要log n的外部空间(维护调用堆栈)。另一方面，归并排序，需要O(n)外部空间。TimSort变体(在Java中引入)如果输入数组为，则需要更少的空间(O(k))近排序。
同样，以下是相关的:
java.util.Arrays.sort和(间接)by使用的算法sort对对象引用进行排序是一个"修改过的"中的最高元素省略合并排序低子列表小于高子列表中最低的元素)。它是一个相当快速稳定的排序，保证O(n log n)性能和需要O(n)额外空间。在它的时代，它是这样写的这是一个很好的选择，但今天，我们可以做得更好。
自2003年以来，Python的列表排序使用了一种称为timsort的算法(以作者蒂姆·彼得斯命名)。它是稳定的、自适应的、迭代的归并排序所需的比较远远少于n log(n)次在部分排序数组上运行，同时提供性能与在随机数组上运行时的传统归并排序相当。就像所有合适的归并排序都是稳定的，运行时间为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服务器虚拟机)。在随机数据上，新旧速度实现是可比较的。对于非常短的列表，新的即使在随机情况下，实现也比旧的要快得多数据(因为它避免了不必要的数据复制)。
另外，请参见Java 7是否对方法Arrays.Sort使用Tim Sort?
没有唯一的"最佳"选择。与许多其他事情一样，这是一个权衡的问题。