[003]:http://latex.codecogs.com/svg.latex?$\Theta(\textit%20n\cdot%20log_2(n))$
[004]:http://latex.codecogs.com/svg.latex?$H(X)%20=%20-\sum_{i}{}P(X_i)%20\cdot%20log_2(P(X_i))$
[005]:http://latex.codecogs.com/svg.latex?i%20\in%20[1,n!],%20\forall%20i\in[1,n!]%20%20%20%20P(X_i)%20=\frac{1}{n!}
[006]:http://latex.codecogs.com/svg.latex?H(X)%20=%20-n!\cdot%20\frac{1}{n!}log_2{\frac{1}{n!}}=log_2{(n!)}
[007]:http://latex.codecogs.com/svg.latex?log_2{(n!)}=\Theta(n\cdot%20log_2(n))
[008]:http://latex.codecogs.com/svg.latex?\Theta(n\cdot%20log_2(n))
[009]:http://latex.codecogs.com/svg.latex?-p\cdot%20log_2{p}-(1-p)\cdot%20log_2{(1-p)}
[010]:http://latex.codecogs.com/svg.latex?\frac{\Theta(n\cdot%20log_2(n))}{1}=\Theta(n\cdot%20log_2(n))
[011]:http://latex.codecogs.com/svg.latex?\Theta(n^2)%20%20and%20%20\Theta(n)
[012]:http://latex.codecogs.com/svg.latex?\Omega(n)%20%20and%20%20O(n^2)%20%20and%20%20\Theta(n)
[013]:http://latex.codecogs.com/svg.latex?\Theta(n%20\cdot%20log_2(n))%20%20and%20%20\Theta(n%20\cdot%20log_2(n))
[014]:http://latex.codecogs.com/svg.latex?\Omega(n%20\cdot%20log_2(n))%20%20and%20%20O(n^2)%20%20and%20%20\Theta(n)
[015]:http://latex.codecogs.com/svg.latex?\Theta(n%20\cdot%20log_2(n))
[016]:http://latex.codecogs.com/svg.latex?E(n)=\frac{1}{n}(E(0)+E(n-1))+\frac{1}{n}(E(1)+E(n-2))+...+\frac{1}{n}(E(n-1)+E(0))+n+1=\frac{2}{n}\sum_{i=0}^{n-1}E(i)+n+1%20\Rightarrow
[017]:http://latex.codecogs.com/svg.latex?n%20\cdot%20E(n)=2\cdot%20\sum_{i=0}^{n-1}E(i)+(n+1)\cdot%20n
[018]:http://latex.codecogs.com/svg.latex?(n-1)%20\cdot%20E(n-1)=2\cdot%20\sum_{i=0}^{n-2}E(i)+n\cdot%20(n-1)
[019]:http://latex.codecogs.com/svg.latex?n%20\cdot%20E(n)-(n-1)%20\cdot%20E(n-1)=2\cdot%20E(n-1)+2%20\cdot%20n
[020]:http://latex.codecogs.com/svg.latex?n%20\cdot%20E(n)=(n+1)%20\cdot%20E(n-1)+2%20\cdot%20n
[021]:http://latex.codecogs.com/svg.latex?a_n%20\cdot%20E(n)=b_n%20\cdot%20E(n-1)+c_n
[022]:http://latex.codecogs.com/svg.latex?a_n=n,b_n=n+1,c_n=2\cdot%20n
[023]:http://latex.codecogs.com/svg.latex?s_n%20\cdot%20a_n\cdot%20E(n)=s_n%20\cdot%20b_n\cdot%20E(n-1)+s_n%20\cdot%20c_n
[024]:http://latex.codecogs.com/svg.latex?S_n=s_n\cdot%20a_n%20%20and%20%20S_{n-1}=s_n\cdot%20b_n
[025]:http://latex.codecogs.com/svg.latex?S_n\cdot%20E(n)=S_{n-1}\cdot%20E(n-1)+s_n\cdot%20c_n
[026]:http://latex.codecogs.com/svg.latex?S_n\cdot%20E(n)=S_0\cdot%20E(0)+\sum_{i=0}^{n}s_i\cdot%20c_i
[027]:http://latex.codecogs.com/svg.latex?S_n=s_n\cdot%20a_n%20,S_{n-1}=s_n\cdot%20b_n\Rightarrow%20S_{n-1}=s_n\cdot%20b_n=s_{n-1}\cdot%20a_{n-1}\Rightarrow
[028]:http://latex.codecogs.com/svg.latex?s_n=\frac{s_{n-1}\cdot%20a_{n-1}}{b_n}
[029]:http://latex.codecogs.com/svg.latex?s_n=\frac{a_{n-1}\cdot%20a_{n-2}\cdot%20...\cdot%20a_{1}}{b_n\cdot%20b_{n-1}\cdot%20...\cdot%20b_{2}}
[030]:http://latex.codecogs.com/svg.latex?s_n=\frac{2}{(n+1)\cdot%20n}
[031]:http://latex.codecogs.com/svg.latex?\frac{2}{n+1}\cdot%20E(n)=S_0\cdot%20E(0)+\sum_{i=1}^{n}\frac{4}{i}
[031]:http://latex.codecogs.com/svg.latex?\frac{2}{n+1}\cdot%20E(n)=S_0\cdot%20E(0)+\sum_{i=1}^{n}\frac{4}{i}
[032]:http://latex.codecogs.com/svg.latex?E(n)=2\cdot%20(n+1)\cdot\sum_{i=1}^{n}\frac{1}{i}
[033]:http://latex.codecogs.com/svg.latex?\sum_{i=1}^{n}\frac{1}{i}=log_2(n)+O(1)
[034]:http://latex.codecogs.com/svg.latex?E(n)=\Theta(n\cdot%20log_2(n))
算法研究是計(jì)算機(jī)科學(xué)中重要的一個(gè)分支辩撑。眾多基礎(chǔ)算法中咕宿，比較排序算法是基礎(chǔ)中的基礎(chǔ)对室。本文主要介紹一種經(jīng)典的比較排序算法----快速排序算法（由Tony Hoare于1961年發(fā)表）的基本思路拉宗，優(yōu)點(diǎn)以及時(shí)間和空間復(fù)雜度分析。

比較排序算法

概念

簡單而言渡冻，比較排序算法是對(duì)兩個(gè)元素進(jìn)行比較來決定兩個(gè)元素的在輸出序列中相對(duì)位置（誰在前面誰在后面）的排序算法戚扳。從數(shù)學(xué)意義說，比較排序算法要求序列中的元素滿足如下兩條性質(zhì)

• 
• 
  
  

  比較排序算法類似用天平來比較兩個(gè)物體之間誰的質(zhì)量大小來排序

  
  
  800px-Balance_à_tabac_1850.JPG

圖片來自：由Photographie personnelle User:Poussin jean - objet personnel User:Poussin jean族吻，CC BY-SA 3.0帽借，https://commons.wikimedia.org/w/index.php?curid=1681347

時(shí)間復(fù)雜度下界

首先拋出結(jié)論，比較排序算法的下界是![][003] n為序列長度呼奢。證明方法有很多宜雀，算法導(dǎo)論中用的是決策樹模型證明（The decision-tree model）。我在這里想展示另外一種證明方法：信息熵（因?yàn)槲沂峭ㄐ殴烦錾砦沾。m然現(xiàn)在已經(jīng)拜在圖靈的門下辐董，但香農(nóng)仍是我的祖師爺啊）禀综。
熵值的數(shù)學(xué)表達(dá)為![][004]如果序列長度為n简烘，那么對(duì)序列排序后則可能有 n! 種結(jié)果。如果輸入序列是完全隨機(jī)序列定枷，則每種結(jié)果的概率是相等的孤澎。具體到比較排序算法和之前的熵值公式![][005]帶回熵值公式![][006]算法導(dǎo)論中3.19證明了![][007]也就是說，針對(duì)排序而言欠窒，一個(gè)長度為n的序列覆旭，其蘊(yùn)含的信息量為![][008]接下來我們分析一下一次比較操作所消除的信息量。對(duì)于任意的a和b岖妄，假設(shè) p 為 a < b 的概率型将，那么一次比較操作所能消除的信息量C為![][009]對(duì)于隨機(jī)序列，p = 0.5,C=1荐虐，這也是C能取到的最大值七兜。所以想用比較操作來完成序列排序，至少要![][010]次比較操作福扬。

常見的比較排序算法

• 冒泡排序（Bubble Sort）時(shí)間復(fù)雜度和空間復(fù)雜度為![][011]
• 插入排序（Insertion Sort） 時(shí)間復(fù)雜度下界腕铸，上界以及空間復(fù)雜度為![][012]
• 歸并排序（Merge Sort）時(shí)間復(fù)雜度和空間復(fù)雜度為![][013]可見雖然歸并排序的時(shí)間復(fù)雜度符合理論最小值，但它的空間復(fù)雜度也很高铛碑。更蛋疼的是歸并排序的時(shí)間復(fù)雜度分析是建立在RAM模型（Random Access Memory）上狠裹，而實(shí)際的計(jì)算機(jī)內(nèi)存模型并不是RAM而是有cache的。因?yàn)闅w并排序算法在每次遞歸迭代過程中都會(huì)申請(qǐng)新的內(nèi)存然后在新申請(qǐng)內(nèi)存上進(jìn)行操作汽烦。這不匹配于cache內(nèi)存機(jī)制酪耳，所以歸并排序算法在真實(shí)硬件上的表現(xiàn)不很理想。不過隨著并行，分布式系統(tǒng)的興起碗暗，這個(gè)算法又有了新的生機(jī)。它非常適合并行優(yōu)化梢夯，并且已經(jīng)有了相應(yīng)分析和研究（如果這篇反響好我第二篇就寫這個(gè)內(nèi)容）言疗。

快速排序算法

偽碼

快速排序則充分利用了cache機(jī)制，算法的偽碼是

algorithm quicksort(A, lo, hi) 

    if lo < hi then p := partition(A, lo, hi) 
    quicksort(A, lo, p – 1) 
    quicksort(A, p + 1, hi) 

algorithm partition(A, lo, hi)

    pivot := A[hi] 
    i := lo
    for j := lo to hi – 1 do 
    if A[j] ≤ pivot then 
        swap A[i] with A[j] 
        i := i + 1 
    swap A[i] with A[hi] 
    return i

復(fù)雜度分析

顯然颂砸，快速排序的時(shí)間復(fù)雜度的下界噪奄，上界以及空間復(fù)雜度為![][014]看上去并不怎么樣。但因?yàn)檩斎胄蛄袨殡S機(jī)序列人乓，所以我們還得關(guān)注下時(shí)間復(fù)雜度的期望值勤篮。
在算法導(dǎo)論中，快速排序的時(shí)間復(fù)雜度期望值證明思路如下

• 猜測(cè)其時(shí)間復(fù)雜度的期望值為![][015]
• 再用數(shù)學(xué)歸納法證明

另一種分析方法

但作為強(qiáng)迫癥晚期的我總覺得這個(gè)方法不夠酷炫色罚，因?yàn)椴聹y(cè)時(shí)間復(fù)雜度期望值這一步總有一種碰運(yùn)氣的感覺（當(dāng)然這是調(diào)侃的說法碰缔，其實(shí)這種思路在數(shù)學(xué)證明中有時(shí)候很有用）〈粱ぃ基于此金抡，向大家隆重推出下面這種方法，簡直是狂拽酷炫屌炸天（純個(gè)人主觀喜好腌且。梗肝。。铺董。）巫击。假設(shè)E(n)為輸入序列長度為n時(shí)期望的時(shí)間復(fù)雜度，則![][016]![][017]那么![][018]兩式相減![][019]![][020]我們將這個(gè)等式一般化![][021]![][022]接下來我們將一般化后的等式兩邊變形為![][023]我們假設(shè)這個(gè)參數(shù)選擇得非常好精续，巧妙的滿足![][024]所以等式可以變形為![][025]化簡![][026]![][027]![][028]迭代則有![][029]我們將![][022]代入后得到![][030]![][031]因?yàn)镋(0)=0![][032]從算法導(dǎo)論的A.7可知![][033]所以![][034]
上述證明來自于具體數(shù)學(xué)（concrete mathematics）第二章

總結(jié)

時(shí)間復(fù)雜度的期望值符合理論最小值坝锰，并且空間復(fù)雜度只有O(n)，能夠很好的利用cache機(jī)制驻右。所以快速排序是很不錯(cuò)的串行比較排序算法什黑，特別是在真實(shí)的硬件上，所以gcc中還有qsort這個(gè)庫函數(shù)（stdlib.h）堪夭。

第一次用Markdown愕把，輸入公式好累啊。森爽。恨豁。。爬迟。