快速排序¶

主算法¶

void quick_sort(const int a*,int l,int r){
    if(l<r){
        int m=partition(a,l,r);
        quick_sort(a,l,m-1);
        quick_sort(a,m+1,r);
    }
    return;
}

划分¶

算法¶

Lomuto 划分¶

左起放置比 \(\mathrm{pivot}\) 小的元素

正确性证明如下：

归纳假设：\(i\) 左边的元素都 \(<\mathrm{pivot}\) ，\([\,i\,,\,j\,)\) 内的元素都大于 \(\mathrm{pivot}\)

归纳奠基：循环未开始时，\(i\) 左边没有元素，\([\,i\,,\,j\,)\) 也没有元素，假设成立

归纳递推：循环中，分以下两种情况：

遍历指针 \(j\) 指向的元素 \(x_j≥\mathrm{pivot}\) ，继续遍历（ \(j\) 右移），假设仍成立

遍历指针 \(j\) 指向的元素 \(x_j<\mathrm{pivot}\) ，将其放到 \(i\) 左边（交换 \(x_i\ ,\ x_j\) ，边界 \(i\) 右移），继续遍历（ \(j\) 右移），则假设仍成立

结论：当 \(L\not <R\) 循环结束时，归纳假设成立

代码如下：

int partition(int* a,int l,int r){
    int pivot=a[r];
    int i,j; 
    for(i=j=l;j<r;j++){
        if(a[j]<pivot){
            swap(a[j],a[i++]);
        }
    }
    swap(a[i],a[r]);
    return i;
}

相向双指针划分¶

正确性证明如下：

归纳假设：左指针 \(L\) 左边的元素都 \(≤\mathrm{pivot}\) ，右指针 \(R\) 右边的元素都 \(>\mathrm{pivot}\)

归纳奠基：循环未开始时，\(L\) 左边和 \(R\) 右边都没有元素，假设成立

归纳递推：循环中，分以下两种情况：

左指针 \(L\) 指向的元素 \(x_L≤\mathrm{pivot}\) ，或右指针 \(R\) 指向的元素 \(x_R>\mathrm{pivot}\) ，那么可以继续相向移动左（右）指针，使假设仍成立

左指针 \(L\) 指向的元素 \(x_L>\mathrm{pivot}\) ，且右指针 \(R\) 指向的元素 \(x_R≤\mathrm{pivot}\) ，则交换 \(x_L\ ,\ x_R\) ，转化为上面的情况，假设仍成立

结论：当 \(L\not <R\) 结束循环时，归纳假设成立

代码如下：

// 本人原创
int partition(int* a,int l,int r){
    int pivot=a[l];
    int L=l+1,R=r;
    for(int tot=0;tot<r-l;){
    // 左、右指针移动总次数 tot<r-l，则两指针一定没有交错，也没有越过左右边界
        bool is=true;
        if(a[L]<=pivot){
            L++;
            tot++;
            is=false;
        }
        if(a[R]>pivot){
            R--;
            tot++;
            is=false;
        }
        if(is)swap(a[L],a[R]); // 如果两个指针都无法移动，则交换
    }
    swap(a[l],a[R]);
    return R;
}

// 自算法引论伪代码
int partition(int* a,int l,int r){
    int pivot=a[l];
    int L=l,R=r;
    while(L<R){
        while(a[L]<=pivot && L<=r){
            L++;
        }
        while(a[R]>pivot && R>=l){
            R--;
        }
        if(L<R) swap(a[L],a[R]);
    }
    swap(a[l],a[R]);
    return R;
}

Warning

第二种实现并没有按证明一步一步移动指针，一个指针一次可能移动多步，这使算法的实现多了很多坑，如左右指针移动的先后顺序必须严格保证，否则会出错。建议考试时要不把 Hoare 划分背下来，要不就写 Lomuto 划分，既简单，效率也不错。

枢值的选取¶

如果划分后左右子列长度总是相等，由递归关系

\[T(n)=2\,\Big(\frac{n}2\Big)+O(n)\]

和终止条件

\[T(2)=1\]

容易知道，此时快速排序的时间复杂度可以达到

\[T(n)=O(n\log n)\]

如果每次划分后某侧子列长度为 0，则快速排序的时间复杂度为最坏的 \(O(n^2)\)

可见枢值 \(\mathrm{pivot}\) 的选取很大程度上影响着快速排序的性能，为避免最坏情况的出现，有以下两种常见的枢值选取方式

三数取中¶

虽然使用快速选择算法可以 \(O(n)\) 地查找中值，但完全没有必要，这里我们使用第一个、最后一个、中间三个数的中数（即第二大的）作为枢值即可

随机选取¶

更好的方法是从序列中随机取数作为枢值

小规模数据改用插入排序¶

快速排序适合长序列，对短序列来说性能反而不如插入排序这种简单排序

因此，我们可以在序列被划分到规模小于一定值时不再继续划分，而是调用插入排序

三路划分¶

如果序列中有大量重复元素，我们不妨在划分时将数组分为 \(>\mathrm{pivot}\) ，\(=\mathrm{pivot}\) ，\(<\mathrm{pivot}\) 三部分，继续划分时只考虑 \(>\mathrm{pivot}\) ，\(<\mathrm{pivot}\) 两部分，而不考虑 \(=\mathrm{pivot}\) 的子列，这样就缩小了问题的规模

实现¶

类似 Lomuto 划分，只不过不仅左起放置 \(<\mathrm{pivot}\) 的元素，还右起放置 \(>\mathrm{pivot}\) 的元素

void three_way_quicksort(int* a,int l,int r){
    if(l<r){
        int pivot=a[r];
        int j=l; // 遍历指针
        int L=l,R=r-1; // 边界指针
        while(j<=R){
            if(a[j]<pivot){
                swap(a[j++],a[L++]);
            }else if(a[j]>pivot){
                swap(a[j],a[R--]); // j 不右移，因为换过来的 a[R] 也要比
            }else{
                j++;
            }
        }
        swap(a[r],a[j]);
        three_way_quicksort(a,l,L-1);
        three_way_quicksort(a,R+2,r); // 坑点
    }
    return;
}

Warning

如果用函数实现三路划分，势必要返回两个参数（中间 \(=\mathrm{pivot}\) 子列的左右端点），所以像上面这样把划分和排序放在一个函数里会比较方便

多线程快排¶

鉴于本人太菜，还不会用 C++ 写多线程，下面都用 Python 实现

def quick_sort(s):
    # 嵌套定义函数
    def inner_quick_sort(s,l,r):
        if l<r:
            leq=l
            for i in range(l+1,r+1):
                if s[i]<s[l]:
                    leq+=1
                    # Python 交换数组元素的方式
                    s[i],s[leq]=s[leq],s[i]
            s[l],s[leq]=s[leq],s[l]
            inner_quick_sort(s,l,leq-1)
            inner_quick_sort(s,leq+1,r)
        return
    inner_quick_sort(s,0,len(s)-1)

拓展¶

快速选择算法¶

借鉴快速排序划分的思想，可以设计出在 \(O(n)\) 复杂度找出 第 \(k\) 大元素 的算法 —— 快速选择算法

int quick_kth(int a[], int k, int l, int r){
    // 子列中只有一个元素，则这个元素就是要找的
    if(l==r) return a[l];
    // 以 l 为枢值, Lomuto 划分
    int leq=l;
    for(int i=l+1; i<=r; i++){
        if(a[i]<a[l])
            std::swap(a[++leq], a[i]);
    }
    std::swap(a[l], a[leq]);
    // 枢值就是要找的
    if(leq+1-l==k) return a[leq];
    // 在左子列中以 原排名 继续搜索
    if(leq+1-l>k) return quick_kth(a, k, l, leq-1);
    // 在右子列中以 原排名-左子列元素个数-1(枢值) 继续搜索
    if(leq+1-l<k) return quick_kth(a, k-(leq-l+1), leq+1, r);
}