big-o - 快速排序算法 - 只需要 n-1 比较的分区。我怎样才能做到这一点？

Question

“我们已经看到 partition() 执行 n 次比较（可能是 n-1 或 n+1，具体取决于实现）。”

来源：http ://homepages.math.uic.edu/~leon/cs-mcs401-r07/handouts/quicksort-continued.pdf

如果我采用 1、2、3、4、5、6、7、8 之类的序列（8 作为枢轴元素，n = 8），我认为我至少有 8 个比较而不是 7（n-1）

如果我从左向右移动以找到一个大于 8 的元素

1. 1 < 8
2. 2 < 8
3. 3 < 8
4. 4 < 8
5. 5 < 8
6. 6 < 8
7. 7 < 8

至少再进行一次比较，以检查我是否找到了一个小于 8 的元素 / 以检查 indizes 是否被交叉。8. 我 < j

分区的哪个实现只需要 n-1 个比较？

标签： big-ocomplexity-theoryquicksortpartition

Answer 1

当枢轴从未移动且从未与自身进行比较时，会发生 n-1 次比较，例如 Lomuto 分区方案。

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

Hoare 分区方案进行更多比较，但通常它比 Lomuto 进行更少的交换。

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

在我的基准测试中，我发现 Lomuto 对于几乎没有重复的伪随机数据稍微快一些。如果重复的数量很大，Hoare 更快，并且在所有相等元素的情况下，它是 Lomuto 的最坏情况 O(n^2) 和 Hoare 的最佳情况 O(n log2(n))。