快速排序算法--澄清

Question

我一直在看不同的视频和阅读不同的文章关于快速排序算法。

我理解它是如何工作的，如果我没有，有大量的在线材料供我查看。我在这里遇到的问题是，我发现的一些文章声明如下(从维基百科)：

重新排序数组，这样所有值小于枢轴的元素都会出现在枢轴之前，而值大于枢轴的所有元素都会出现在它之后(等量值都可以)。在此分区之后，枢轴处于其最后位置。这称为分区操作。

其他一些来源，(hackerrank视频)：

我们在周围交换元素，使得所有小于枢轴的元素都在大于枢轴的元素之前。

这两种算法有很大的不同。第一种方法使用枢轴将数组拆分，并将较小的东西放在一边，而将较大的东西放在另一边。

第二种方法与枢轴本身无关，但它将确保所有小于枢轴的元素都先于较大的元素。甚至没有提到枢轴的位置。

因此，如果这是排序3，15，4，8，12的数组，而枢轴是8

解决方案1: 3、4、8、15、12

解决方案2: 3、8、4、15、12

我发现有很多互相矛盾的意见，我想知道这是否重要，但我想知道是否有正确的实施方法，或它可以有所不同。

Answer 1

两个主要的快速分区方案是洛穆托和霍尔。这两者都在wiki文章中的伪代码中进行了解释：

方案

方案

对于这两种方案，每个分区步骤都将支点置于其最后的排序位置。在分区步骤之后，等于枢轴的元素可以在左或右分区中结束(但枢轴元素以其正确的位置结束)。

对于洛穆托方案，支点要么位于子数组的左端，要么位于子数组的右端，并有一个最终交换来将支点放置到位。对于洛穆托，支点元素不包含在递归调用中。

对于Hoare方案，由于该算法的工作方式，支点结束在适当的位置。但是，支点作为左分区的最后一个元素或右侧分区的第一个元素结束。可以添加额外的代码来从递归中排除pivot元素，但是它最终会稍微慢一些。Hoare计划的速度通常比洛穆托快。

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

中庸

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

另一种方法是使用一种混合排序，如内部排序，如果递归级别超过某个阈值，则切换到堆排序。

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