数据结构与算法复习——3、平均分析入门

3、平均分析入门——快速排序分析

　　这篇我们只分析快速排序，作为平均分析的经典例子。在此之后，我们暂时停下算法分析的学习，转而去复习堆。当我们复习到二项队列和斜堆之后，我们再来学习摊还分析。

一、快速排序简单介绍

　　快速排序是一个与归并排序同样经典的分治排序。归并排序的思想在于“先分治再合并”，快速排序相反，是“先分类再分治”。至于为什么叫“快速”，则是因为它只需交换操作的优越性以及长时间发展以来对它的优化造成它确实非常快。

快速排序的具体思想是这样的：

如果数组$S$分为了左右两部分$S_1$、$S_2$，使得任意$S_1$的元素都小于$S_2$的元素，则我们只需要分别排序$S_1$和$S_2$就好了。快速排序时，先把数组变成刚刚说的这个模样，然后分治排序。若遇到$|S| leq 1$，则是递归的基本情况，无需排序则有序，此时停止递归返回。

当然，真正操作的时候，我们需要知道到底$S_1$和$S_2$的分界线是什么（一个特殊的例子，若$S$已经升序排列好，则任意两部分都可以是$S_1$和$S_2$），这就是快速排序的枢纽元的概念，选取枢纽元的策略极大地影响了快速排序的时间复杂度。

默认我们要进行升序排列，则选取枢纽元之后，将它交换到数组的最后一个位置（或者第一个，这样是为了让枢纽元不参与后面的分割），在剩余的部分里，令一个指针从左开始，向右寻找首个大于等于枢纽元的数后停止，令另一个指针从右开始向左寻找首个小于等于枢纽元的数后停止，交换两者的值，然后继续这个操作直到两个指针相遇。之后，将枢纽元与最后一个大者交换（如果枢纽元放到了最后位置就如此，如果在第一个就应与小者交换），然后递归即可。

上面的过程中，两个指针在遇到等于枢纽元的数时也都停止，这是为了保证数组中相同的数过多时算法的复杂度。考虑极端情况：数组是一个常数数列（实际上经常可能遇到这种情况，例如100000个数中有5000个相同的数，则快速排序最终不免来排序这5000个数），则只有都交换时，才能保证分割出的两个数组是平均的，否则就会分出一个空数组。同样，如果枢纽元是数组中的最大或最小数，同样会分出空数组。这样为何不好，我们下面来分析。

另外，由于数据较小时，多次分治递归的实际效率不佳，所以这时可以采用插入排序这种对小数组比较有利的排序，但下面分析时我们认为没有这样做。

二、快速排序复杂度分析

我们定义$N=|S|,N_1=|S_1|,N_2=|S_2|$，由于会排除枢纽元，有$N_1+N_2=N-1$，则关于时间复杂度上界有如下关系式：

$T(N)=T(N_1)+T(N_2)+N$

首先来分析最差的情况，即每一次分割都有$N_1=0, N_2=N-1$（由于枢纽元会被排除因此是$N-1$，如果不排除枢纽元则有可能不断递归）。能不能构造出这种情况呢？当然可以，如果我们每次都将数组的第一个元素选为枢纽元（这是一个不好的策略），而数组本身就是升序排列好的，则会产生这种情况，而且更尴尬的是，这时我们没有对这个数组做任何事，但是还是递归了很多次。次数如下：

$T(N)=T(N-1)+N$

最后当然算出$T(N)=N(N+1)/2=O(N^2)$，可见这是一个无法忍受的情况。快速排序的最坏情况莫过于此。如果$N_1$是一个稍大一点的数，但相对还是很小，可以分析出复杂度仍然不好。

再来分析最好的情况，也就是每次分割都能恰好分出一半。那么我们就有：

$T(N)=2T(N/2)+N$

这里我们已经分析过了，$T(N)=O(N log N)$。这就是快速排序最好情况的时间复杂度。

选取枢纽元的方法有很多，但主要是为了避免选到最大或最小值。一种很好的方法是三数中值法，即随机选取数组中的三个数（一般并不真正随机而是选首项、末项和中项），取三者的中间值作为枢纽元。显然此时枢纽元几乎不可能是最值了。这样一来，一个排好序的数组用三数中值法就可以达到最好情况。

但一般的数组不会是排好序的，三数中值法选到的枢纽元也会比较随机。我们做一个差一点的假设，每次选到的数是平均随机的，意思就是，$N_1$可能是$[0,N-1]$的所有数。那么我们就有期望值：

$T(N) = (1/N) [sum_{i=0}^{N-1} (T(i) + T(N-1-i))] + N$

$T(N)=(2/N) sum_{i=0}^{N-1}T(i) + N$

把分母去掉

$NT(N) = 2 sum_{i=0}^{N-1}T(i) + N^2$

为了分析这个式子，把$N-1$代入$N$，就有

$(N-1)T(N-1) = 2 sum_{i=0}^{N-2} T(i) + (N - 1)^2$

两个式子对减，就得到

$NT(N) - (N-1)T(N-1) = 2T(N-1) + 2N - 1$

合并一下同类项，然后把无关紧要的常数去掉，就有

$NT(N) = (N+1)T(N-1) + 2N$

这里$T$前面的式子不是很合适，我们用$N(N+1)$去除

$frac{T(N)}{N+1} = frac{T(N-1)}{N} + frac{2}{N+1}$

至此很显然，${ frac{T(N)}{N+1} }$与调和级数是等价的，也就是：

$frac{T(N)}{N+1} = 2sum_{i=2}^{N+1} 1/i = 2ln(N+1) + c$

其中$c$是$O(1)$的，而对数之间变换底数不影响它们的增长率等级，因此最终就有

$T(N) = O(N log N)$

这就是快速排序的平均复杂度。可以看到和它的最优复杂度是相同等级的。如果采用三数中值法寻找枢纽元，并注意处理数据相等时的情况，就可以避免最坏情况。

下面是一个采用三数中值法的示例，具体就不解释了。

int* _find_mid(int* l, int* r) {  //三数中值法
    int a = *l, b = *(l + ((r - l) / 2)), c = *(r - 1);
    if ((a >= b && b >= c) || (a <= b && b <= c)) {
        return l + ((r - l) / 2);
    }
    if ((b >= a && a >= c) || (b <= a && a <= c)) {
        return l;
    }
    if ((a >= c && c >= b) || (a <= c && c <= b)) {
        return r - 1;
    }
}

void quick_Sort(int* l, int* r) {  //快速排序
    if (r - l <= 3) {
        insert_Sort(l, r);
        return;
    }
    int* p = _find_mid(l, r);  //找到枢纽元
    int temp = *p;
    *p = *l;
    *l = temp;
    int t = *l;
    int *i = l, *j = r;
    while (i < j) {  //直到i和j相遇
        while (*(++i) < t && i < r) {
        }
        //寻找左侧首个大于等于枢纽元的数

        while (*(--j) > t && j > l) {
        }
        //寻找右侧首个小于等于枢纽元的数

        if (i < j) {  //交换两者
            temp = *i;
            *i = *j;
            *j = temp;
        }
    }
    temp = *j;
    *j = *l;
    *l = temp;  //将最后一个小数与枢纽元交换
    quick_Sort(l, j);
    quick_Sort(j + 1, r);  // i已经不需要进行排序了，它的位置是对的
    return;
}

从上面的分析过程可以看到，平均分析其实就是求解数学期望，因此会遇到各种和式，这时适当的做上面用过的相减可以极大地减少运算难度。