使用快速排序观察二次行为 - O(n ^ 2)

Question

的快速排序算法为O的平均时间复杂度(N*的log(n))和O的最坏情况下的复杂性(N ^ 2).

假设Hoare的快速排序算法的一些变体,哪种输入会导致快速排序算法表现出最坏的情况复杂性？

请说明与特定快速排序算法的实施细节有关的任何假设,例如枢轴选择等,或者它是否来自诸如libc之类的常用库.

一些阅读:

1. Quicksort的杀手对手
2. Quicksort是最佳的
3. 设计排序功能
4. 内省的排序和选择算法

Answer 1

的快速排序执行最坏即,在为O(n ^ 2)时所选择的枢轴的所有值或者是拍摄组的最大或最小.考虑这个例子.

1 2 3 4 5

选择的枢轴为1,您将在枢轴的右侧有4个元素,左侧没有元素.递归地应用这个相同的逻辑并且选择的枢轴分别是2,3,4,5,我们已经达到了这种情况,即在最糟糕的时间执行.

已经推荐并证明,如果输入被很好地改进,Quicksort表现良好.

此外,选择排序通常取决于对输入域的清晰知识.例如,如果输入很大,那么有一种称为外部排序的东西可能会使用外部存储器.如果输入大小非常小,我们可能会进行合并排序,但不能用于中型和大型输入集,因为它使用额外的内存.Quick sort的主要优点是它的"就地"含义,没有额外的内存用于输入数据.它在纸上的最坏情况时间是O(n ^ 2),但仍然是广泛优选和使用的.我的观点是,排序算法可以根据输入集的知识及其偏好来改变.