相信大家在大學(xué)的《算法與數(shù)據(jù)結(jié)構(gòu)》里面都學(xué)過快速排序(QuickSort), 知道這種排序的性能很好罢维，JDK里面直到JDK6用的都是這種經(jīng)典快排的算法锉试。但是到了JDK7的時候JDK內(nèi)置的排序算法已經(jīng)由經(jīng)典快排變成了Dual-Pivot排序算法。那么Dual-Pivot到底是何方圣神熟妓，能比我們學(xué)過的經(jīng)典快排還要快呢遏片？我們一起來看看。
經(jīng)典快排
在學(xué)習(xí)新的快排之前豪墅，我們首先來復(fù)習(xí)一下經(jīng)典快排，它的核心思想是:
接受一個數(shù)組黔寇，挑一個數(shù)(pivot)偶器，然后把比它小的那一攤數(shù)放在它的左邊，把比它大的那一攤數(shù)放在它的右邊，然后再對這個數(shù)左右兩攤數(shù)遞歸的執(zhí)行快排過程屏轰，直到子數(shù)組只剩一個數(shù)為止颊郎。[2]
偽代碼大概是這樣的:
void quicksort(int array[], int left, int right)
{
//Do nothing if left <= right
//p <- Get a number from array
//Put elements <= p to the left side
//Put elements >= p to the right side
//Put p in the middle slot which index is pivot
//Recursive quicksort the left parts and right parts
}
元素比較的次數(shù)
經(jīng)典快排為什么快？ 所謂快其實專業(yè)的說法是“時間復(fù)雜度”霎苗。對于排序算法來說主要看的是排序所需要的元素比較的次數(shù)姆吭。
我們在《算法與數(shù)據(jù)結(jié)構(gòu)》里面都是這么學(xué)的。
對于快排來說唁盏，假設(shè)輸入數(shù)組里面數(shù)字的個數(shù)為n猾编，那么平均要進(jìn)行的元素之間比較的次數(shù)是: O(nlogn)。相比冒泡排序的O(n2)來說比較的次數(shù)要少升敲，那么當(dāng)然就快了答倡。
Dual-Pivot快排是個什么鬼？
它是俄羅斯人Vladimir Yaroslavskiy在2009年開發(fā)出來的驴党。要知道經(jīng)典快排在1990年代穩(wěn)定下來就再也沒有大改過了瘪撇，幾乎所有的語言里面的排序用的都是同樣的經(jīng)典快排的算法。20年之后當(dāng)這個俄羅斯人提出新的Dual-Pivot快排的時候港庄，很多人的第一想法是不信的倔既，因為經(jīng)典快排都被研究爛了，大家不相信在這個算法上面還會有什么可以改進(jìn)的地方鹏氧。
那么Dual-Pivot快排到底是怎么樣的一個排序算法呢渤涌？其實從它的名字里面可以看出一些端倪：在經(jīng)典快排里面有一個pivot的概念，它是用來分隔大數(shù)和小數(shù)的 -- 這個pivot把一個數(shù)組分成兩份把还。那么所謂的Dual-Pivot其實就是用兩個Pivot, 把整個數(shù)組分成三份实蓬。偽代碼大概是這樣的:
dual_pivot_quicksort(A,left,right) // sort A[left..right]
if right?left ≥ 1
// Take outermost elements as pivots (replace by sampling)
p := min {A[left],A[right]}
q := max{A[left],A[right]}
? := left +1; g := right ?1; k := ?
while k ≤ g
if A[k] < p
Swap A[k] and A[?]; ? := ?+1
else if A[k] ≥ q
while A[g] > q and k < g
g := g ?1
end while
Swap A[k] and A[g]; g := g ?1
if A[k] < p
Swap A[k] and A[?]; ? := ?+1
end if
end if
k := k +1
end while
? := ??1; g := g +1
A[left] := A[?]; A[?] := p // p to final position
A[right] := A[g]; A[g] := q // q to final position
dual_pivot_quicksort(A, left , ??1)
dual_pivot_quicksort(A, ?+1,g ?1)
dual_pivot_quicksort(A,g +1,right)
end if
看起來主要的區(qū)別就是經(jīng)典快排遞歸的時候把輸入數(shù)組分兩段，而Dual-Pivot則分三段吊履，就這么簡單安皱，那為什么這就快了呢？
其實如果按照元素比較次數(shù)來比較的話艇炎，Dual-Pivot快排元素比較次數(shù)其實比經(jīng)典快排要多:
1.5697nlnn VS 1.7043nlnn
理論跟實際情況不符合的時候酌伊，如果實際情況沒有錯，那么就是理論錯了缀踪。
CPU與內(nèi)存
要理解上面的問題居砖，先介紹點背景知識。我們平常很少考慮過CPU的速度驴娃，內(nèi)存的速度奏候，CPU和內(nèi)存速度是否匹配的問題。
其實它們是不匹配的托慨。
距統(tǒng)計在過去的25年里面鼻由，CPU的速度平均每年增長46%, 而內(nèi)存的帶寬每年只增長37%暇榴，那么經(jīng)過25年的這種不均衡發(fā)展厚棵，它們之間的差距已經(jīng)蠻大了蕉世。
假如這種不均衡持續(xù)持續(xù)發(fā)展，有一天CPU速度再增長也不會讓程序變得更快婆硬，因為CPU始終在等待內(nèi)存?zhèn)鬏敂?shù)據(jù)狠轻，這就是傳說中內(nèi)存墻(Memory Wall)。
有點像木桶理論：木桶的容量是由最短的那塊板決定的彬犯，所以你CPU再快向楼，如果內(nèi)存帶寬不夠，那也沒用谐区。
25年前Dual-Pivot快排可能真的比經(jīng)典快排要慢湖蜕，但是25年之后雖然算法還是以前的那個算法，但是計算機(jī)已經(jīng)不是以前的計算機(jī)了宋列。在現(xiàn)在的計算機(jī)里面Dual-Pivot算法更快昭抒！
掃描元素個數(shù)
那么既然光比較元素比較次數(shù)這種計算排序算法復(fù)雜度的方法已經(jīng)無法客觀的反映算法優(yōu)劣了，那么應(yīng)該如何來評價一個算法呢炼杖？作者提出了一個叫做掃描元素個數(shù)的算法灭返。
在這種新的算法里面，我們把對于數(shù)組里面一個元素的訪問: array[i] 稱為一次掃描坤邪。但是對于同一個下標(biāo)熙含，并且對應(yīng)的值也不變得話，即使訪問多次我們也只算一次艇纺。而且我們不管這個訪問到底是讀還是寫怎静。
其實這個所謂的
掃描元素個數(shù)反應(yīng)的是CPU與內(nèi)存之間的數(shù)據(jù)流量的大小。
因為內(nèi)存比較慢黔衡，統(tǒng)計CPU與內(nèi)存之間的數(shù)據(jù)流量的大小也就把這個比較慢的內(nèi)存的因素考慮進(jìn)去了消约，因此也就比元素比較次數(shù)更能體現(xiàn)算法在當(dāng)下計算機(jī)里面的性能指標(biāo)。
在這種新的算法下面經(jīng)典快排和Dual-Pivot快排的掃描元素個數(shù)分別為:
1.5697nlnn VS 1.4035nlnn
也就是說經(jīng)典快排確實進(jìn)行了更多的元素掃描動作员帮，因此也就比較慢或粮。在這種新的算法下面，Dual-Pivot快排比經(jīng)典快排t節(jié)省了12%的元素掃描捞高，從實驗來看節(jié)省了10%的時間氯材。
結(jié)論
- 由于CPU與內(nèi)存的發(fā)展失衡，我們在分析算法復(fù)雜性的時候已經(jīng)不能簡單地用
元素比較次數(shù)來比較了硝岗，因為這種比較的方法只考慮了CPU的因素氢哮，沒有考慮內(nèi)存的因素。 - 對于那種對輸入數(shù)據(jù)進(jìn)行順序掃描的排序算法型檀，
掃描元素的個數(shù)這種新的算法把內(nèi)存的流量的因素考慮進(jìn)去冗尤，比較適應(yīng)新時代。 - 世界在不斷的變化，你當(dāng)年在學(xué)堂里面學(xué)的東西可能已經(jīng)過時了裂七。
