quicksort算法的平均时间复杂度为 O(n*log(n))，最坏情况复杂度为 O(n^2)。
假设 Hoare 快速排序算法的某些变体，什么样的输入会导致快速排序算法表现出最坏情况的复杂性？
请说明与特定快速排序算法(例如主元选择等)的实现细节相关的任何假设，或者它是否来自 libc 等常用库。
一些阅读:
最佳答案
Quick sort表现最差，即在 O(n^2) 时，当所选枢轴的所有值都是所采用集合的最大或最小值时。考虑这个例子。
1 2 3 4 5
枢轴选择为 1，枢轴右侧有 4 个元素，左侧没有元素。递归地应用相同的逻辑，选择的基准分别为 2、3、4、5，我们得到了这种排序在最坏可能时间执行的情况。
有人推荐并证明，如果输入打乱得很好，快速排序的性能会很好。
此外，排序的选择通常取决于对输入域的清晰了解。例如，如果输入很大，那么有一种称为外部排序的东西可能会使用外部存储器。如果输入大小非常小，我们可能会进行归并排序，但对于中型和大型输入集则不行，因为它会占用额外的内存。快速排序的主要优点是它的“就地”意义，输入数据不使用额外的内存。它在纸面上的最坏情况时间是 O(n^2) 但仍然被广泛首选和使用。我的观点是，可以根据对输入集的了解及其偏好来更改排序算法。
关于c++ - 使用快速排序观察二次行为 - O(n^2)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4708419/