algorithm - 科门快速排序

Question

在 Introduction to Algorithms 一书中，Quicksort 一章中描述的快速排序算法没有使用 Hoare-Partitioning。

谁能告诉我这种方法相对于流行的 hoare 分区的优势。还是只是作者的选择问题？

Answer 1

第二版中的注释（自第一版以来的变更日志）说（强调我的）：

用于快速排序（第 7.1 节）和预期线性时间顺序统计算法（第 9.2 节）的分区方法是不同的。我们现在使用 Lomuto 开发的方法，该方法与指标随机变量一起， 可以进行更简单的分析。由于 Hoare 的原因，第一版中的方法在第 7 章中出现了问题。