在做快排的题目时,使用y总介绍的模板方法,使用do … while();的方法,
int x = f[st + ed >> 1];
while (l < r) {
do l++; while (f[l] < x);
do r--; while (f[r] > x);
if(l < r) swap(f[l], f[r]);
}
quickSort(f, st, r);
quickSort(f, r + 1, ed);
想了下能不能l, r都可以作为边界,那能不能使用l 而不使用r呢,就是上面的递归替换为:
quickSort(f, st, l);
quickSort(f, l + 1, ed);
发现有些数据是通过不了的,比如对于这一串数据 49 59 88 37 98 97 68 54 31 3
输出的结果总是错误的,后来跟踪一下递归的过程发现,如下,59
这个值在进行第二轮递归时,l = 1
,此时是错误的。因为我们每次递归的条件:左半部分 <= x && 右半部分 >= x
,很明显 l 可能在最后 while出来时存在 > x的情况,使用 r 才是符合要求的
=======98========
l: -1 r: 10
l: 4 r: 9
49 59 88 37 3 97 68 54 31 98
l: 9 r: 8
49 59 88 37 3 97 68 54 31 98
=======3========
l: -1 r: 10
l: 0 r: 4
3 59 88 37 49 97 68 54 31 98
l: 1 r: 0
3 59 88 37 49 97 68 54 31 98
=======3========
l: -1 r: 2
l: 0 r: 0
3 59 88 37 49 97 68 54 31 98
感谢分享~写得很清晰~
第一段代码里这一段好像写错了?
我猜可能是想写这个?
所以说边界要么用[st, r], [r + 1, ed], 或者也可以用l,但是要往左取,就是[st, l - 1], [l, ed],好像也刚好对应了y总给的两种模板~
感谢指出错误,已修改,后面这种 l - 1的在这种情况下可能会遇到边界问题。具体的这个
r
,l
的写法和哨兵位置的计算有关,有点类似二分那个模板的意思嗯嗯,确实。如果是用l - 1的话,取pivot的时候要上取整,即(l + r + 1) >> 1