快速排序分区算法——为什么与循环外的主元值交换？

Question

我正在看 CLRS 算法简介中的快速排序算法 https://dl.ebooksworld.ir/books/Introduction.to.Algorithms.4th.Leiserson.Stein.Rivest.Cormen.MIT.Press.9780262046305.EBooksWorld .ir.pdf

在第184页，它显示了分区算法，为方便起见，粘贴在下面：

我已经很多年没有看过这个了，但现在我不明白为什么我们需要第 7 行，而不是让循环从

j = p

到

j = r

，然后

return i

。如图所示这样做是否会带来一些性能提升？

Answer 1

这是 Lomuto 分区方案的标志。

执行交换的原因是将枢轴元素（它被放在一边并且在循环中没有被访问）放置在两个分区之间。这有一个优点，因为这个枢轴值现在位于该分区中的“最终”位置：它永远不必再次移动！通过返回该主元值的索引，调用者可以将其从将传递给更深层次递归调用的较小分区中排除。