- 作為最常用和好用的排序方法, 快速排序是每個(gè)工程師必須隨時(shí)能夠手寫出代碼和解釋其運(yùn)行原理的算法
快速排序算法
- Quick-Sort(A, p, r)
if p<r
q = Partition(A, p, r)
Quick-Sort(A, p, q-1)
Quick-Sort(A. q+1, r)
- Partition(A, p, r)
q = RANDOＭ(p, r)
swap A[q] and A[r] //現(xiàn)在A[r]是一個(gè)隨機(jī)挑選的值
i = p-1 // i指向分界線左側(cè)最后一個(gè)元素, 其初始值定在p-1表示還沒有任何小于q的元素
for j=p to r-1 //區(qū)分已經(jīng)分好的未分好的區(qū)域的指針不斷向右移動(dòng)
if A[j]<=A[r]
i++ //讓小于q的分界線指針向右移動(dòng)
swap A[i] with A[j] //發(fā)現(xiàn)A[j]是比q所在值小的話, 把A[j]換到分界線的左側(cè)第一個(gè)位置, 即A[i]位置
swap A[i+1] and A[r] //交換分界線右側(cè)第一個(gè)位置的元素, 保證q左側(cè)的<=q, q右側(cè)的>=q
return q
快排時(shí)間復(fù)雜度分析
CLRS告訴我們, 快速排序在不斷遞歸的過程中, 遞歸樹的每一層花費(fèi)的時(shí)間都是Partition的時(shí)間, 因此整體的時(shí)間復(fù)雜度T(n)取決于整個(gè)算法到底進(jìn)行了多少次Partition, 而每次Partition的時(shí)間復(fù)雜度又是不相等的 -- Partition的時(shí)間復(fù)雜度取決于其中的for循環(huán)進(jìn)行的次數(shù), 而 for循環(huán)主要的操作就是比較大小.
所以, 整個(gè)算法的T(n)最后在研究進(jìn)行了幾次比較大小操作的問題
-
對(duì)于輸入數(shù)組A的規(guī)模為n的情況, 我們已經(jīng)知道的:
- 每個(gè)元素對(duì)(pair)最多只比較一次, 而且這次比較只出現(xiàn)在pair中有一個(gè)元素被選中為q (A[q] becomes partition pivot).
- 反過來說, 在選q的時(shí)候, 如果一個(gè)pair<ai, aj> (i<j且都∈[current-p, current-r])中的元素都沒被選中, 而是有一個(gè)i<=x<=j的的元素被選為pivot, 那么ai和aj將永遠(yuǎn)失去相互比較的機(jī)會(huì). 注意, 此處如果[i, j]區(qū)間外的元素被選中, 由于a[i], a[j]可能被分配到同一邊, 仍存在相互比較的機(jī)會(huì), 這對(duì)寫概率公式很重要
- Ind{[i, j]區(qū)間中A[i], A[j]外的其他元素不被選中} = Ind{a[i]或者a[j]被選中作為pivot} == Ind{在[i, j]中i被選中} + Ind{在[i, j]中j被選中}
- E[Ind{在[i, j]中i被選中}] = E[Ind{在[i, j]中j被選中}] = 1/(j-i+1)
- 規(guī)模為n的情況下, 且元素對(duì)不考慮排序, 會(huì)有C(n, 2)= (n(n-1))/(21) 個(gè)pair的組合, 一般為了算期望, 我們會(huì)改寫成 Σ[in-1]Σ[j=i+1n] 形式 (容易證明得到這兩個(gè)寫法是完全等價(jià)的) 來遍歷得出所有可能的組合, 即pair的數(shù)目
假設(shè)X為總的比較次數(shù)的隨機(jī)變量 E[X] = Σ[in-1]Σ[j=i+1n] (Ind{a[i]或者a[j]被選中作為pivot}) = Σ[in-1]Σ[j=i+1n](2 / (j-i+1) ) = O(nlgn)
