快速排序

约 1327 个字 65 行代码 预计阅读时间 5 分钟

比较排序中，实践中最快的已知算法。

它的最坏情形的性能为 $O(n^2)$，但稍加努力就可避免这种情形。

原理

快速排序也是一种分治的递归算法，将数组 $S$ 排序的基本算法由下列简单的四步组成

1. 如果 $S$ 中元素个数是 $0$ 或 $1$，则返回
2. 取 $S$ 中任意元素 $v$,称之为枢纽元(pivot)
3. 将 $S-{v}$($S$ 中其余元素)分成两个不相交的集合：$S_1=\{x\in S-\{v\}|x\le v\}$ 和 $S_2=\{x\in S-\{v\}|x\ge v\}$
4. 返回 $\{quicksort(S_1)$ 后，继而 $v$，继而 $quicksort(S_2)\}$

由于对那些等于枢纽元的元素的处理，第3步分割的描述不是唯一的，因此这就成了一个设计上的决策。

直观地看，我们希望把等于枢纽元的大约一半的关键字分到 $S_1$ 中，而另外的一半分到 $S_2$ 中，具体的实现后面再解释

算法的成立应该是显然的，但是不清楚为什么比归并排序快，快速排序并不保证子问题大小相近，这是个潜在的隐患。

快排更快的原因在于，第3步的分割实际上是在适当的位置进行而且非常有效，它的高效大大弥补了大小不等的递归调用的缺憾。

迄今为止，对快排的描述缺少许多细节，对于第2，3步有许多方法，这里介绍的方法是大量分析和经验研究的结果，哪怕是对该方法最微小的偏差，都可能引起意想不到的不良结果

选取枢纽元

无论选择哪个元素作为枢纽元都能完成排序工作，但有些选择更优

三数中值分割法

枢纽元的最好选择是数组的中值，但这不好算，且会明显减慢快排的速度。

对中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元。

事实上，由于输入也是随机的，所以枢纽元的随机选取并没有多大帮助。

因此一般做法是使用左端，右端，中心位置的三个元素的中值作为枢纽元

三数中值分割法消除了有序输入的坏情形，减少了快速排序约 $5\%$ 的运行时间

分割策略

一种已知的安全的做法，第一步将枢纽元和最后一个元素交换，使得枢纽元离开将要被分割的数据段。

$i$ 从第一个元素开始，$j$ 从倒数第二个元素开始。

暂时假设所有元素互异，后面再着重考虑重复元素该怎么办。

分割阶段要做的就是把，相对于枢纽元，小元素移到数组的左边，而大元素移到数组的右边

当 $i<j$ 时，将 $i$ 右移，移过那些小元素；并将 $j$ 左移，移过那些大元素。

当 $i,j$ 停止时，$i$ 指向一个大元素，而 $j$ 指向一个小元素，如果 $i<j$ ，那么交换这两个元素

重复上述过程直至 $i\ge j$

分割的最后一步是将枢纽元与 $i$ 指向的元素交换

这样分割完之后的效果是，在位置 $P<i$ 的每一个元素都是小元素，反之都是大元素

现在考虑如何处理等于枢纽元的关键字。

$i,j$ 碰到等于枢纽元的关键字是否应该停止。

直观地看，他们应该要么都停止，要么都不停止。否则分割会偏向一方。

为了搞清楚怎么办更好，考虑全部关键字都相等的情况。

假如都停止，那么程序会在相同的元素间交换多次，从结果上看没有任何改变。但是，当分割停止时，i正好在中间，这样，子问题大小就非常均衡，根据归并排序的复杂度分析，这样做的复杂度是 $O(n\log_2 n)$

假如都不停止，那么 $i$ 会停止在倒数第二个位置，这样，子问题大小极不均衡，事实上，复杂度是 $O(n^2)$

因此我们发现，在相同元素间交换看似没有改变结果，但是有助于均衡地分割子问题，提高算法运行速度

小数组

对于很小的数组 $(n\le 20)$，快速排序不如插入排序好。而且因为快速排序是递归的，这样的情形还经常发生。

一个好的解决方法是对于小的数组使用插入排序，大的数组使用快速排序。使用这种方法相比始终使用快速排序，大约节省 $15\%$ 时间。

一种好的截止范围是 $(n\le 10)$，根据大量测试得来

实现

int Median3(int l,int r)
{
    int mid=(l+r)/2;
    if(a[l]>a[mid])
        swap(a[l],a[mid]);
    if(a[l]>a[r])
        swap(a[l],a[r]);
    if(a[mid]>a[r])
        swap(a[mid],a[r]);
    swap(a[mid],a[r-1]);
    return a[r-1];
}
void Qsort(int l,int r)
{
    if(r-l+1<=10)
    {
        InsertionSort(l,r);
        return;
    }
    int Pivot=Median3(l,r);
    int i=l,j=r-1;
    for(;;)
    {
        while(a[++i]<Pivot){}
        while(a[--j]>Pivot){}
        if(i<j)
            swap(a[i],a[j]);
        else
            break;
    }
    swap(a[i],a[r-1]);
    Qsort(l,i-1);
    Qsort(i+1,r);
}
void QuickSort()
{
    Qsort(0,n-1);
}

时间复杂度分析

为了方便分析快排的复杂度，这里讨论时不涉及三数中值分割法和小数组换插入排序

和归并排序类似，取 $T(0)=T(1)=1$，快排运行时间等于两个递归调用的运行时间加上分割时间（枢纽元这里随机选取，仅花费常数时间），得到如下式子

$$T(n)=T(i)+T(n-i-1)+cn$$

$c$ 是分割的常数

其中 $i$ 是 $S_1$ 的元素个数

---

对于平均情形，假设对于 $S_1$ 的每个元素个数都是等可能的，因此概率都是 $\frac 1n$

上式变成

$$T(n)=\frac 2n[\sum\limits_{j=0}^{n-1}T(j)]+cN$$

$$nT(n)=2[\sum\limits_{j=0}^{n-1}T(j)]+cN^2$$

$$(n-1)T(n-1)=2[\sum\limits_{j=0}^{n-2}T(j)]+c(N-1)^2$$

$$nT(n)-(n-1)T(n-1)=2T(n-1)+2cn-c$$

$c$ 是常数，和复杂度无关了，所以上式变为

$$nT(n)-(n-1)T(n-1)=2T(n-1)+2cn$$

$$nT(n)=(n+1)T(n-1)+2cn$$

$$\frac{T(n)}{n+1}=\frac{T(n-1)}n+\frac{2c}{n+1}$$

$$\frac{T(n-1)}{n}=\frac{T(n-2)}{n-1}+\frac{2c}{n}$$

$$...$$

$$\frac{T(2)}{3}=\frac{T(1)}{2}+\frac{2c}{3}$$

$$\frac{T(n)}{n+1}=\frac{T(1)}2+2c\sum\limits_{i=3}^{n+1}\frac 1i$$

等式右边和大约 $\log_e(n+1)+\gamma-\frac 32$，其中 $\gamma\approx0.577$ 叫作欧拉常数，于是

$$\frac{T(n)}{n+1}=O(\log n)$$

$$T(n)=O(n\log n)$$

快速选择

void nth_element<_RAIter>(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);

该函数可以从某个序列中 $O(n)$ 找到第 k 小的元素 Val，并将 Val 移动到序列中第 k 的位置处。不仅如此，整个序列经过 nth_element() 函数处理后，所有位于 k 之前的元素都比 Val 小，所有位于 k 之后的元素都比 Val 大，在默认的升序排序规则（std::less）的条件下

快速排序在算法竞赛中常见的应用

观察出目标具有某种性质，使用std::sort排序，然后贪心

std::sort的使用

C++的库的一个函数，其底层是快速排序

重载不等号

返回值类型都是 bool

如果想排升序就重载小于号，想排降序就重载大于号

对于等于的情况一定要返回false，笔者在暑假牛客多校踩了5h的坑

sort默认是升序，若想降序需使用 greater()

const int N=10;
struct edge
{
    int v,w;
    bool operator<(const edge t)const
    {
        return w<t.w;
    }
    bool operator>(const edge t)const
    {
        return w>t.w;
    }
}a[N];
sort(a,a+n);
sort(a,a+n,greater<edge>());

自定义比较大小函数

按照自定义函数，返回true的排在前面，否则排在后面

const int N=10;
struct edge
{
    int v,w;
}a[N];
bool cmp(edge x,edge y)
{
    return x.w<y.w;
}
sort(a,a+n,cmp);