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

Question

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

Answer 1

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

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

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