快速排序和优化的快速排序有什么不同？

Question

快速排序和优化的快速排序之间的根本区别是什么？快速排序的改进是什么？Java是如何决定使用这种排序而不是合并排序的？

Answer 1

“调优”快速排序只是意味着对basic algorithm应用了一些改进。通常，改进是为了尽量避免最坏情况下的时间复杂性。一些改进的例子可能是选择枢轴(或多个枢轴)，这样分区中永远不会只有一个键，或者只有当分区大于某个最小大小时才进行递归调用。

看起来Java只在对对象进行排序时才使用合并排序( Arrays doc会告诉你哪种排序算法用于哪种排序方法签名)，所以我不认为它会自己“决定”，但这个决定是事先做出的。(而且，实现者可以自由地使用另一种类型，只要它是稳定的。)

Answer 2

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

最坏情况时间复杂度

当每个步骤的分区的一侧总是有零个元素时，快速排序会出现最坏的时间复杂度。当一个分区中的元素与另一个分区中的元素的比率远远不是1:1 (例如10000:1)时，就会出现接近最坏情况的时间复杂度。造成这种最坏情况复杂性的常见原因包括但不限于：

1. 一种快速排序算法，它始终选择与透视具有相同子数组相对索引的元素。例如，对于已经排序的数组，总是选择子数组最左边或最右边的元素作为轴心的快速排序算法将是O(N^2)。总是选择中间元素的快速排序算法为器官管道数组提供了O(N^2) (1,2,3,4,5,4,3,2,1就是一个例子)。
2. 不处理数组中重复/重复元素的快速排序算法可以是O(N^2)。最明显的例子是对包含所有相同元素的数组进行排序。明确地说，如果快速排序将数组排序成像= p这样的分区，那么左边的分区将始终有零个元素。

如何解决这些问题？第一个问题通常是通过随机选择轴心来修复的。使用几个元素的中位数作为轴心也会有所帮助，但排序为O(N^2)的概率高于使用随机轴心的概率。当然，一些随机选择的元素的中位数也可能是一个明智的选择。在这里，三个随机选择的元素的中位数作为枢轴是一种常见的选择。

第二种情况是重复元素，通常使用类似Bentley-McIlroy paritioning(链接到pdf)或Dutch National Flag problem的解决方案来解决。然而，Bentley-McIlroy分区更常用，因为它通常更快。我想出了一个比它更快的方法，但这不是这篇文章的重点。

Optimizations

以下是上面列出的方法之外的一些常见优化，以帮助应对最坏的情况：

1. 使用收敛指针快速排序，而不是基本的快速排序。当this.
2. Insertion排序子数组小于特定大小时，如果需要更详细的说明，请让我知道。插入排序渐近为O(N^2)，但对于足够小的N，它优于使用显式堆栈的迭代快速排序，而不是循环的递归quicksort.
3. Unrolling部分，以减少比较次数。
4. 将透视复制到寄存器，并使用数组中的该空间来减少交换元素的时间成本。

其他备注

Java在对对象进行排序时使用mergesort，因为它是一种稳定的排序(保留了具有相同键的元素的顺序)。快速排序可以是稳定的或不稳定的，但稳定的版本比不稳定的版本慢。

Answer 3

在java中，Arrays.sort(Object[])使用合并排序，但所有其他重载排序函数都使用

如果长度小于7，则插入排序；如果数组长度大于7，则使用

调整了快速排序。