algorithm - 快速排序算法——说明

Question

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

我明白它是如何工作的，如果我不明白，网上有很多资料供我研究。我在这里遇到的问题是，我发现的一些文章陈述如下 ( from wikipedia):

Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.

一些其他来源，( hackerrank video ):

We swap elements around such that all elements smaller than the pivot come before elements that are bigger than the pivot

这两种算法有很大的不同。第一个使用枢轴拆分数组，将较小的所有内容放在一侧，将较大的所有内容放在另一侧。

第二个不关心主元本身，但它会确保所有小于主元的元素都排在比主元大的元素之前。甚至没有提到枢轴的最终位置。

因此，如果这是要对 [3, 15, 4, 8, 12] 进行排序的数组，并且基准值为 8

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

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

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

Answer 1

两个主要的快速排序分区方案是 Lomuto 和 Hoare。两者都在 wiki 文章中用伪代码进行了解释:

https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme

https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme

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

对于 Lomuto 方案，枢轴位于子数组的左端或右端，并且有一个最终交换将枢轴放在适当的位置。对于 Lomuto，枢轴元素不包含在递归调用中。

对于 Hoare 方案，由于算法的工作方式，枢轴最终到位。然而，枢轴最终成为左分区的最后一个元素或右分区的第一个元素。可以添加额外的代码来从递归中排除枢轴元素，但它最终会稍微慢一些。 Hoare 方案通常比 Lomuto 方案快。

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

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

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

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

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