为什么Arrays.sort是快速排序算法，为什么不是另一种排序算法呢？
为什么？ 它更快还是更有效？
对于具有一个核心的系统，我们可以使用快速排序。 我们应该在具有两个内核，四个内核或八个内核的系统上使用什么？
Quicksort具有O（n log n）平均值和O（n ^ 2）最差情况性能，这是排序算法可能的最佳“平均情况”，还有其他排序算法具有此性能，但quicksort往往表现更好比大多数人。
请参阅： http ： //en.wikipedia.org/wiki/Quicksort
Quicksort具有完全就位的优点，因此它不需要任何额外的存储，而mergesort（实际上由Arrays.sort()用于对象数组）和其他（所有？）保证O（n * log n）算法至少需要一个完整的数组副本。 对于对非常大的原始数组进行排序的程序，这意味着可能会使整体内存使用量翻倍。
答案在Jon L. Bentley和M. Douglas McIlroy的“工程排序函数”中 ，排序函数引用了该函数。
为了获得更好的qsort，我们发现1983年在Berkeley编写的qsort会在包含少量重复多次元素的数组上消耗二次时间 – 特别是随机零和1的数组。 事实上，在十几个不同的Unix库中， 我们发现没有qsort不能轻易被驱动到二次行为 ; 所有这些都来自第七版或1983年的伯克利函数….
无法找到足够好的qsort，我们打算建立一个更好的。 该算法应该避免合理输入的极端减速，并且应该在“随机”输入上快速。 它在数据空间和代码空间中也应该是高效的。 排序不一定稳定; 它的规范不保证保持相等元素的顺序。
由于Java是在20世纪90年代初创建的，所以替代品是heapsort和mergesort。 Mergesort不太理想，因为它需要额外的存储空间。 Heapsort具有更好的最坏情况性能（ O(n log n)与O(n^2) ），但在实践中表现更慢。 因此，如果您可以通过良好的启发式方法控制最坏情况的性能，那么可以采用经过调整的快速排序方式。
Java 7正在转向Timsort ，它是1993年发明的（2002年在Python中实现），具有O(n log n)的最差情况，并且是一种稳定的类型。
这是一个经过调整的快速排序。 如果您真的感兴趣，可以阅读文档中提到的材料。
排序算法是一个经过调整的快速排序，改编自Jon L. Bentley和M. Douglas McIlroy的“工程排序function”，软件实践和经验，卷。 23（11）P。1249-1265（1993年11月）。
这里有一点解释 – 调优版本在许多数据集上给出了n * log（n）：
该算法在许多数据集上提供n * log（n）性能，导致其他快速降序降级为二次性能
与Quicksort相比，Mergesort的比较次数较少，但移动元素的数量较多。
在Java中，元素比较昂贵但移动元素很便宜。 因此，Mergesort在标准Java库中用于通用排序
在C ++中，复制对象可能很昂贵，而比较对象通常相对便宜。 因此，quicksort是C ++库中常用的排序例程。
参考： http ： //www.cs.txstate.edu/~rp44/cs3358_092/Lectures/qsort.ppt
首先，Arrays.sort不仅使用快速排序，它还使用多个算法java1.6
请参阅以下Arrays类中的代码
/ ** *将指定的数组按升序排序。 * *
实施注意事项：排序算法是由Vladimir Yaroslavskiy，Jon Bentley和Joshua Bloch组成的Dual-Pivot Quicksort *。 该算法*在许多数据集上提供O（n log（n））性能，导致其他*快速降级到二次性能，并且通常比传统（单枢轴）Quicksort实现快*。 * * @param要排序的数组* / public static void sort（int [] a）{DualPivotQuicksort.sort（a）; }
DualPivotQuicksort.sort(a); // This uses 5 algorithms internally depending upon dataset size do checkout the source code of Arrays class.
在java 1.6之前我认为它使用三种算法快速排序原始类型，如int和mergesort用于对象，当快速排序执行它开始堆排序时，请参阅此处了解更多详细信息http://cafe.elharo.com/programming/ java的编程/为什么-java的util的arrays用途，二，排序的算法
Quicksort平均速度最快O(n log(n)) ，因此Sun可能将其作为一个很好的指标。
QuickSort是一种常见的排序算法。 它的速度相当快，除非要排序的数据已经是相反的顺序。 它在太空中也很有效率。
这取决于你想做什么。 正常快速排序的问题是，它有时可以是O（n²）。 所以通常你可以使用堆排序，但大多数时候快速排序更快。
然而，Arrays.sort（…）实现使用了“调整过的快速排序，改编自Jon L. Bentley和M. Douglas McIlroy […]”（根据JavaDoc文档）。 该算法具有一些优化构建，使其能够在O（n * log（n））上工作，其中正常的快速排序将使用O（n²）。
此外，Arrays.sort算法一遍又一遍地进行测试，你可以确定它是有效的并且是无错的（虽然这不能保证。）
iuiz
Arrays.sort（）使用多种排序算法，具体取决于数组中的大小和元素。
- 小数组的插入排序
- 合并排序主要是排序的数组
- 高度调整和适应性强的双枢轴和单枢轴快速配件，适用于其他一切
所以在实践中我们看到快速排序对于大型基元数组来说非常快，但是当它需要适应部分排序的数组时，当对象之间的比较缓慢，稳定排序等等时，它会有一些缺陷。
自从这个post上次回答以来已经有一段时间了，这里有一些更新……
它依赖于复杂性及其与数组大小的相关性以及当Java研究这些算法时的概率，并且仅取决于测量和基准。
根据JAVA JDK 1.8 DOCS它的自解释，它根据一些阈值选择不仅一个算法而且最多四个算法…
/** * If the length of an array to be sorted is less than this * constant, Quicksort is used in preference to merge sort. */ private static final int QUICKSORT_THRESHOLD = 286; /** * If the length of an array to be sorted is less than this * constant, insertion sort is used in preference to Quicksort. */ private static final int INSERTION_SORT_THRESHOLD = 47; /** * If the length of a byte array to be sorted is greater than this * constant, counting sort is used in preference to insertion sort. */ private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29; /** * If the length of a short or char array to be sorted is greater * than this constant, counting sort is used in preference to Quicksort. */ private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200;
参考 Java DOC JDK 8
它的事件演变为在Java中使用并行排序排序
Java 8附带了一个新的API – parallelSort – 具有与Arrays.sort() API类似的签名：
@Test public void givenIntArray_whenUsingParallelSort_thenArraySorted() { Arrays.parallelSort(toSort); assertTrue(Arrays.equals(toSort, sortedInts)); }
在parallelSort （）的幕后，它将数组分成不同的子数组（根据parallelSort算法的粒度）。 每个子数组都使用不同线程中的Arrays.sort （）进行排序，以便排序可以并行方式执行，最后作为排序数组合并。
请注意，ForJoin公共池用于执行这些并行任务，然后合并结果。
Arrays.parallelSort的结果当然与Array.sort相同，这只是利用multithreading的问题。
最后，在Arrays.parallelSort中也有类似的API Arrays.sort变体：
Arrays.parallelSort (int [] a, int fromIndex, int toIndex);
简介 ：因此，随着Java API与HardWare和软件一起发展，在阈值和算法上有更多用于multithreading和调优的方法。