快速排序中的特殊位置
-
快排正常模板
void quick_sort(int q[],int l,int r)
{
if(l>=r) return;
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);
}
-
中间值的设置选择
-
如果中间值设置为 mid = l + r >> 1;
void quick_sort(int q[],int l,int r)
{
if(l>=r) return;
int i = l-1,j = r+1,mid = l+r >>1;
while(i<j)
{
do i++;while(q[i]<q[mid]);
do j--;while(q[j]>q[mid]);
if(i<j) swap(q[i],q[j]);
}
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}
就会出现边界问题,例如跑样本
49 59 88 37 98 97 68 54 31 3
输出
3 49 59 37 88 31 54 68 97 98
标准答案
3 31 37 49 54 59 68 88 97 98
