双指针快排的实现中有这样两行:
while(a[j]>=t&&i<j) j--;
while(a[i]<=t&&i<j) i++;
为什么这两行不能互换?
还有,快排不是要把基准值放到第一位吗?为什么有些实现方式不用交换?
而且这种实现方式中,可以先动 i 再动 j,为什么?
附上我经常使用的实现方式:
void qsort(int l,int r) {
int i=l,j=r;
if(i>=j) return;
int mid=(l+r)>>1;
if(a[l]>a[mid]) swap(a[mid],a[l]);
if(a[mid]<=a[r]) swap(a[l],a[mid]);
int t=a[l];
while(i<j) {
while(a[j]>=t&&i<j) j--;
while(a[i]<=t&&i<j) i++;
swap(a[i],a[j]);
}
swap(a[l],a[i]);
qsort(l,i-1);
qsort(i+1,r);
}