算法导论（四）：快排及随机化算法

麻省理工学院公开课：算法导论。B站地址，网易公开课也有对应的资源。
https://www.bilibili.com/video/av1149902/?p=4

视频比较长（80min），吓坏宝宝，以为内容挺多。换回了第一集的老师，感觉亲切好多啊哈哈。其实这一集内容不多，主要讲解了快速排序。

快速排序

这是一个分治策略的算法，在原地排序，不需要占用额外的空间，而且非常实用。
1、分：把数据分成2个数组
2、治：分别对数组进行递归求值
3、合并
前面讲过的归并排序也是分治策略的算法。不同点在于：快速排序是递归地划分数组，归并排序是递归地合并。

递归地划分数组的伪代码如下：

Partition(A, p, q)
x <- A[p]
i <- p
for j <- p+1
  do if A[j] <= x
    then i <- i+1
    exch A[i] <--> A[j]   //交换A[i]和A[j]
exch A[p] <--> A[i]    //交换A[p]和A[i]
return i;

整理一下JavaScript版本的代码：

function Partition(A, p, q){
    var x = A[p];
    var i = p;
    for(var j=0;j<q;j++){
        if(A[j] <= x){
            i = i+1;
            var tmp = A[i];
            A[i] = A[j];
            A[j] = tmp;
        }
    }
    var tmp1 = A[p];
    A[p] = A[i];
    A[i] = tmp1;
    return i;
}

找个实例来看一下具体是怎么划分的：
对数组A=[6, 10, 13, 5, 8, 3, 2, 11]进行划分
其中，p=6, q=11
选定第一个元素6为划分的主元素。将比6小的元素移到前面，比6大的元素移到后面。

交换过程如下：

6   10  13  5   8  3   2   11   // 初始数组，i指向6，j指向10
6   5   13  10  8  3   2   11   // j往后移动，找到<=6的元素5，i移动指向10，交换10和5的位置
6   5   3   10  8  13  2   11   // j继续移动，找到<=6的元素3，i移动指向13，交换13和3的位置
6   5   3   2   8  13  10  11   // j继续移动，找到<=6的元素2，i移动指向10，交换10和2的位置
2   5   3   6   8  13  10  11   // j移动到最后一位元素，划分完成。交换主元素6和索引i指向的元素

划分之后对数组进行求值，伪代码如下：

Quicksort(A, p, q)
if p < q
  then r <- Partition(A, p, q)   //中间元素
    Quicksort(A, p, r-1)
    Quicksort(A, r+1, q)

要注意处理数组内只有一个元素的情况。

快排的时间复杂度分析

最差的情况：数组已排序（正序or逆序）

此时递归表达式为 T(n) = T(0) + T(n-1) + Θ(n)
Θ(n)表示划分数组需要的消耗，T(0) = Θ(1)
所以 T(n) = T(n-1) + Θ(n) = Θ(n²)

画递归树图分析下

T(n) = cn + T(0) + T(n-1) T(n) = cn + T(0) + c(n-1) + T(0) + T(n-2)
最后完成的递归树如上图所示，树的高度为n。左边共有n个T(0)的叶节点，总和为nΘ(1) = Θ(n)。右边的总和为c(1+2+3+...+n) = Θ(n²)。所以整体时间复杂度为T(n) = Θ(n) + Θ(n²) = Θ(n²)

最佳情况

上面分析了最差的情况，下面来看最好的情况，即每次划分都能正好把数组一分为二为两个规模相同的子数组。递归表达式如下：【符合主方法的第二种情况】
T(n) = 2T(n/2) + Θ(n) = Θ(nlgn)

其它情况

除了分析最差、最佳的情况，再来看看其它情况。
假设每次都把数组划分为两个比例为1:9的数组。递归表达式如下T(n) = T(n/10) + T(9n/10) + Θ(n)
画递归树分析如下

T(n) = T(n/10) + T(9n/10) + cn

最后完成的递归树如上图所示，最左边的树的高度最矮，为log₁₀n。最右边的树的高度最高，为log_10/9n。
每一次划分需要的消耗均为cn，最后叶节点总数为n，所以总的时间复杂度T(n) ≤ cnlog_10/9n + Θ(n)，即Θ(nlgn)

再来一种情况

假设时而是n²，时而是nlgn的复杂度。即一次刚好划分为最佳情况，一次划分为最差情况，这样重复。
好的情况时， L(n) = 2U(n/2) + Θ(n)
差的情况时， U(n) = L(n-1) + Θ(n)
解递归式如下
L(n) = 2L(n/2-1) + 2Θ(n/2) + Θ(n)
....... = 2L(n/2-1) + Θ(n)
....... = Θ(nlgn)

---

综合上面的几种情况，只有数组已排序的情况下，时间复杂度为n²。那如何尽量避免这种情况呢？
有两种主要的方法：
1、打乱数字
2、随机选择划分的主元素（把主元素同随机一个元素交换位置即可）
这里选用第二种方法，也就是随机化快速排序。
随机化快速排序的好处是：运行时间不依赖于输入序列的顺序。无需对输入序列的分布做任何假设，即没有一种特定的输入，会引起最差的运行效率。

X_k = 1，如果划分为k:(n-k-1)
X_k = 0，划分为其它情况

【------------这块是概率论的内容---------】
E[X_k] —— X_k的期望值
E[X_k] = 0 · Pr{X_k=0} + 1 · Pr{X_k=1} = Pr{X_k=1} = 1/n

求解T(n)：
T(n) = T(0) + T(n-1) + Θ(n)，if 划分为0:n-1
T(n) = T(1) + T(n-2) + Θ(n)，if 划分为1:n-2
...
T(n) = T(n-1) + T(0) + Θ(n)，if 划分为n-1:0

T(n) = Σ X_k( T(k) + T(n-k-1) + Θ(n) )，k=0,1,2,...n-1

E[T(n)] = E[Σ X_k( T(k) + T(n-k-1) + Θ(n) )]
........... = Σ E[X_k( T(k) + T(n-k-1) + Θ(n) )] -----//和的期望 == 期望的和
........... = Σ E[X_k] · E[( T(k) + T(n-k-1) + Θ(n) )] -----//积的期望 == 期望的积
........... = (1/n) Σ E[( T(k) + T(n-k-1) + Θ(n) )] -----//上面已求得 E[X_k] = 1/n
........... = (1/n) Σ E[T(k)] + (1/n) Σ E[T(n-k-1)] + (1/n) Σ E[Θ(n)] ------// Σ E[T(k)] == Σ E[T(n-k-1)]
........... = (2/n) Σ E[T(k)] + Θ(n)

以上的Σ表示从 k=0,1,2,3,...,n-1 累加的情况。

把k=0,1时的项吸收到Θ(n)中，使它更简洁。
E[T(n)] = (2/n) Σ E[T(k)] + Θ(n)，k=2,3,4...,n-1

一个证明

要证明T(n)的运行时间期望值为 E[T(n)] ≤ anlgn，a>0
代换法
1、证明基础情况，通过选择一个足够大的a，使anlgn > E[T(n)]
有个已经证明成立的结论：Σ klgk ≤ (1/2)n²lgn-1/8n²，k=2, 3, 4, ... , n-1
有空的话可以自己去证明。【这个后面有空再补充】

2、代换
E[T(n)] ≤ (2/n)Σaklgk + Θ(n)
........... ≤ (2a/n)[(1/2)n²lgn-(1/8)n²] + Θ(n)
........... = anlgn - [(a/4)n - Θ(n)]

anlgn是我们需要的理想情况，(a/4)n-Θ(n)是余项，
要使得：E[T(n)] ≤ anlgn成立，余项>0，即(a/4)n-Θ(n)>0
这里无论Θ(n)的常数项多大，都可以找到更大的a来使得余项>0成立。

所以随机化快速排序的时间复杂度为nlgn。这是个非常实用的算法，通常可以比归并排序快三倍以上。