麻省理工學院公開課：算法導論。B站地址，網(wǎng)易公開課也有對應(yīng)的資源。
https://www.bilibili.com/video/av1149902/?p=4

視頻比較長（80min），嚇壞寶寶，以為內(nèi)容挺多。換回了第一集的老師，感覺親切好多啊哈哈。其實這一集內(nèi)容不多，主要講解了快速排序。

快速排序

這是一個分治策略的算法，在原地排序，不需要占用額外的空間，而且非常實用。
1、分：把數(shù)據(jù)分成2個數(shù)組
2、治：分別對數(shù)組進行遞歸求值
3、合并
前面講過的歸并排序也是分治策略的算法。不同點在于：快速排序是遞歸地劃分數(shù)組，歸并排序是遞歸地合并。

遞歸地劃分數(shù)組的偽代碼如下：

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;
}

找個實例來看一下具體是怎么劃分的：
對數(shù)組A=[6, 10, 13, 5, 8, 3, 2, 11]進行劃分
其中，p=6, q=11
選定第一個元素6為劃分的主元素。將比6小的元素移到前面，比6大的元素移到后面。

交換過程如下：

6   10  13  5   8  3   2   11   // 初始數(shù)組，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繼續(xù)移動，找到<=6的元素3，i移動指向13，交換13和3的位置
6   5   3   2   8  13  10  11   // j繼續(xù)移動，找到<=6的元素2，i移動指向10，交換10和2的位置
2   5   3   6   8  13  10  11   // j移動到最后一位元素，劃分完成。交換主元素6和索引i指向的元素

劃分之后對數(shù)組進行求值，偽代碼如下：

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

要注意處理數(shù)組內(nèi)只有一個元素的情況。

快排的時間復雜度分析

最差的情況：數(shù)組已排序（正序or逆序）

此時遞歸表達式為 T(n) = T(0) + T(n-1) + Θ(n)
Θ(n)表示劃分數(shù)組需要的消耗，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)

最佳情況

上面分析了最差的情況，下面來看最好的情況，即每次劃分都能正好把數(shù)組一分為二為兩個規(guī)模相同的子數(shù)組。遞歸表達式如下：【符合主方法的第二種情況】
T(n) = 2T(n/2) + Θ(n) = Θ(nlgn)

其它情況

除了分析最差、最佳的情況，再來看看其它情況。
假設(shè)每次都把數(shù)組劃分為兩個比例為1:9的數(shù)組。遞歸表達式如下T(n) = T(n/10) + T(9n/10) + Θ(n)
畫遞歸樹分析如下

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

最后完成的遞歸樹如上圖所示，最左邊的樹的高度最矮，為log₁₀n。最右邊的樹的高度最高，為log_10/9n。
每一次劃分需要的消耗均為cn，最后葉節(jié)點總數(shù)為n，所以總的時間復雜度T(n) ≤ cnlog_10/9n + Θ(n)，即Θ(nlgn)

再來一種情況

假設(shè)時而是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)

綜合上面的幾種情況，只有數(shù)組已排序的情況下，時間復雜度為n²。那如何盡量避免這種情況呢？
有兩種主要的方法：
1、打亂數(shù)字
2、隨機選擇劃分的主元素（把主元素同隨機一個元素交換位置即可）
這里選用第二種方法，也就是隨機化快速排序。
隨機化快速排序的好處是：運行時間不依賴于輸入序列的順序。無需對輸入序列的分布做任何假設(shè)，即沒有一種特定的輸入，會引起最差的運行效率。

X_k = 1，如果劃分為k:(n-k-1)
X_k = 0，劃分為其它情況

【------------這塊是概率論的內(nèi)容---------】
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、證明基礎(chǔ)情況，通過選擇一個足夠大的a，使anlgn > E[T(n)]
有個已經(jīng)證明成立的結(jié)論：Σ 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)的常數(shù)項多大，都可以找到更大的a來使得余項>0成立。

所以隨機化快速排序的時間復雜度為nlgn。這是個非常實用的算法，通?？梢员葰w并排序快三倍以上。