快速排序在 O(n^2) 时间内运行？

Question

这个问题在这里已经有了答案:





Quick sort Worst case

(6 个回答)


8 年前关闭。




谁能解释为什么快速排序的最坏情况运行时间是 O(n^2) 以及为什么这种情况很少见？

Answer 1

如果每次都以最差的方式选择主元，而不是划分为大小为 n/2 的两个列表，它将划分为大小为 1 的列表和大小为 n-1 的列表。这导致递归深度为 n，总时间为 n^2。

这是罕见的，因为枢轴通常是随机选择的，因此每次选择最差枢轴的机会很小，平均而言，枢轴倾向于将列表大致分成两半。

如果枢轴是非随机选择的，例如取第一个元素，那么某些输入(预排序或反向排序的列表)可以强制执行 n^2 性能。