快排中,最终的i,j指针的指向是确定的。
i指针之前的数(不包括i本身),一定是严格小于 x 的
j指针之后的数(不包括j本身),一定是严格大于 x 的
以j指针为分界时,可以:
int x = a[l+r>>1];
...
quick_sort(l,j); //[l,j] 满足小于等于x
quick_sort(j+1,r); //[j+1,r] 满足大于x
以i指针为分界时,可以:
int x = a[l+r+1>>1]; //注意此处的+1,类似二分中求右端点的处理
...
quick_sort(l,i-1); // [l,i-1] 满足小于x
quick_sort(i,r); // [i,r] 满足大于等于x