快速排序和调整快速排序有什么区别？
快速排序和调整快速排序之间的根本区别是什么？快速排序有何改进？ Java 如何决定使用它而不是合并排序？
What is the fundamental difference between quicksort and tuned quicksort? What is the improvement given to quicksort? How does Java decide to use this instead of merge sort?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
正如蜥蜴比尔所说，调整的快速排序仍然具有与基本快速排序相同的复杂性 - O(N log N) 平均复杂度 - 但调整的快速排序使用一些不同的方法来尝试避免 O(N^2) 最坏情况的复杂性以及使用一些优化来减少平均运行时间 N log N 前面的常数。
最坏情况时间复杂度
当每个步骤的分区一侧始终具有零个元素时，快速排序会出现最坏情况时间复杂度。当一个分区中的元素与另一分区中的元素的比率远离 1:1（例如 10000:1）时，就会出现接近最坏情况的时间复杂度。这种最坏情况复杂性的常见原因包括但不限于：
快速排序算法始终选择与主元具有相同子数组相对索引的元素。例如，对于已经排序的数组，始终选择子数组最左边或最右边元素作为主元的快速排序算法的复杂度为 O(N^2)。始终选择中间元素的快速排序算法为风琴管数组提供 O(N^2)（[1,2,3,4,5,4,3,2,1] 就是一个例子）。
不处理数组中重复/重复元素的快速排序算法可以是 O(N^2)。一个明显的例子是对包含所有相同元素的数组进行排序。明确地说，如果快速排序将数组排序为分区，例如 [ << p| >= p ]，那么左侧分区将始终有零个元素。
这些是如何补救的呢？第一个通常可以通过随机选择枢轴来解决。使用几个元素的中位数作为主元也有帮助，但排序为 O(N^2) 的概率高于使用随机主元。当然，随机选择一些元素的中位数也可能是一个明智的选择。这里通常选择三个随机选择的元素的中值作为基准。
第二种情况，重复的元素，通常用类似 Bentley-McIlroy 分区（链接到 pdf）或 荷兰国旗问题。然而，Bentley-McIlroy 分区更常用，因为它通常更快。我想出了一种比它更快的方法，但这不是本文的重点。
优化
以下是上面列出的方法之外的一些常见优化，可帮助应对最坏的情况：
使用收敛指针快速排序而不是基本快速排序。如果您想对此进行更多详细说明，请告诉我。
当子数组低于特定大小时，对子数组进行插入排序。插入排序的渐进复杂度为 O(N^2)，但对于足够小的 N，它优于快速排序。
使用带有显式堆栈的迭代快速排序而不是递归快速排序。
展开部分循环以减少比较次数。
将主元复制到寄存器并使用数组中的该空间来减少交换元素的时间成本。
其他说明
Java 在对对象进行排序时使用归并排序，因为它是一种稳定排序（保留具有相同键的元素的顺序）。快速排序可以是稳定的，也可以是不稳定的，但稳定版本比不稳定版本慢。
As Bill the Lizard said, a tuned quicksort still has the same complexity as the basic quicksort - O(N log N) average complexity - but a tuned quicksort uses some various means to try to avoid the O(N^2) worst case complexity as well as uses some optimizations to reduce the constant that goes in front of the N log N for average running time.
Worst Case Time Complexity
Worst case time complexity occurs for quicksort when one side of the partition at each step always has zero elements. Near worst case time complexity occurs when the ratio of the elements in one partition to the other partition is very far from 1:1 (10000:1 for instance). Common causes of this worst case complexity include, but are not limited to:
A quicksort algorithm that always chooses the element with the same relative index of a subarray as the pivot. For instance, with an array that is already sorted, a quicksort algorithm that always chooses the leftmost or rightmost element of the subarray as the pivot will be O(N^2). A quicksort algorithm that always chooses the middle element gives O(N^2) for the organ pipe array ([1,2,3,4,5,4,3,2,1] is an example of this).
A quicksort algorithm that doesn't handle repeated/duplicate elements in the array can be O(N^2). The obvious example is sorting an array that contains all the same elements. Explicitly, if the quicksort sorts the array into partitions like [ < p | >= p ], then the left partition will always have zero elements.
How are these remedied? The first is generally remedied by choosing the pivot randomly. Using a median of a few elements as the pivot can also help, but the probability of the sort being O(N^2) is higher than using a random pivot. Of course, the median of a few randomly chosen elements might be a wise choice too. The median of three randomly chosen elements as the pivot is a common choice here.
The second case, repeated elements, is usually solved with something like Bentley-McIlroy paritioning(links to a pdf) or the solution to the Dutch National Flag problem. The Bentley-McIlroy partitioning is more commonly used, however, because it is usually faster. I've come up with a method that is faster than it, but that's not the point of this post.
Optimizations
Here are some common optimizations outside of the methods listed above to help with worst case scenarios:
Using the converging pointers quicksort as opposed to the basic quicksort. Let me know if you want more elaboration on this.
Insertion sort subarrays when they get below a certain size. Insertion sort is asymptotically O(N^2), but for small enough N, it beats quicksort.
Using an iterative quicksort with an explicit stack as opposed to a recursive quicksort.
Unrolling parts of loops to reduce the number of comparisons.
Copying the pivot to a register and using that space in the array to reduce the time cost of swapping elements.
Other Notes
Java uses mergesort when sorting objects because it is a stable sort (the order of elements that have the same key is preserved). Quicksort can be stable or unstable, but the stable version is slower than the unstable version.
“调整”快速排序仅意味着对基本算法进行了一些改进。通常，改进是为了尝试避免最坏情况的时间复杂度。一些改进的示例可能是选择主元（或多个主元），以便分区中永远不会只有 1 个键，或者仅在分区大于某个最小大小时才进行递归调用。
看起来Java在对对象进行排序时只使用合并排序（Arrays doc 告诉您哪种排序算法用于哪种排序方法签名），所以我认为它不会真正自行“决定”，但决定是提前做出的。 （此外，实施者可以自由使用另一种类型，只要它稳定。）
"Tuned" quicksort just means that some improvements are applied to the basic algorithm. Usually the improvements are to try and avoid worst case time complexity. Some examples of improvements might be to choose the pivot (or multiple pivots) so that there's never only 1 key in a partition, or only make the recursive call when a partition is above a certain minimum size.
It looks like Java only uses merge sort when sorting Objects (the Arrays doc tells you which sorting algorithm is used for which sort method signature), so I don't think it ever really "decides" on its own, but the decision was made in advance. (Also, implementers are free to use another sort, as long as it's stable.)
在java中，Arrays.sort(Object[])使用合并排序，但
如果长度小于7，则所有其他重载排序函数使用插入排序，如果数组长度大于7，则使用
调整快速排序。
In java, Arrays.sort(Object[]) uses merge sort but all other overloaded sort functions use
insertion sort if length is less than 7 and if length of array is greater than 7 it uses
tuned quicksort.