快速排序和调整后的快速排序有什么区别？

Question

快速排序和调整后的快速排序之间的根本区别是什么？对于快速排序，有何改进之处？Java如何决定使用它而不是归并排序？

- unj2

Answer 1

正如蜥蜴比尔所说，经过调整的快速排序仍具有与基本快速排序相同的复杂度 - O(N log N)平均复杂度 - 但是经过调整的快速排序使用一些不同的方法来尝试避免O(N^2)最坏情况下的复杂度，并使用一些优化来减少N log N前面的常数以达到平均运行时间。

最坏时间复杂度

当每一步的分区一侧始终没有元素时，快速排序的最坏时间复杂度会发生。当一个分区中的元素与另一个分区中的元素的比率远离1:1时（例如10000:1），近似最坏时间复杂度会发生。导致这种最坏情况复杂度的常见原因包括但不限于：

1. 快速排序算法总是选择子数组中与相对位置相同的元素作为枢轴。例如，对于已经排序好的数组，一个总是选择子数组最左边或最右边的元素作为枢轴的快速排序算法将会是O(N^2)。而总是选择中间元素作为枢轴的快速排序算法，在有机管数组（[1,2,3,4,5,4,3,2,1]是其示例）中也是O(N^2)。

2. 在数组中存在重复元素的情况下，不处理这些元素的快速排序算法可能会是O(N^2)。明显的例子是对包含所有相同元素的数组进行排序。具体来说，如果快速排序将数组按照[ < p | >= p ]的方式分区，那么左侧分区将始终没有元素。

如何解决这些问题？第一个问题通常通过随机选择枢轴来解决。使用几个元素的中位数作为枢轴也可以帮助解决问题，但是使用随机枢轴的排序出现O(N^2)的概率比较高。当然，从随机选择的几个元素中选取中位数也是一个明智的选择。在这里，选择三个随机选取的元素的中位数作为枢轴是一个常见的选择。

第二种情况，即重复元素，通常可以通过类似Bentley-McIlroy partitioning（链接到pdf）或Dutch National Flag problem的解决方案来解决。然而，Bentley-McIlroy分区更常用，因为它通常更快。我想出了一种比它更快的方法，但这不是本文的重点。 优化 以下是一些常见的优化方法，超出上述方法的范围，以帮助处理最坏情况：

1. 使用收敛指针快速排序而不是基本快速排序。如果需要更详细的解释，请告诉我。

2. 在子数组大小低于某个阈值时使用插入排序。插入排序的渐近时间复杂度为O(N^2)，但对于足够小的N，它比快速排序更快。

3. 使用显式栈的迭代快速排序而不是递归快速排序。

4. 展开循环的部分以减少比较次数。

5. 将枢轴复制到寄存器中，并利用该空间来减少交换元素的时间成本。

其他注意事项

Java在排序对象时使用归并排序，因为它是稳定排序（保留具有相同键的元素的顺序）。快速排序可以是稳定或不稳定的，但稳定版本比不稳定版本慢。

- Justin Peel

Answer 2

"调谐"快速排序指的是对基本算法应用了一些改进。通常这些改进是为了避免最坏时间复杂度。一些改进的例子可能是选择主元（或多个主元），以便在分区中永远不仅有一个关键字，或者仅当一个分区大小超过某个最小值时才进行递归调用。

看起来在Java中，当排序对象时只使用合并排序（Arrays doc告诉您哪种排序算法用于哪种排序方法签名），因此我认为它从未真正自行“决定”，而是提前做出的决策。（另外，实现者可以自由地使用其他排序方法，只要它是稳定的。）

- Bill the Lizard

Answer 3

在Java中，Arrays.sort(Object[])使用归并排序，但所有其他重载的排序函数在数组长度小于7时使用插入排序，在数组长度大于7时使用调优后的快速排序。

- Shekhar