快速排序的Dijkstra 3路分区：为什么额外的交换？ [英] QuickSort Dijkstra 3-Way Partitioning: why the extra swapping?
问题描述
这里给出的算法，看场景，我是在X，将出现以下情况：
Given the algorithm here, look at the scenario where i is at "X", the following happens:
方案： I - >X，X - >P
Scenario: 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在这个值用值。这将节省交换操作。
Why don't we just decrement gt until gt points to a value that is < the value at lt ("P" in this case), then we swap this value with the value at i. This will save swapping operations.
因此，如果我们做到这一点的情况下上面提到的，我们会做的：
So if we do that for the scenario mentioned above, we'll do:
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++;
时该算法所需的这种过度交换？它确实提高在某些方面的表现？ 如果它确实提高性能，怎么样？
Is this excessive swapping needed for the algorithm? does it improve performance in some way? If it does improve performance, how?
如果它不会影响性能，请给一个适当的解释或证明，为什么这不会影响性能。
If it doesn't affect performance, please give a proper explanation or a proof as to why this it does not affect performance.
另外，我会提到的第二个方法以任何方式影响性能？请解释原因。
Also, would the second method I mentioned affect performance in any way? please explain why.
P.S。上面使用意味着要么提高/降低性能影响性能。
P.S. "Affect performance" as used above means either improve/degrade performance.
推荐答案
你是对的，额外的交换操作是没有必要的，这种算法在这里是最好的清晰度，而不是性能。请参见快速排序（3路分区）的讨论。
You are right, the extra swap operations are not necessary, this algorithm here is best for clarity, but not for performance. See the discussion of Quick Sort (3 Way Partition).
在快速排序是由罗伯特·Sedgewich自己最佳，他有不同的方法使用更少的交换操作，但你可以想象它也需要更多的code，并且比算法演示不太清楚。
In Quicksort is optimal by Robert Sedgewich himself, he has a different approach that uses much less swap operation, but you can imagine it also needs more code, and is less clear than the algorithm in the demo.
这篇关于快速排序的Dijkstra 3路分区：为什么额外的交换？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
