四. 走向世界之巔——快速排序
你可能會(huì)以為歸并排序是最強(qiáng)的算法了，其實(shí)不然诊胞。回想一下锹杈，歸并的時(shí)間效率雖然高撵孤，但空間效率仍然有可以改進(jìn)的空間，人類仍然不滿足竭望，仍然孜孜不倦追求更好邪码，更快和更強(qiáng)，于是便有了快速排序咬清，這一神一樣的算法以各種面目出現(xiàn)在各種編程語(yǔ)言中闭专，最著名的就是C語(yǔ)言中的qsort了，Java也用它來(lái)排序基本類型旧烧∮髌裕快速排序被稱為20世紀(jì)最偉大的10大算法之一，它們是：
- 蒙特卡洛方法
- 單純形法
- Krylov子空間迭代法
- 矩陣計(jì)算的分解方法
- 優(yōu)化的Fortran編譯器
- 計(jì)算矩陣特征值的QR算法
- 快速排序算法
- 快速傅立葉變換
- 整數(shù)關(guān)系探測(cè)算法
- 快速多極算法
所以今天粪滤，我們要來(lái)了解一下這個(gè)偉大算法的基本思想斧拍，以及數(shù)十年來(lái)無(wú)數(shù)牛人對(duì)她的研究和改進(jìn)。
4.1 基本思想
快速排序的基本思想是這樣的：對(duì)一個(gè)含有N個(gè)元素的序列arr杖小，我們?cè)谛蛄兄姓业揭粋€(gè)界標(biāo)j肆汹，然后對(duì)序列進(jìn)行分區(qū)，把不大于arr[j]的元素放在j的左邊予权，把不小于arr[j]的元素放在j的右邊昂勉，然后再遞歸地對(duì)arr[0..j-1]和arr[j+1..N-1]重復(fù)上述分區(qū)過(guò)程，如圖4-1所示扫腺。這里有兩個(gè)關(guān)鍵的點(diǎn)要注意把握岗照，首先該輸入序列要進(jìn)行均勻的隨機(jī)洗牌，從概率上保證其運(yùn)行效率笆环，因此快速排序是一種隨機(jī)化算法攒至；其次，就像歸并排序的關(guān)鍵在于歸并一樣躁劣，快速排序的關(guān)鍵在于分區(qū)的過(guò)程迫吐，它看似簡(jiǎn)單，但實(shí)現(xiàn)的時(shí)候?qū)吔绲臋z查要小心仔細(xì)账忘，否則容易出錯(cuò)志膀。后面我們將看到熙宇，圍繞這個(gè)分區(qū)人們給出了各種各樣的應(yīng)用和改進(jìn)，它是這個(gè)算法最出彩的地方溉浙。
4.2 算法和性能分析
我們先來(lái)搞懂分區(qū)的工作原理烫止。如下所示，我們以a[lo]為分區(qū)界標(biāo)v戳稽，索引i從左往右走速蕊，索引j從右往左走栅炒，一直走到i所在位置的值不小于v蜓竹，且j所在位置的值不大于v蝶溶，這樣的兩個(gè)值是逆序的，對(duì)它們進(jìn)行一次交換赊时，當(dāng)i和j相遇后循環(huán)即停止吨铸，此時(shí)j指向第一個(gè)不大于v的元素，將它與a[lo]交換祖秒，就得到了分區(qū)好的序列诞吱，最后分區(qū)方法返回新的界標(biāo)索引j即可，圖4-2給出了分區(qū)前竭缝、分區(qū)中和分區(qū)后的演示房维。排序的過(guò)程其實(shí)挺簡(jiǎn)單，排序前先對(duì)序列進(jìn)行一次隨機(jī)洗牌抬纸，使用（Knuth Shuffle）咙俩，然后進(jìn)行排序，排序的過(guò)程是先分區(qū)取得界標(biāo)j湿故，然后遞歸排序a[lo..j-1]和a[j+1..hi]即可阿趁。圖4-3給出快速排序算法的一個(gè)完成的演示。有科學(xué)家對(duì)快速排序進(jìn)行過(guò)分析坛猪，在最好情況下脖阵，快速排序效率為O(NlgN)，最壞情況下為O(N^2)墅茉，但是命黔，通過(guò)隨機(jī)洗牌，我們能夠保證快速排序算法在絕大多數(shù)情況下對(duì)含有N個(gè)不同元素序列的運(yùn)行效率為O(NlgN)就斤，而那極少數(shù)情況發(fā)生的概率比你中五百萬(wàn)大獎(jiǎng)的概率還要低悍募。
快速排序的平均效率能夠達(dá)到1.39NlgN，比歸并排序只高了39%战转，但實(shí)際應(yīng)用中卻更快——因?yàn)榭焖倥判蛞苿?dòng)的元素更少搜立，快速排序是真正的就地排序算法，它不需要額外開(kāi)辟大小為N的臨時(shí)空間槐秧，因此空間效率比歸并排序要好啄踊，但是它卻不是一種穩(wěn)定的算法，有關(guān)幾種算法運(yùn)行效率的經(jīng)驗(yàn)值如圖4-4所示刁标。
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
Comparable v = a[lo];
while (true) {
// find item on lo to swap
while (less(a[++i], v))
if (i == hi) break;
// find item on hi to swap
while (less(v, a[--j]))
if (j == lo) break; // redundant since a[lo] acts as sentinel
// check if pointers cross
if (i >= j) break;
exch(a, i, j);
}
// put partitioning item v at a[j]
exch(a, lo, j);
// now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
return j;
}
public static void sort(Comparable[] a) {
StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
}
// quicksort the subarray from a[lo] to a[hi]
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int j = partition(a, lo, hi);
sort(a, lo, j-1);
sort(a, j+1, hi);
assert isSorted(a, lo, hi);
}
4.3 鏡鑒快速排序——求第k大的元素
在實(shí)際工作中颠通，我們常常會(huì)碰到這樣的問(wèn)題，即求一個(gè)序列中最大的元素或者最小的元素膀懈，這種問(wèn)題實(shí)際上是順序統(tǒng)計(jì)學(xué)上求“第k大的元素”的一種特例顿锰。這種問(wèn)題一眼看上去好像很簡(jiǎn)單：對(duì)序列排序然后取第k個(gè)元素即可。但這樣一來(lái)解決問(wèn)題的效率就變成了O(NlgN)启搂，還能不能更快些呢硼控？當(dāng)然能！這里可以借鑒partition的思想編寫(xiě)一個(gè)quick-select算法胳赌，該算法每次都使用partition取得分區(qū)界標(biāo)j牢撼，此時(shí)j左邊的元素都比它小，右邊的元素都比它大疑苫，如果j == k熏版，說(shuō)明我們找到了，返回a[k]捍掺；否則撼短，如果j < k，下一次我們就在j的右邊找（a[j+1..hi]）,如果j > k挺勿，說(shuō)明k在j的左邊曲横，下一次我們就在j的左邊找（a[lo..j-1]）。算法像二叉查找一樣不瓶，每次都將范圍減半禾嫉，因此效率為N+N/2+N/4+...+1，約2N次比較湃番，那么我們通過(guò)這樣的方法就能在線性時(shí)間內(nèi)確定第k大的元素是多少夭织。
4.4 對(duì)快速排序的研究和改進(jìn)
就像上面提到的，快速排序算法在誕生后由于其卓越的性能成為各大編程語(yǔ)言標(biāo)準(zhǔn)庫(kù)中不可或缺的一員吠撮，一切看上去都是那么的完美尊惰。直到1991年的一天AT&T Bell實(shí)驗(yàn)室的兩位科學(xué)家Allan Wilks和Rick Becker意外地發(fā)現(xiàn)，原本運(yùn)行幾秒鐘就能給出結(jié)果的qsort()跑了好幾分鐘才返回泥兰，這讓他們很無(wú)語(yǔ)弄屡，于是決定深入研究，他們發(fā)現(xiàn)了上述基本算法存在的問(wèn)題——若序列中出現(xiàn)重復(fù)值鞋诗，那么上述算法的效率將降低到O(N^2)膀捷。實(shí)際生活中排序的序列具有大量重復(fù)值是很常見(jiàn)的，極端情況下削彬，如果序列中記錄的值都是相同的全庸，那么上述快速排序的分區(qū)處理就會(huì)變得非常的糟糕——因?yàn)樗鼘⑺械脑厮Φ搅俗筮呅阒伲缓蟛粩嘀貜?fù)，如圖4-5所示壶笼。理想情況下神僵，當(dāng)遇到與分區(qū)界標(biāo)相同的值時(shí)，我們應(yīng)該停下來(lái)覆劈。更進(jìn)一步說(shuō)保礼，如果能將序列分區(qū)為三個(gè)部分：“左邊都是小于界標(biāo)的元素，中間都是等于界標(biāo)的元素责语，右邊都是大于界標(biāo)的元素”炮障，那就更好了。于是科學(xué)家們對(duì)快速排序進(jìn)行了改進(jìn)坤候，便有了3-way partitioning胁赢。圖4-6給出了三路分區(qū)的一個(gè)大概的示意圖☆砉眨可以看到徘键，算法執(zhí)行完成后a[lo..lt-1]都是比v小的元素；a[lt..gt]都是等于v的元素遍蟋；a[gt+1..hi]都是大于v的元素吹害。
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return;
int lt = lo, gt = hi;
Comparable v = a[lo];
int i = lo;
while (i <= gt) {
int cmp = a[i].compareTo(v);
if (cmp < 0) exch(a, lt++, i++);
else if (cmp > 0) exch(a, i, gt--);
else i++;
}
// a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
sort(a, lo, lt-1);
sort(a, gt+1, hi);
assert isSorted(a, lo, hi);
}
一開(kāi)始先將lt和gt分別初始化為lo和hi，分區(qū)界標(biāo)v初始化為a[lo]虚青，然后i從左往右遍歷它呀，每次都與v作比較。1）若a[i] < v棒厘，說(shuō)明這玩意兒應(yīng)該在a[lo..lt-1]的范圍內(nèi)纵穿，所以交換a[lt]和a[i]，然后lt和i分別自增一個(gè)單位奢人，這相當(dāng)于是把a(bǔ)[i]甩到序列的左邊谓媒；2）若a[i] > v，說(shuō)明這玩意兒應(yīng)該在a[gt+1..hi]的范圍內(nèi)何乎，于是交換a[i]和a[gt]句惯，然后gt自減一個(gè)單位，因?yàn)榻粨Q后a[i]就是原來(lái)的a[gt]支救，還沒(méi)做比較抢野，所以i不能動(dòng)；最后各墨，若a[i] == v指孤，則只增加i。若i > gt了贬堵，說(shuō)明序列已經(jīng)分區(qū)完畢恃轩，此時(shí)循環(huán)結(jié)束结洼，然后再遞歸地對(duì)a[lo..lt-1]和a[gt+1..hi]進(jìn)行排序（實(shí)質(zhì)上是重復(fù)這一分區(qū)過(guò)程）即可。圖4-7是這一分區(qū)過(guò)程的展示详恼，經(jīng)過(guò)復(fù)雜的數(shù)學(xué)分析發(fā)現(xiàn)补君，對(duì)大部分實(shí)際情況而言引几，這樣的三路快速排序都能達(dá)到線性時(shí)間的運(yùn)行效率昧互，當(dāng)序列中只有常量個(gè)不同的值，其他值都重復(fù)時(shí)伟桅，該算法的效率能做到O(N)敞掘，這真是一個(gè)了不起的進(jìn)步。
人們并沒(méi)有停下追求卓越的腳步楣铁，在上面提到過(guò)的那篇著名的論文“Engineering a Sort Function”中玖雁，Bentley和McIlroy針對(duì)實(shí)際工程中使用的排序算法做了一系列的優(yōu)化。算法的基本思想仍然采用快速排序盖腕，但是對(duì)于規(guī)模較小的子序列赫冬，使用了插入排序，分區(qū)的方法則采用了上面介紹的3-way partitioning溃列，但針對(duì)不同情況做了不同處理：對(duì)較小序列取中間位置作為分區(qū)界標(biāo)劲厌；對(duì)于中等序列則使用“median of 3”方法；對(duì)于較大的序列則使用更高端的“Tukey's ninther”方法听隐。這樣以來(lái)补鼻，原本理論化的，“純粹”的快速排序算法就被改的面目全非了雅任，但同時(shí)我們也收獲了一份能夠在遇到問(wèn)題時(shí)馬上就能用的高效算法风范。有的時(shí)候沒(méi)有選擇就是最好的選擇，這就是為什么你可以在大多數(shù)編程語(yǔ)言中輕輕松松使用sort()或者stable()就能對(duì)序列進(jìn)行排序或穩(wěn)定排序沪么，而不是在那里絞盡腦汁地糾結(jié)到底該選哪種排序算法比較好的原因硼婿。從這里可以得到一點(diǎn)點(diǎn)啟發(fā)，如果我們是標(biāo)準(zhǔn)庫(kù)的使用者禽车，那么我們只關(guān)心結(jié)果（速度快不快寇漫，結(jié)果對(duì)不對(duì)），不在乎中間過(guò)程哭当；但如果我們是標(biāo)準(zhǔn)庫(kù)的設(shè)計(jì)者猪腕，就要注意避免讓使用者去糾結(jié)，去選擇钦勘，就應(yīng)該做到高效實(shí)用陋葡，哪怕它是一個(gè)“大雜燴”一樣的排序算法。
時(shí)至今日彻采，只要你去閱讀編程語(yǔ)言排序標(biāo)準(zhǔn)庫(kù)的源代碼腐缤，你幾乎都能在注釋中看到這篇算法的身影捌归，比如圖4-8展示的Go語(yǔ)言sort包中的源代碼。不到萬(wàn)不得已或者情況特殊岭粤，完全沒(méi)有必要自己造輪子惜索，因?yàn)槟阍斐鰜?lái)的輪子未必有人家的好。那這是否就代表我們無(wú)所作為了呢剃浇？其實(shí)不是的巾兆，我們應(yīng)該想想怎樣利用好別人的東西做好自己的事情。比如Java語(yǔ)言使用Comparator接口來(lái)實(shí)現(xiàn)對(duì)同一記錄的多種排序虎囚，Go語(yǔ)言的sort包卻沒(méi)有提供這樣的功能角塑，那么我們?cè)鯓觾?yōu)雅地實(shí)現(xiàn)這一功能呢？下面這段代碼是我在Go語(yǔ)言文檔的啟發(fā)下自己編寫(xiě)的實(shí)現(xiàn)淘讥。仍然是采用回調(diào)函數(shù)的方法圃伶，但是我們定義一個(gè)multiKeySorter的結(jié)構(gòu)，它包含待排序的序列coll和比較函數(shù)lesser蒲列，然后我們定義Len()窒朋，Swap()和Less()函數(shù)，使得該結(jié)構(gòu)滿足sort包的接口蝗岖，在Less()函數(shù)中我們通過(guò)回調(diào)lesser()函數(shù)來(lái)執(zhí)行排序侥猩。這里一個(gè)比較巧妙的地方是將形如“func(o1, o2 interface{}) bool”的函數(shù)定義為By類型，然后在這個(gè)函數(shù)類型上定義“成員函數(shù)”Sort()剪侮，在Sort()函數(shù)中強(qiáng)制轉(zhuǎn)換傳入的任何同型構(gòu)函數(shù)以及待排序序列拭宁，并使用它們就地定義一個(gè)multiKeySorter結(jié)構(gòu)變量然后進(jìn)行排序。
// multiKeySorter is a kind of Sortable used for sorting according to different keys
// One can write different lesser functions for a user-defined type and call
// By(*lesser*).Sort(*coll*) to sort the collection
type multiKeySorter struct {
coll interface{}
lesser func(o1, o2 interface{}) bool
}
func (mks *multiKeySorter) Len() int {
if reflect.TypeOf(mks.coll).Kind() == reflect.Slice {
slice := reflect.ValueOf(mks.coll)
return slice.Len()
}
panic("passing a non-slice type")
}
func (mks *multiKeySorter) Swap(i, j int) {
if reflect.TypeOf(mks.coll).Kind() == reflect.Slice {
slice := reflect.ValueOf(mks.coll)
temp := reflect.ValueOf(slice.Index(i).Interface())
slice.Index(i).Set(reflect.ValueOf(slice.Index(j).Interface()))
slice.Index(j).Set(temp)
return
}
panic("passing a non-slice type")
}
func (mks *multiKeySorter) Less(i, j int) bool {
if reflect.TypeOf(mks.coll).Kind() == reflect.Slice {
slice := reflect.ValueOf(mks.coll)
return mks.lesser(slice.Index(i).Interface(), slice.Index(j).Interface())
}
panic("passing a non-slice type")
}
// By is a function type for multiple-key sorting
type By func(o1, o2 interface{}) bool
// Sort sorts the slice by lesser func passing in
func (by By) Sort(coll interface{}) {
mks := &multiKeySorter{
coll: coll,
lesser: by,
}
sort.Sort(mks)
}
func TestMultiKeySorter(t *testing.T) {
fmt.Println("====== Multi Key Sorter ======")
planets := []Planet{
{"Mercury", 0.055, 0.4},
{"Venus", 0.815, 0.7},
{"Earth", 1.0, 1.0},
{"Mars", 0.107, 1.5},
}
name := func(o1, o2 interface{}) bool {
p1 := o1.(Planet)
p2 := o2.(Planet)
return strings.ToLower(p1.name) < strings.ToLower(p2.name)
}
distance := func(o1, o2 interface{}) bool {
p1 := o1.(Planet)
p2 := o2.(Planet)
return p1.dist < p2.dist
}
mass := func(o1, o2 interface{}) bool {
p1 := o1.(Planet)
p2 := o2.(Planet)
return p1.mass < p2.mass
}
sorter.By(name).Sort(planets)
fmt.Println("By name: ", planets)
sorter.By(distance).Sort(planets)
fmt.Println("By distance: ", planets)
sorter.By(mass).Sort(planets)
fmt.Println("By mass: ", planets)
}
五. 為“排序”而生——優(yōu)先級(jí)隊(duì)列
5.1 什么是優(yōu)先級(jí)隊(duì)列
在之前的算法分析學(xué)習(xí)筆記中瓣俯，我們?cè)?jīng)介紹過(guò)兩種數(shù)據(jù)結(jié)構(gòu)——棧和隊(duì)列杰标。回想一下彩匕，棧執(zhí)行的操作是“先入后出”腔剂，它刪除的元素是總是最近插入的那個(gè)；而隊(duì)列執(zhí)行的操作是“先入先出”驼仪，它刪除的元素總是最先放進(jìn)去的那個(gè)掸犬。這里我們要介紹的優(yōu)先級(jí)隊(duì)列，采用了一種截然不同的方式來(lái)刪除元素——根據(jù)優(yōu)先級(jí)的大小绪爸。這種優(yōu)先級(jí)是人為定義的湾碎，這樣就增加了使用的靈活性，優(yōu)先級(jí)隊(duì)列也分為兩種：最大優(yōu)先級(jí)隊(duì)列每次刪除的是優(yōu)先級(jí)最高的那個(gè)元素奠货，而最小優(yōu)先級(jí)隊(duì)列每次刪除的是優(yōu)先級(jí)最低的那個(gè)元素介褥。這樣的數(shù)據(jù)結(jié)構(gòu)與我們之前接觸的排序算法有區(qū)別又有聯(lián)系：它們之間的區(qū)別是，排序算法是將整個(gè)序列重新排列有序之后再進(jìn)行處理，而優(yōu)先級(jí)隊(duì)列并不要求整體有序柔滔，但它每次刪除的元素總是從小到大或從大到小溢陪，使得優(yōu)先級(jí)隊(duì)列中的元素總是按序處理；它們之間的聯(lián)系是睛廊，優(yōu)先級(jí)隊(duì)列內(nèi)部使用的一種稱為“堆”的數(shù)據(jù)結(jié)構(gòu)直接導(dǎo)致了“堆排序”算法的誕生形真，這個(gè)后面會(huì)有詳細(xì)的講解。
優(yōu)先級(jí)隊(duì)列不負(fù)眾望超全，應(yīng)用廣泛咆霜。在數(shù)據(jù)壓縮（哈夫曼編碼）、圖搜索（Dijkstra算法和Prim算法）卵迂、人工智能（A*搜索）裕便、操作系統(tǒng)（負(fù)載均衡和中斷處理）和垃圾郵件過(guò)濾（貝葉斯分類器）中都扮演重要角色。一個(gè)最常見(jiàn)的應(yīng)用就是海量數(shù)據(jù)處理：從N個(gè)記錄中獲取最大的（或者最小的）M個(gè)記錄见咒，一般N很大M很小，沒(méi)有足夠的內(nèi)存來(lái)存放這海量的N個(gè)記錄挂疆。比如谷歌每天都會(huì)產(chǎn)生海量的搜索日志改览，要從這些數(shù)據(jù)中找出搜索頻率最高的10大關(guān)鍵詞，就是優(yōu)先級(jí)隊(duì)列的典型應(yīng)用場(chǎng)景缤言。v_July_v哥在他的“結(jié)構(gòu)之法宝当，算法之道”系列博客中有一篇博文叫《教你如何迅速秒殺掉：99%的海量數(shù)據(jù)面試題》對(duì)這一課題有精彩的研究。圖5-1展示了最大優(yōu)先級(jí)隊(duì)列的API胆萧，其中黑色部分就是優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)的最主要接口庆揩，對(duì)稱地，最小優(yōu)先級(jí)隊(duì)列只要將delMax()改為delMin()即可跌穗。
5.2 優(yōu)先級(jí)隊(duì)列的樸素實(shí)現(xiàn)
有兩種簡(jiǎn)單的方式可以實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列——用數(shù)組订晌。無(wú)序數(shù)組的實(shí)現(xiàn)在每次插入元素時(shí)只簡(jiǎn)單地將其插入到數(shù)組末端，因此效率是O(1)蚌吸，刪除元素時(shí)則需要遍歷數(shù)組求最大值锈拨，因此效率是O(N)，取最大元素的效率為O(N)羹唠；有序數(shù)組的實(shí)現(xiàn)在每次插入元素時(shí)都將元素插入到適當(dāng)?shù)奈恢檬沟脭?shù)組有序奕枢，使用類似插入排序的方法，因此效率是O(N)佩微，刪除時(shí)直接刪除數(shù)組末端的元素缝彬，因此效率是O(1)，取最大元素的效率為O(1)哺眯。同樣是使用數(shù)組谷浅，我們還可以實(shí)現(xiàn)效率更高的優(yōu)先級(jí)隊(duì)列，使得上述所有的操作都能在O(logN)時(shí)間內(nèi)完成，這就是鼎鼎大名的——二叉堆壳贪。
5.3 叫我“二叉堆”陵珍！
要理解二叉堆，首先要理解二叉樹(shù)违施，二叉樹(shù)是一種遞歸結(jié)構(gòu)互纯，它要么為空（什么都沒(méi)有，空空如也）磕蒲，要么就是一個(gè)結(jié)點(diǎn)留潦，該結(jié)點(diǎn)有左右兩個(gè)link分別指向一棵二叉樹(shù)。完全二叉樹(shù)又是一種特殊的二叉樹(shù)辣往，除了最底層可以例外兔院，其他層的結(jié)點(diǎn)都填滿了，也就是說(shuō)站削，如果我們一層一層坊萝，從左到右地創(chuàng)建二叉樹(shù)，那么就能創(chuàng)造出一棵完全二叉樹(shù)许起，它是近乎完美平衡的十偶，如圖5-2所示。只要是樹(shù)型結(jié)構(gòu)园细，我們都要注意有關(guān)樹(shù)的高度的結(jié)論惦积，因?yàn)樵跇?shù)的世界里又瘦又高并不是一種討人喜歡的身材，又矮又胖才是人見(jiàn)人愛(ài)的對(duì)象猛频，樹(shù)越矮越胖狮崩，從根結(jié)點(diǎn)走到葉子結(jié)點(diǎn)的路徑就越短÷寡埃可以通過(guò)數(shù)學(xué)歸納法進(jìn)行證明睦柴，一棵具有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)其高度為floor(lgN)，因此lgN的時(shí)間內(nèi)就能從根結(jié)點(diǎn)走到葉子結(jié)點(diǎn)烈和。而二叉堆其實(shí)就是一棵“堆有序”的完全二叉樹(shù)爱只，它分為兩種——最大堆和最小堆。最大堆中每一個(gè)結(jié)點(diǎn)都大于等于它的兩個(gè)子節(jié)點(diǎn)招刹，根節(jié)點(diǎn)是最大的恬试；而最小堆中每一個(gè)結(jié)點(diǎn)都小于等于它的兩個(gè)子節(jié)點(diǎn)，根節(jié)點(diǎn)是最小的疯暑。對(duì)完全二叉樹(shù)训柴，我們可以從根節(jié)點(diǎn)開(kāi)始從左到右，從上到下地按序標(biāo)記為1妇拯，2幻馁，3……正是因?yàn)檫@一特殊性洗鸵，所以我們可以用數(shù)組來(lái)表示二叉堆，其中下標(biāo)為0的位置空出來(lái)仗嗦，從下標(biāo)為1的位置開(kāi)始按層次存放樹(shù)的節(jié)點(diǎn)膘滨，如圖5-3所示。對(duì)完全二叉樹(shù)要牢記父節(jié)點(diǎn)和子節(jié)點(diǎn)的計(jì)算公式稀拐，對(duì)于節(jié)點(diǎn)k火邓，它的父節(jié)點(diǎn)為k/2，兩個(gè)子節(jié)點(diǎn)分別為2k和2k+1德撬，且對(duì)于一棵有N個(gè)節(jié)點(diǎn)的完全二叉樹(shù)只有左半部分（k <= N/2）節(jié)點(diǎn)有子節(jié)點(diǎn)铲咨，這在圖5-3中同樣可以得到驗(yàn)證。下面我們以最大堆為例介紹一下相關(guān)的核心算法蜓洪。
5.3.1 “上浮”和“下沉”算法
在一個(gè)最大堆中纤勒，如果一個(gè)節(jié)點(diǎn)k的值突然變得比它的父節(jié)點(diǎn)k/2大了，那么這棵二叉堆就被破壞了隆檀，恢復(fù)的辦法就是讓這個(gè)節(jié)點(diǎn)與它的父節(jié)點(diǎn)發(fā)生交換摇天，此時(shí)節(jié)點(diǎn)k相當(dāng)于“上浮”了一層，然后我們?cè)倥袛喔詹伲绻匀淮笥诟腹?jié)點(diǎn)闸翅，那么就再“上浮”一層，這個(gè)過(guò)程一直持續(xù)到根節(jié)點(diǎn)菊霜，或目標(biāo)節(jié)點(diǎn)不再比其父節(jié)點(diǎn)大為止；同樣地济赎，如果 一個(gè)節(jié)點(diǎn)k的值突然小于了它的（其中一個(gè)或兩個(gè)）子節(jié)點(diǎn)鉴逞，那么二叉堆的秩序仍然被破壞了，此時(shí)恢復(fù)的辦法正好反過(guò)來(lái)——讓節(jié)點(diǎn)k與其子節(jié)點(diǎn)2k和2k+1進(jìn)行比較司训，然后與較大的那個(gè)做交換构捡，此時(shí)節(jié)點(diǎn)k相當(dāng)于“下沉”了一層，這個(gè)過(guò)程一直持續(xù)到葉子節(jié)點(diǎn)壳猜，或目標(biāo)節(jié)點(diǎn)不再比其任何子節(jié)點(diǎn)小為止勾徽。下面的幾行代碼展示了這兩個(gè)過(guò)程，特別要注意循環(huán)的條件统扳，對(duì)于swim()喘帚，首先要判斷k > 1，這是k/2有效的條件咒钟；對(duì)于sink()吹由，只需要處理左半部分（2k <= N）即可，因?yàn)橛野氩糠侄际侨~子節(jié)點(diǎn)朱嘴，處理的過(guò)程中倾鲫，我們用j來(lái)獲取兩個(gè)子節(jié)點(diǎn)中較大的那個(gè)粗合，一旦發(fā)現(xiàn)節(jié)點(diǎn)k不再小于j即停止。
private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}
private void sink(int k) {
while (2*k <= N) {
int j = 2*k;
if (j < N && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
以上兩個(gè)過(guò)程被用在優(yōu)先級(jí)隊(duì)列的插入和刪除過(guò)程中乌昔，插入元素時(shí)隙疚，我們先將元素插入到數(shù)組末尾，然后調(diào)用swim()進(jìn)行可能的上浮操作磕道，將新節(jié)點(diǎn)調(diào)整到合適的位置供屉；刪除時(shí)，我們刪除根節(jié)點(diǎn)（最大的元素）捅厂，然后用數(shù)組最末尾的元素填補(bǔ)根節(jié)點(diǎn)的空缺贯卦，最后調(diào)用sink()進(jìn)行可能的下沉操作，恢復(fù)堆有序焙贷。兩種操作都是在根節(jié)點(diǎn)到某一葉子節(jié)點(diǎn)的路徑上操作撵割，所以效率都是O(lgN)，圖5-4和圖5-5分別演示了這一過(guò)程辙芍。下面的代碼展示了最大堆的插入和刪除啡彬。
public void insert(Key x) {
// double size of array if necessary
if (N >= pq.length - 1) resize(2 * pq.length);
// add x, and percolate it up to maintain heap invariant
pq[++N] = x;
swim(N);
assert isMaxHeap();
}
public Key delMax() {
if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
Key max = pq[1];
exch(1, N--);
sink(1);
pq[N+1] = null; // to avoid loiterig and help with garbage collection
if ((N > 0) && (N == (pq.length - 1) / 4)) resize(pq.length / 2);
assert isMaxHeap();
return max;
}
如果要實(shí)現(xiàn)最小優(yōu)先級(jí)隊(duì)列（最小堆），那其實(shí)很簡(jiǎn)單故硅，只要把less()函數(shù)改為greater()函數(shù)即可庶灿，這樣就變成了小的元素“上浮”，大的元素“下沉”吃衅，根節(jié)點(diǎn)存儲(chǔ)的是最小的元素往踢。有感于此，我們給出了一個(gè)統(tǒng)一的Go語(yǔ)言實(shí)現(xiàn)徘层，比起Java實(shí)現(xiàn)來(lái)說(shuō)它有兩個(gè)優(yōu)勢(shì)：首先峻呕，Go語(yǔ)言的“切片”類型相當(dāng)于動(dòng)態(tài)數(shù)組，我們不用考慮對(duì)數(shù)組重新調(diào)整大小的問(wèn)題趣效；其次瘦癌，通過(guò)傳入比較函數(shù)我們可以用同一套代碼生成最大優(yōu)先級(jí)隊(duì)列和最小優(yōu)先級(jí)隊(duì)列；它的缺點(diǎn)是需要使用者自己去記住創(chuàng)建的是最大優(yōu)先級(jí)隊(duì)列還是最小優(yōu)先級(jí)隊(duì)列跷敬。
package cntr
import (
"fmt"
)
type PQueue struct {
keys []interface{}
length int
compare func(interface{}, interface{}) bool
}
func NewPQ(cmp func(interface{}, interface{}) bool) *PQueue {
// arr[0] not use
arr := make([]interface{}, 1)
arr[0] = 0
return &PQueue{
keys: arr,
compare: cmp,
}
}
func (pq *PQueue) Insert(v interface{}) {
pq.keys = append(pq.keys, v)
pq.length++
pq.swim(pq.length)
}
func (pq *PQueue) swim(k int) {
for k > 1 && pq.compare(pq.keys[k/2], pq.keys[k]) {
pq.keys[k/2], pq.keys[k] = pq.keys[k], pq.keys[k/2]
k = k / 2
}
}
func (pq *PQueue) pq() interface{} {
if pq.Empty() {
panic(fmt.Sprintf("queue is empty"))
}
return pq.keys[1]
}
func (pq *PQueue) PrintOut() {
fmt.Println(pq.keys[1:])
}
func (pq *PQueue) Del() interface{} {
if pq.Empty() {
panic(fmt.Sprintf("Trying to delete an empty queue"))
}
ret := pq.keys[1]
pq.keys[1] = pq.keys[pq.length]
pq.keys = pq.keys[:pq.length]
pq.length--
pq.sink(1)
return ret
}
func (pq *PQueue) sink(k int) {
for 2*k <= pq.length {
j := 2 * k
if j < pq.length && pq.compare(pq.keys[j], pq.keys[j+1]) {
j++
}
if !pq.compare(pq.keys[k], pq.keys[j]) {
break
}
pq.keys[k], pq.keys[j] = pq.keys[j], pq.keys[k]
k = j
}
}
func (pq *PQueue) IsHeapified() bool {
k := 1
for 2*k <= pq.length {
j := 2 * k
if pq.compare(pq.keys[k], pq.keys[j]) || (j < pq.length && pq.compare(pq.keys[k], pq.keys[j+1])) {
return false
}
k++
}
return true
}
func (pq *PQueue) Empty() bool {
return pq.length == 0
}
func (pq *PQueue) Size() int {
return pq.length
}
5.4 又一個(gè)神一樣的存在——堆排序
通過(guò)二叉堆讯私，我們又誕生了一個(gè)偉大的算法——堆排序。我個(gè)人認(rèn)為西傀，最經(jīng)典的排序算法斤寇，非歸并排序，快速排序和堆排序莫屬池凄，對(duì)她們算法性能的改進(jìn)傾注了無(wú)數(shù)科學(xué)家的心血抡驼，她們解決問(wèn)題的思想被大量地借鑒用于解決其他問(wèn)題，她們?cè)跓o(wú)數(shù)計(jì)算問(wèn)題中發(fā)揮的基礎(chǔ)作用深刻影響了科技的發(fā)展肿仑。堆排序是一種就地排序算法致盟，不需要占用額外的數(shù)組空間碎税，因此它的空間效率比歸并排序要好，與此同時(shí)堆排序最壞情況下的時(shí)間效率是O(NlgN)馏锡，這點(diǎn)她又比快速排序強(qiáng)雷蹂，后者只能保證平均情況。因此堆排序也是一個(gè)最優(yōu)的比較排序算法杯道，只可惜它并不是穩(wěn)定的匪煌，而且由于移動(dòng)的距離比較大，它對(duì)緩存并不友好党巾。
堆排序的思想很容易解釋萎庭，首先該算法會(huì)在輸入序列的基礎(chǔ)上重建最大堆，然后不停地刪除最大值齿拂，將其與數(shù)組末尾元素交換驳规，直到處理完全部序列，如圖5-6所示署海。下面的代碼展示了對(duì)一個(gè)整型切片進(jìn)行堆排序的Go語(yǔ)言實(shí)現(xiàn)吗购。HeapSort()中的第一個(gè)for循環(huán)在數(shù)組上建堆，它是一個(gè)自底向上的過(guò)程砸狞。我們將數(shù)組中每一個(gè)元素看作以它為根節(jié)點(diǎn)的子二叉堆捻勉，首先我們認(rèn)為所有大小為1的子堆（葉子節(jié)點(diǎn)）都是堆有序的，之前我們提到過(guò)堆的數(shù)組表示有個(gè)性質(zhì)刀森，即數(shù)組右半部分都是葉子節(jié)點(diǎn)踱启，因此我們從N/2的位置開(kāi)始從右往左遍歷，調(diào)用下沉函數(shù)sink()建堆研底，當(dāng)k = 1時(shí)執(zhí)行最后一次建堆并結(jié)束循環(huán)禽捆，此時(shí)整個(gè)數(shù)組構(gòu)建成了一個(gè)二叉堆，如圖5-7所示飘哨。緊接著在第二個(gè)循環(huán)中，我們不斷地將堆中第一個(gè)元素（最大值）放到最后一個(gè)元素的位置上琐凭，最后一個(gè)元素放到第一個(gè)位置上芽隆，遞減N的值（此時(shí)堆的大小減一），然后調(diào)用sink()恢復(fù)堆有序统屈，因?yàn)樗惴看味紝⒆畲蟮脑胤诺阶詈笠粋€(gè)位置并遞減堆的大小胚吁，因此該算法執(zhí)行完成后數(shù)組就是有序的，如圖5-8所示愁憔。有一個(gè)處理細(xì)節(jié)要引起注意腕扶，因?yàn)槲覀兣判虻臄?shù)組是從下標(biāo)0開(kāi)始的，而最大堆是從下標(biāo)1開(kāi)始的吨掌，所以在實(shí)現(xiàn)lesser()函數(shù)和excher()函數(shù)的時(shí)候要注意在下標(biāo)上做減一處理半抱，其他地方不變脓恕。
func HeapSort(arr []int) {
N := len(arr)
for k := N / 2; k >= 1; k-- {
sink(arr, k, N)
}
for N > 1 {
excher(arr, 1, N)
N--
sink(arr, 1, N)
}
}
func sink(arr []int, k, N int) {
for 2*k <= N {
j := 2 * k
if j < N && lesser(arr, j, j+1) {
j++
}
if !lesser(arr, k, j) {
break
}
excher(arr, k, j)
k = j
}
}
func lesser(arr []int, i, j int) bool {
return arr[i-1] < arr[j-1]
}
func excher(arr []int, i, j int) {
arr[i-1], arr[j-1] = arr[j-1], arr[i-1]
}
六. 排序算法的學(xué)以致用
就這樣，我們?cè)诓欢嗟钠锝榻B了多種排序算法窿侈，從最基礎(chǔ)的選擇排序炼幔，插入排序和Shell排序，到經(jīng)典的歸并排序史简，快速排序乃秀，再到為排序而生的優(yōu)先級(jí)隊(duì)列，以及堆排序圆兵。世界上存在有上百種千奇百怪的排序算法跺讯，這里能夠介紹到的算法只是滄海之一粟，但是了解游戲規(guī)則殉农，理解它們的思想對(duì)于學(xué)習(xí)其他算法以及解決實(shí)際問(wèn)題都是很有幫助的刀脏，圖6-1以表格的形式歸納了我們學(xué)習(xí)過(guò)的七種算法以及它們具有的性質(zhì)。下面统抬，我們就拋磚引玉火本，來(lái)看看排序算法的應(yīng)用。
6.1 學(xué)以致用之一：歸約思想
課本上介紹了一種叫做“歸約”（Reductions）的重要思想——其實(shí)它就是我們常說(shuō)的“舉一反三”啦聪建！怎么說(shuō)呢钙畔？歸約就是用解決一個(gè)問(wèn)題的算法去解決另一個(gè)問(wèn)題。如果一個(gè)問(wèn)題中的對(duì)象只有在有序時(shí)才能很容易地解決金麸，那么我們就說(shuō)我們將這個(gè)問(wèn)題“歸約”為一個(gè)排序問(wèn)題來(lái)解決擎析。例如在第一篇學(xué)習(xí)筆記中介紹的二叉搜索算法，它能夠在對(duì)數(shù)時(shí)間內(nèi)查找目標(biāo)元素挥下，但前提是該序列是有序的揍魂。下面我們來(lái)看看都有哪些問(wèn)題可以歸約為一個(gè)排序問(wèn)題。
6.1.1 重復(fù)元素
序列中有多少元素是重復(fù)的棚瘟？序列中哪個(gè)元素出現(xiàn)的最頻繁现斋？怎樣去除隊(duì)列中的重復(fù)元素？這些問(wèn)題當(dāng)序列是無(wú)序時(shí)很難回答偎蘸，而當(dāng)序列有序時(shí)就簡(jiǎn)單多了庄蹋，因?yàn)榕判蚝笾貜?fù)的元素都會(huì)靠在一起。這類問(wèn)題是算法面試題中的趁匝客限书，如果沒(méi)有限制，我們還可以用額外的存儲(chǔ)空間章咧，比如一個(gè)散列表去統(tǒng)計(jì)倦西，這樣無(wú)需序列有序；若題目要求不準(zhǔn)使用額外的空間時(shí)赁严，就需要對(duì)序列先進(jìn)行排序然后再處理扰柠。
6.1.2 逆序數(shù)
就像上面提到過(guò)的那樣粉铐，逆序數(shù)是指一個(gè)序列中的有序?qū)?a, b)的個(gè)數(shù)，其中a > b耻矮。仔細(xì)想一想秦躯，我們排序的過(guò)程就是逐步消除逆序數(shù)的過(guò)程，因此稍加改造就能在排序的過(guò)程中求得序列的逆序數(shù)裆装。一個(gè)經(jīng)典的辦法是改造歸并排序踱承，在歸并的過(guò)程中若發(fā)現(xiàn)左子序列當(dāng)前元素大于右子序列當(dāng)前元素，就能根據(jù)右子序列元素個(gè)數(shù)得到逆序哨免，這是一個(gè)經(jīng)典面試題的經(jīng)典解法茎活。
6.1.3 中位數(shù)與順序統(tǒng)計(jì)學(xué)
這個(gè)也在之前提到過(guò)了，在統(tǒng)計(jì)學(xué)和其他數(shù)據(jù)處理應(yīng)用中應(yīng)用較為廣泛琢唾。它借鑒了快速排序的分區(qū)算法的思想载荔，在不需要完全排序的情況下就能找到第k小的元素，且算法能夠在線性時(shí)間內(nèi)運(yùn)行完畢采桃，然而它是一種隨機(jī)化的算法——處理之前需要進(jìn)行一次隨機(jī)排序懒熙，因此該運(yùn)行效率是平均情況。
6.2 學(xué)以致用之二：人工智能問(wèn)題中的優(yōu)先級(jí)隊(duì)列
這里要介紹的是優(yōu)先級(jí)隊(duì)列在人工智能問(wèn)題中的應(yīng)用——8 puzzle謎題普办，問(wèn)題的完整定義和描述詳見(jiàn)http://introcs.cs.princeton.edu/java/assignments/8puzzle.html工扎。這一問(wèn)題于1870年由Sam Loyd給出：在一個(gè)33的格子上有8個(gè)方塊和1個(gè)空缺，這8個(gè)方塊從1編號(hào)到8衔蹲，我們的任務(wù)是利用這個(gè)空缺或水平或垂直地移動(dòng)這些方塊肢娘，盡量用最少的移動(dòng)使得它們有序，圖6-2展示了一個(gè)例子舆驶。
這個(gè)問(wèn)題可以利用人工智能中著名的A Search算法進(jìn)行求解橱健，首先我們定義一個(gè)三元組，它由棋盤(pán)當(dāng)前狀態(tài)board沙廉，走到此位置要用的移動(dòng)數(shù)moves拘荡，以及之前的狀態(tài)prev組成。起始狀態(tài)為(board, 0, NULL)撬陵，其中board是人為輸入的初始狀態(tài)俱病。我們將起始狀態(tài)塞入最小優(yōu)先級(jí)隊(duì)列，每次都取出優(yōu)先級(jí)最小的三元組袱结，然后將它的“鄰居們”（所有只移動(dòng)一步就能達(dá)到的棋盤(pán)）插入優(yōu)先級(jí)隊(duì)列（要注意將與之前狀態(tài)prev相同的情況排除掉），此過(guò)程一直持續(xù)到彈出的三元組為最終狀態(tài)途凫，此時(shí)我們將根據(jù)它以及它的prev指針重建整個(gè)步驟序列作為算法的解垢夹。有三個(gè)關(guān)鍵的問(wèn)題要解決：1.優(yōu)先級(jí)怎么定義；2.如何判別棋盤(pán)走到了最終態(tài)维费；3.如何判別初始狀態(tài)是可解的果元；
這里我們有兩種方法來(lái)定義優(yōu)先級(jí)：Hamming優(yōu)先級(jí)函數(shù)和Manhattan優(yōu)先級(jí)函數(shù)：前者定義為當(dāng)前棋盤(pán)狀態(tài)中放錯(cuò)位置的方塊數(shù)加上從初始狀態(tài)走到這一狀態(tài)要用的移動(dòng)數(shù)促王，直觀地看，放錯(cuò)位置的方塊數(shù)越少該狀態(tài)就越接近最終狀態(tài)而晒；后者定義為方塊與其最終位置的距離和（包括橫向和縱向）蝇狼，加上從初始狀態(tài)走到這一狀態(tài)要用的移動(dòng)數(shù)，圖6-3展示了這兩種優(yōu)先級(jí)函數(shù)的計(jì)算倡怎。因此優(yōu)先級(jí)隊(duì)列里的三元組都是以這兩個(gè)函數(shù)任意一個(gè)的計(jì)算值為優(yōu)先級(jí)排列的迅耘。不管使用哪一個(gè)優(yōu)先級(jí)函數(shù)，要從某一初始位置走到最終位置监署，移動(dòng)的步數(shù)至少是優(yōu)先級(jí)函數(shù)的輸出值（對(duì)Hamming颤专，放錯(cuò)位置的方塊至少要移動(dòng)一步；對(duì)Manhattan钠乏，放錯(cuò)位置的方塊至少要移動(dòng)曼哈頓距離才能走到最終位置）栖秕，因此當(dāng)我們從優(yōu)先級(jí)隊(duì)列中取出一個(gè)三元組時(shí)，我們就找到了從初始狀態(tài)走到這一狀態(tài)的一系列最小步驟晓避，當(dāng)Hamming距離或Manhattan距離為0時(shí)簇捍，此三元組即為最終態(tài)。
剩下的最后一個(gè)問(wèn)題就是要搞清楚初始狀態(tài)是不是可解的俏拱，棋盤(pán)狀態(tài)分為兩種：一種能夠通過(guò)移動(dòng)走到最終態(tài)（可解）暑塑；另一種不能（不可解）但隨機(jī)交換相鄰方塊則可解，那么我們就能夠在兩個(gè)棋盤(pán)狀態(tài)上同時(shí)運(yùn)行A* Search算法彰触，一個(gè)是初始棋盤(pán)梯投，一個(gè)是交換了任意相鄰方塊的棋盤(pán)，若后者得解則立即返回前者不可解况毅，若前者得解則構(gòu)造解的序列（使用堆棧）分蓖，下面給出的是核心代碼，完整實(shí)現(xiàn)請(qǐng)參考Solver.java和Board.java
public Solver(Board initial) {
solvable = false;
solutions = null;
M = -1;
MinPQ<SNode> nq = new MinPQ<SNode>();
MinPQ<SNode> tq = new MinPQ<SNode>();
nq.insert(new SNode(initial));
tq.insert(new SNode(initial.twin()));
while (!nq.isEmpty() && !tq.isEmpty()) {
SNode n = nq.delMin();
SNode t = tq.delMin();
// test if we have reached the goal
if (t.board.manhattan() == 0) break;
if (n.board.manhattan() == 0) {
// rebuild the solutions
solutions = new Stack<Board>();
solutions.push(n.board);
solvable = true;
M = n.moves;
SNode prev = n.previous;
while (prev != null) {
solutions.push(prev.board);
M += prev.moves;
prev = prev.previous;
}
break;
}
// putting neighbors into queues
for (Board nbr : n.board.neighbors())
if (n.previous == null || !n.previous.board.equals(nbr))
nq.insert(new SNode(nbr, n.moves + 1, n));
for (Board tbr : t.board.neighbors())
if (t.previous == null || !t.previous.board.equals(tbr))
tq.insert(new SNode(tbr, t.moves + 1, t));
}
}
