原题链接
y总：注意本题数据已加强，划分中点取左端点或右端点时会超时，改成取中点或者随机值即可。
-
啊哈算法
左端点定为temp，右边先开始走，当左右哨兵相遇时，保证在i左边的数都<=temp，右边的数都>=temp，temp归位，因为是i==j取到的值，所以l>r时返回
//最开始接触的快排版本，不用考虑边界递归问题，很简单好懂，写法也不容易混淆，但过不了这题
int a[MAX],n;
void quick_sort(int l,int r)
{
if(l>r)
return ;
int i=l,j=r,temp=a[l];
while(i!=j)
{
while(a[j]>=temp&&i<j)
j--;
while(a[i]<=temp&&i<j)
i++;
if(i<j)
swap(a[i],a[j]);
}
a[l]=a[i];
a[i]=temp;
quick_sort(l,i-1);
quick_sort(i+1,r);
}
-
学习进阶
先把左右两指针往中间移动，然后再判断
递归情况[l,j][j+1,r]
x取中间值a[(l+r)>>1]
void quick_sort(int l,int r)
{
if(l>=r)
return ;
int i=l-1,j=r+1,x=a[(l+r)>>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(l,j);
quick_sort(j+1,r);
}
这种情况，[l,j][j+1,r]或[l,j-1][j,r]都可取
只有[l,j][j+1,r]可取
- 递归j
一定不能取右边界，否则会边界死循环
x=a[l]或x=a[(l+r)/2],对应[l,j],[j+1,r]
- 递归i
一定不能取到左边界，否则边界会死循环
x=a[r]或x=a[(l+r)/2+1],对应[l,i-1],[i,r]
void quick_sort(int l,int r)
{
if(l>=r)
return ;
int i=l-1,j=r+1,x=a[(l+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(l,j);// quick_sort(l,i-1);
quick_sort(j+1,r);//quick_sort(i,r);
}
