快速排序算法-澄清

Question

我知道它是如何工作的，如果我不知道的话，网上有很多资料供我查阅。我在这里遇到的问题是，我找到的一些文章陈述如下（来自维基百科）：

对数组重新排序，使所有值小于透视的元素都在透视之前，而所有值大于透视的元素都在透视之后（相等的值可以从任一方向移动）。分区后，枢轴处于其最终位置。这称为分区操作。

其他一些消息来源，（hackerrank视频）：

第二种方法与枢轴本身无关，但它将确保所有比枢轴小的元素在比枢轴大的元素之前出现。甚至没有提到枢轴的终点。

所以如果这是要排序的数组[3,15,4,8,12]并且枢轴是8

解决方案1:[3,4,8,15,12]

我发现有这么多相互矛盾的意见，我想知道这是否重要，但我想知道是否有一个正确的方法来执行它，或者它可以是不同的。

Answer 1

两种主要的快速排序分区方案是Lomuto和Hoare。wiki文章中的pseudo code对这两种方法都进行了解释：

https://en.wikipedia.org/wiki/quicksort#lomuto_partition_scheme

https://en.wikipedia.org/wiki/quicksort#hoare_partition_scheme

对于Lomuto方案，枢轴要么位于子数组的左端，要么位于子数组的右端，有一个最后的交换来将枢轴放置到位。对于Lomuto，pivot元素不包括在递归调用中。

对于Hoare格式，由于算法的工作方式，枢轴最终就位。然而，枢轴最终作为左分区的最后一个元素或右分区的第一个元素结束。可以添加额外的代码来将pivot元素排除在递归之外，但最终会稍微慢一些。Hoare方案一般比Lomuto更快。

为了避免简单数据模式（如已排序数据、反向排序数据）的最坏情况下的O(n^2)时间复杂度，可以在开始时使用3的中位数，对子数组中的第一个、中间和最后一个元素进行排序，然后使用中间元素作为枢轴。另一种选择是选择一个随机数据透视，但是生成一个随机索引通常需要进行乘法、加法和除法（对于模），从而增加了开销。其他方案如中值的中值保证了O（n log（n））的时间复杂度，但常因子开销是标准方案的倍数。

https://en.wikipedia.org/wiki/median_of_medians

最坏情况下的堆栈复杂度可以限制在O（log（n））,方法是在分区步骤中只使用两个分区中较小的分区的递归,然后循环回去处理较大的分区。这并不能避免时间复杂度O(n^2)。

另一种选择是使用像introsort这样的混合排序，如果递归级别超过某个阈值，则切换到堆排序。