快速排序平均和最差情况下的复杂性混淆？

Question

对于快速排序的平均和最差情况，我有点困惑。我知道以下内容：

1. 快速排序为O（nlogn）的平均情况复杂选择了中间的支点时。
2. 快速排序最差情况下的复杂性是选择Minimum或Maximum元素作为关键点。
3. 上述两种情况都会为几乎排序的元素列表和未排序的数据列表提供相同的复杂度。

是以上三点是真的吗？如果没有，我想知道如何快速排序行为几乎排序列表和未排序的列表？

Answer 1

你说得对（1）和（2）。如果枢轴将数据分成大约一半（理想情况下枢轴为中位数），则快速排序表现良好，并且当分区不均匀时排列不佳。

输入数据是否被排序的重要性取决于如何选择关键点。

枢纽的最简单的可能的选择是把你划分部分的第一要素。如果你这样做，并且数据被排序或者反向排序，那么你得到最不平均的可能的除法，因为你选择的数据是该范围中最小或最大的值。

下最简单的，我想，是沿输入中途取作为枢轴的元素。那么如果数据已经被排序，你会得到最好的分割。欢呼！但是这个中间元素仍然可能是这个范围内的最小值（或者最大值），在这种情况下，你会得到一个不好的分割。嘘！使用各种技术可以做出更好的枢轴选择：“三位数中位数”，“伪中位数九”或随机的（在这种情况下，恶意用户不能构造出最坏情况，案件发送给你，并且一个坏案件的可能性对于显着大小的投入是如此之小以至于在实践中你不能合理照顾）。

你可以甚至使用中位数的位数quickselect找到线性时间中位数和使用它作为枢轴，从而完全避免为O（n^2）最坏情况。实际上，有一个更好的方法可以避免O（n^2）最差的情况：Introsort。

当人们谈论“快速排序”，他们并不一定意味着转动的任何特定的选择，所以你不能说什么快速排序将不指定一个选择这样做。 Hoare对Quicksort的第一个描述使用第一个元素作为关键点，我认为，所以它对接近排序或接近反向排序的数据的速度很慢。