快速排序

luckydrawbox · 2021-08-28 23:30:28 · 个人记录

对一个下标在 [l,r] 间的数组 a 排序。

一般可以这么调用：ksort(a,1,n)，把 a_{1\sim n} 排好序。

void ksort(int *a,int l,int r){
    int i=l,j=r,f=a[(l+r)/2];
    do{
        while(a[i]<f)
            i++;
        while(a[j]>f)
            j--;
        if(i<=j)
            swap(a[i++],a[j--]);
    }while(i<=j);
    if(l<j)
        ksort(a,l,j);
    if(i<r)
        ksort(a,i,r);
}

平均时间复杂度 O(n\log n)。