当稳定性不是必需的时候，有没有什么常用的、高效的Java排序实现？

Question

Java实现(至少是我使用的那个，它是Oracle的JDK版本1.8 )使用了一个稳定的排序。对于稳定，我指的是保证根据排序标准相等的两个对象A和B保持其原始顺序的算法。但是，我有一个对对象进行排序的用例，并且我不需要排序是稳定的。

我还注意到(通过分析)优化这种排序对我来说是有益的。因为我不需要稳定的排序，而且我认为不稳定的排序可以更快，所以我想用不稳定的(希望是更快的)排序替换这里的默认排序。有没有什么好的，知名的，常用的实现呢？你能推荐一些吗？

在最坏的情况下，自己实现算法总是一种选择，但我更喜欢已经经过彻底测试和分析并被广泛使用的现有实现。不幸的是，我找不到这样的实现。

编辑:我假设不稳定排序可能比稳定排序更快的原因是因为不稳定排序的任务比稳定排序任务更容易，或者和稳定排序任务一样难。稳定排序的每个解决方案也是不稳定排序的解决方案，但事实并非如此。我意识到，在实践中，这并不一定意味着不稳定的排序算法会更快，但在理论上是可能的，所以我想探索一下这种选择

Answer 1

根据各种评论，看起来TimSort (这是Java用于排序的默认实现，并且是一种稳定的排序)可能是可用的最佳选项之一。

然而，通过更多的谷歌搜索，我确实找到了这个可能比TimSort更快的"Vergesort"算法。虽然它是用C++实现的，但如果我有时间，我可能会尝试将其移植到Java语言，对其进行基准测试，并在此处描述结果。

我的数据特别倾向于包含升序或降序元素的短序列，这是VergeSort页面上描述的两个“锯齿”基准测试的一种组合。在这些基准测试中，VergeSort的表现优于TimSort。但是，C++中的这些基准测试对纯整数进行排序，而不是对指向数据的指针进行排序(正如rcgldr所描述的，在Java语言中更有可能是这种情况)。

Answer 2

Wikipedia has a great table for you

据我所知，正如Nayuki所说，你最好的选择是快速排序和堆排序。

感谢Here's，这是一个堆排序的快速实现，谢谢GitHub。

当然，如果这是针对您想要使用的真实数据，那么只需使用Oracle的排序即可。可能很难找到一种更有效的排序，而且它的稳定性通常是没有意义的。