关于快速排序
  • 板块学术版
  • 楼主sfmmdm
  • 当前回复13
  • 已保存回复13
  • 发布时间2020/8/26 12:11
  • 上次更新2023/11/6 19:17:48
查看原帖
关于快速排序
82124
sfmmdm楼主2020/8/26 12:11

双指针快排的实现中有这样两行:

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);
}
2020/8/26 12:11
加载中...