关于快排的一些思考(如有错误,欢迎指正,我将深刻反思)
可认为,最左边和最右边的两段是已经处理完的了,大于x的必须排到右边,等于x的可以排到右边,这两种情况我们都叫能排到右边
同理,小于x的必须排到左边,等于x的可以排到左边,这两种情况我们都叫能
排到左边
不断交换元素的过程可看出“左边处理区域”和“右边处理完区域”壮大的过程
(这样理解或许能更好体会算法的正确性)
i指向“能排到右边的”,而不仅仅是“必须排到右边的”
j指向“能排到左边的”,而不仅仅是“必须排到左边的”
这样是正确的,否则存在这样一种棘手的情况:
右边j找到必须排到左边的,左边的i没找到必须排到右边的,而只有不必须但可以排到右边的,这样没有元素跟j指向的元素换了
比如 3 3 3 1 5 4
x为l+r/2,即3
(如果错误地认为只有大于x时i才能停下)则j最终指向1,i指向5,1没被换到3左边,这没达到目的。
对于边界情况
由于最终一定是i==j(若中间待处理的剩俩元素,此时i=j-1,while里一定i++,j–只执行一个,因为其中一个元素是x;若剩仨则可能俩都执行)
i-1 i j+1 是这样的关系,三个及以上元素你选i-1,i分界,或者j,j+1分界都可以
j
但是如果就俩,可能导致一边没元素,一边俩。然后俩的还是俩,和刚才一样的情况,死循环
void quick_sort(int q[], int l, int r)
{
if (l == r) return;//写成l==r 和l>=r是一样的,因为l不会大于r
int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}