快速排序边界分析
void quick_sort(int a[], int l, int r)
{
if(l >= r) return;
int i = l - 1, j = r + 1, x = a[l + r + 1 >> 1];
while(i < j)
{
do i++; while(a[i] < x);
do j--; while(a[j] > x);
if(i < j) swap(a[i], a[j]);
}
quick_sort(a, l, i - 1), quick_sort(a, i, r);
}
快速排序挺简单的,但是边界分析让我有点头痛,学习了大佬的题解之后有以下总结(搬运:
- 进行边界分析是为了避免分治时出现被分为
0
和n
的情况,造成无限分治内存超限问题。 - 若以
j
为分界点,对于quick_sort(q, l, j), quick_sort(q, j + 1, r)
,j
有可能取l
~r
的任何一个值,若j
取l
,则quick_sort(q, l + 1, r)
执行时会产生分割,不会出现0
和n
的情况;若j
取r
,则quick_sort(q, l, r)
执行时会分割为n
,会导致无限分治。本条结论:若在递归分治前保持j = r
,那么就会出现无限分治的情况 - 所以只要在进入分治前不要让
j
取到r
就可以了。那什么时候会取到r
呢?初始化完毕时,j
的值为r + 1
,当执行过一次do j--; while(q[j] > x)
后,j
变为r
,并且恰好在此之后j
都不会发生改变,即do j--; while(q[j] > x)
只会执行一次,如果保持j = r
不变的话,那么i
会在此之前一直自增到i = r
,此时j = r; i = r
不满足i < j
循环结束,此时,整个while(i < j) {}
循环只进行了1轮,分治,从而导致分治出了0
和n
两个情况。本条结论:若要在递归分治前保持j = r
,那么while(i < j) {}
只能执行一次 - 现在把焦点转移到x的取值上,第3点说到,若出现无限分治问题,
i
会一直自增到i = r
,若出现这种情况,那么x
的取值一定是q[r]
,因为如果x
的值不为q[r]
,那么一定会在x
处存在q[i] == x
,而q[i] == x
会导致i
自增暂时停止,那么就会往下执行,执行do j--;
,判断后进入第二轮while(i < j) {}
循环,进入第二轮循环会使j
自减至少两次,而他的初值为r + 1
,也就是说,j
的值不会一直保持在j = r
上,也就不会导致无限分治。本条结论:若x
的取值不为q[r]
,那么while(i < j) {}
会至少执行两次,因此在进行递归分治前,j
的值是一定小于r
的。 l + r >> 1
的值一定是小于r
的,不会取到r
,而l + r + 1 >> 1
的值一定是大于l
的,不会取到l
所以综合2、3、4、5的结论就得出了若以j
为分界点,x
取q[l + r >> 1]
,此时不会出现无限分治的情况;若以i
为分界点,x
取q[l + r + 1 >> 1]
,此时不会出现无限分治的情况
(写的第一篇文章,太啰嗦了,排版也不好
666
int a[]不是定义在外边的吗,为什么用的时候还要传
nb
泰库拉
我逐渐理解一切。。。
终于找到了用i时MLE的原因了,谢谢大佬!!!
大佬太强了,讲的真的细节
就是这个边界搞不懂,裂开了