双路快排partition中while(true)中止的条件if(i>j)

Question

if( i > j )
   break;

为什么不是 i >= j 呢？

i >= j

Answer 1

qq_漫笔_0 2021-09-15 19:57:15

当 i >= j 时，性能会有一点提升，可有可无。

1.while (i <= r && arr[i] < v) i++ 过滤出的元素是 arr[i] >= v

2.while (j >= l + 1 && arr[j] > v) j-- 过滤出的元素是 arr[j] <= v

当 i == j 时,说明指向同一元素，同时满足 1，2 说明 arr[i] == arr[j] == v

如下序列：

  3 1 5 3 2 4 

  3 4 2 3 5 1

  3 4 5 3 2 1

使用  i >= j 时 break，i == j，跳出循环，此时 l =0，j=3, i=3，arr[j] 和 arr[l] 发生标定点置换操作（这里也可省略）

使用 i > j 时 break, i == j，继续循环（多了一轮循环判断），直到 l=0，j=2，i=4，此时 break，跳出循环，arr[j] 和 arr[l] 发生标定点置换操作

Answer 2

liuyubobobo 2020-11-08 11:48:11

i >= j 就 break 也是正确的：）

继续加油：）