快速排序笔记

一、quick_sort方法中如果 i=l,j=r 会死循环的分析

1、示例代码

void quick_sort(int a[],int l,int r){if(l>=r) return;int i=l,j=r; //此处设置会导致死循环int x = num[(l+r)>>1];while(i<j){while(a[++i] <x); //死循环的地方while(a[--j] >x);if(i<j) swap(a[i],a[j]);}quick_sort(a,l,j);quick_sort(a,j+1,r);
}

2、代码分析

因为数组a默认值都是，i的坐标越过了选中的数x ，并且x往后的数都小于0或者没有明确赋值（此种情况为0）此后a[i]的值都会小于x,导致死循环。而
while(a[--j] >x); 就不会导致因为j往左移终究会变成没有明确赋值的0，所以循环会结束。

3、示例

假如就两个数 98 97，i=1(值97，i坐标往右移动，值变成0，始终小于选出来的数98，导致死循环)

4、心得

算法当中有很多默认值的地方，比如此处的数组a的未明确下标的值都为0，为一个隐含条件，可以帮忙判断是否发生死循环。

二、无限划分的分析

1、重要结论

当以i划分区间，选数不能选到左边界，则a[x] = a[(L+R+1)>>1]
当以j划分区间，选数不能选到右边界，则a[x]=a[(L+R)>>1]

2、逻辑分析

假设选的数是a[x] ,退出循环时，a[l] …a[i-1] 都是a[x];a[j+1]…a[r] 都是>x，a[j]<a[x][x]，a[i]>。

3、示例

以3 1 2 5 4 这个五个数排序为例：

4、心得

退出循环时的条件判断，有些退出循环时的条件很明确，比如以i划分，选数为L时，退出循环时i=L,但是j就不确定，只能是比L小的某一个位置。对于明确的位置是算法中一些重要判断的条件。

​