快速排序和调整快速排序之间的区别是什么？ [英] What is the difference between quicksort and tuned quicksort?

问题描述

什么是快速排序和调整快速排序之间的根本区别是什么？什么是给快速排序的改进？如何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?

推荐答案

调整快速排序只是意味着一些改进应用到的基本算法。一般的改进是尽量避免最坏的情况下的时间复杂度。改进一些例子可能是选择枢轴（或多个枢轴），使得从未有仅1键在一个分区，或者仅使递归调用时一个分区是高于某个最小尺寸。

"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.

它看起来像Java只使用排序对象（的阵列DOC 告诉你哪个排序算法用于哪种类型的方法签名），所以我不认为它曾经真正决定自己，但决定是提前。 （另外，实施者可以自由使用另一分类，只要它是稳定的。）

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.)

这篇关于快速排序和调整快速排序之间的区别是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！