algorithm - QuickSort Dijkstra 三向分区 : why the extra swapping?

Question

给定这里的算法，看看 i 在“X”的场景，会发生以下情况:

场景: i -> "X", "X"> "P"

1. swap("X", "Z"), gt--;   // the value at i is now "Z", which is still > "P"
2. swap("Z", "Y"), gt--;   // the value at i is now "Y", which is still > "P"
3. swap("Y", "C"), gt--;    // Now we finally get a value at i "C" which is < "P"
// Now we can swap values at i and lt, and increrement them
4. swap("P", "C"), i++, lt++;

为什么我们不直接递减 gt 直到 gt 指向一个小于 lt 处的值(本例中为“P”)的值，然后我们将这个值与 i 处的值交换。这将节省交换操作。

因此，如果我们针对上述场景执行此操作，我们将执行:

1. gt--
2. gt--
3. swap("X", "C"), gt--;   
// Now we can swap values at i and lt, and increrement them
4. swap("P", "C"), i++, lt++;

算法是否需要这种过度交换？它会以某种方式提高性能吗？如果它确实提高了性能，那又如何呢？

如果它不影响性能，请给出适当的解释或证明为什么它不影响性能。

此外，我提到的第二种方法会以任何方式影响性能吗？请解释原因。

附言上面使用的“影响性能”意味着提高/降低性能。

Answer 1

你是对的，额外的交换操作不是必需的，这里的算法最适合清晰度，而不是性能。参见 Quick Sort (3 Way Partition) 的讨论.

在Quicksort is optimal由 Robert Sedgewich 自己提出，他有一个不同的方法，使用更少的交换操作，但你可以想象它也需要更多的代码，并且不如演示中的算法清晰。