双路排序问题

Question

为什么这里写成i >= j 会排序失败

while(true){
	while...;

	while...;

	if( i > j )
      break;
}

Answer 1

liuyubobobo 2018-09-28 16:10:53

我测试了一下，这个问题我以前的回答不对。if(i >= j) break; 掉应该没有问题。如果你排序失败，应该是代码其他地方有问题？

因为如果在 if 里，i == j，说明 arr[i] >= v，同时 arr[j] <= v，只有这样，才能分别从上面两个 while 跳出来。

而此时 i == j，所以，此时，arr[i] == arr[j] == v。那么这个值放在这里是没问题，整个数组依然满足被分成了两半，一半 <= v；另一半 >= v。

我将我原来的回答也放在了下面。原来的回答我说“arr[j]可能是大于标定点的，却被我们置换到了左边。”，实际上这是不可能的，因为如果 arr[j] 还大于标定点，在上面的 while 循环中就出不来。

抱歉！

==================

以课程实现代码为例：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/03-Sorting-Advance/Course%20Code%20(C%2B%2B)/07-Quick-Sort-Deal-With-Identical-Keys/main.cpp

注意，我们的i和j的定义，在41行注释中：// arr[l+1...i) <= v; arr(j...r] >= v

如果i==j的时候就break，对于arr[i]位置的元素（此时，也是arr[j]位置的元素），我们还没有看过，我们不知道这个元素和我们的标定点之间的大小关系。我们没有把他正确的分到左边或者右边。这将使得跳出循环后，65行执行的swap可能不正确。因为此时的arr[j]可能是大于标定点的，却被我们置换到了左边。

加油！：）

• 提问者 慕工程8551597 #1

  非常感谢！

• 提问者 慕工程8551597 #2

  终于理解了，上面两个while结束后，新的i和j的位置还没被处理过