大話數據結構 [溢彩加強版]

《大話數據結構【溢彩加強版】》以一個電腦教師的教學過程為場景，講解數據結構和相關算法的知識。全書以趣味方式來敘述，大量引用各種各樣的生活知識來類比，並充分運用全彩色圖形語言來解讀抽象內容，對數據結構所涉及的一些經典算法做出逐行分析、多算法比較。與同類圖書相比，《大話數據結構【溢彩加強版】》內容有趣易讀，算法講解細致深入，是一本非常適合自學的讀物。 對於學習數據結構來說，難點之一是對相關算法的理解。《大話數據結構【溢彩加強版】》創新性地採用全彩印刷，圖表、流程、代碼等內容結合色彩來重新進行約定和歸納，使得對一些難以理解的知識點的解析更加清晰順暢，極大提升了閱讀體驗。 《大話數據結構【溢彩加強版】》主要內容包含：數據結構介紹、算法推導大O階的方法；順序結構與鏈式結構差異、棧與隊列的應用；串的樸素模式匹配、KMP模式匹配算法；二叉樹前中後序遍歷、哈夫曼樹及應用；圖的深度、廣度遍歷；最小生成樹兩種算法、最短路徑兩種算法；拓撲排序與關鍵路徑算法；折半查找、插值查找、斐波那契查找等靜態查找；稠密索引、分塊索引、倒排索引等索引技術；二叉排序樹、平衡二叉樹等動態查找；B樹、B+樹技術，散列表技術；冒泡、選擇、插入等簡單排序；希爾、堆、歸並、快速等改進排序。 《大話數據結構【溢彩加強版】》適合學過一門編程語言的各類讀者，包括在讀的大中專電腦專業學生、想轉行做開發的非專業人員、欲考電腦專業研究生的應屆生或在職人員，以及工作後需要補學或溫習數據結構和算法的程序員等。

程杰，一个被读者誉为很适合写IT技术书的家伙。

著有 《大话设计模式》（简体版销量破25万册、繁体版印刷12次，开创了一种适合国人阅读的趣味讲解IT知识的风格与模式）。

作者参与过政府、证券、游戏、交通等多种行业的软件开发及项目管理工作，也曾做过软件培训的教师，目前从事教育类APP/微信小程序的开发与运营。因为有过两年半高中数学教学的独特经历，使得其书作当中处处以初学者视角考虑和分析问题，成为了当前很受欢迎的IT技术图书作者之一。

目錄

第1章   數據結構緒論 1
1.1　開場白 2
如果你交給某人一個程序，你將折磨他一整天；如果你教某人如何編寫程序，你將折磨他一輩子。
1.2　你數據結構怎麽學的 3
他完成開發並測試通過後，得意地提交了代碼。項目經理看完代碼後拍著桌子對他說：“你數據結構是怎麽學的？”
1.3　數據結構起源 4
1.4　基本概念和術語 5
正所謂“巧婦難為無米之炊”，再強大的電腦，也要有“米”下鍋才可以乾活，否則就是一堆破銅爛鐵。這個“米”就是數據。
1.4.1   數據 5
1.4.2   數據元素 6
1.4.3   數據項 7
1.4.4   數據對象 7
1.4.5   數據結構 7
1.5　邏輯結構與物理結構 8
1.5.1   邏輯結構 8
1.5.2   物理結構 9
1.6　數據類型 11
大家都需要房子住，但顯然沒錢考慮大房子是沒有意義的。於是商品房就出現了各種各樣的戶型，有幾百平米的別墅，也有僅兩平米的膠囊公寓……
1.6.1   數據類型定義 11
1.6.2   抽象數據類型 12
1.7　總結回顧 13
1.8　結尾語 14
最終的結果一定是，你對著別人很牛地說“數據結構——就那麽回事。”

第2章　算法 15
2.1　開場白 16
2.2　數據結構與算法的關系 16
電腦界的前輩們，是一幫很牛很牛的人，他們使得很多看似沒法解決或者很難解決的問題，處理得如此美妙和神奇。
2.3　兩種算法的比較 17
高斯在上小學的一天，老師要求每個學生都計算1+2+…+100的結果，誰先算出來誰先回家……
2.4　算法定義 18
現實世界中的算法千變萬化，沒有通用算法可以解決所有問題。甚至一個小問題，某個解決此類問題很優秀的算法卻未必就適合它。
2.5　算法的特性 19
2.5.1   輸入輸出 19
2.5.2   有窮性 19
2.5.3   確定性 20
2.5.4   可行性 20
2.6　算法設計的要求 20
求100個人的高考成績平均分與求全省所有考生的成績平均分在占用時間和內存存儲上有非常大的差異，我們自然追求高效率和低存儲的算法來解決問題。
2.6.1   正確性 21
2.6.2   可讀性 21
2.6.3   健壯性 21
2.6.4   時間效率高和存儲量低 22
2.7　算法效率的度量方法 22
隨著n值越來越大，它們在時間效率上的差異也就越來越大。好比有些人每天都在學習，而有些人，打打游戲、睡睡大覺，畢業後前者名企爭著要，後者求職處處無門。
2.7.1   事後統計方法 22
2.7.2   事前分析估算方法 23
2.8　函數的漸近增長 25
2.9　算法時間復雜度 27
理解大O階推導不算難，難的其實是對數列的一些相關運算，這考查的更多是數學知識和能力。
2.9.1   算法時間復雜度定義 27
2.9.2   推導大O階方法 28
2.9.3   常數階 28
2.9.4   線性階 29
2.9.5   對數階 29
2.9.6   平方階 29
2.10　常見的時間復雜度 31
有些時候，告訴你某些東西不可以去嘗試，也是一種知識的傳遞。總不能非要去被毒蛇咬一口才知道蛇不可以招惹吧。
2.11　最壞情況與平均情況 32
2.12　算法空間復雜度 33
事先建立一個有2050個元素的數組，然後把所有年份按下標數字對應，如果是閏年，此數組項的值就是1，如果不是就是0。這樣，所謂的判斷某一年是否是閏年就變成了查找這個數組的某一項的值是多少的問題。
2.13　總結回顧 34
2.14　結尾語 35
愚公移山固然可敬，但發明炸藥和推土機，可能更加實在和聰明。

第3章　線性表 37
3.1　開場白 38
門外家長都擠在大門口與門里的小孩子的井然有序，形成了鮮明對比。哎，有時大人的所作所為，其實還不如孩子。
3.2　線性表的定義 39
有時我們想知道某個小朋友（比如麥兜）是否是班級的同學，老師會告訴我說，沒有，麥兜是在春田花花幼兒園里。這種查找某個元素是否存在的操作很常用。
3.3　線性表的抽象數據類型 41
3.4　線性表的順序存儲結構 43
他每次一吃完早飯就沖著去了圖書館，挑一個好地兒，把他書包里的書，一本一本地按座位放好，長長一排，九個座硬是被他占了。
3.4.1   順序存儲定義 43
3.4.2   順序存儲方式 43
3.4.3   數據長度與線性表長度的區別 44
3.4.4   地址計算方法 45
3.5　順序存儲結構的插入與刪除 46
春運時去買火車票，大家都排著隊好好的，這時來了一個美女：“可否讓我排在你前面？”這可不得了，後面的人像蠕蟲一樣，全部都得退後一步。
3.5.1   獲得元素操作 46
3.5.2   插入操作 46
3.5.3   刪除操作 47
3.5.4   線性表順序存儲結構的優缺點 49
3.6　線性表的鏈式存儲結構 49
反正也是要讓相鄰元素間留有足夠餘地，那乾脆所有元素都不要考慮相鄰位置了，哪有空位就到哪裡。而只是讓每個元素知道它下一個元素的位置在哪裡。
3.6.1   順序存儲結構不足的解決辦法 49
3.6.2   線性表鏈式存儲結構定義 50
3.6.3   頭指針與頭結點的異同 52
3.6.4   線性表鏈式存儲結構代碼描述 52
3.7　單鏈表的讀取 53
3.8　單鏈表的插入與刪除 54
本來是爸爸左手牽著媽媽的手、右手牽著寶寶的手在馬路邊散步。突然迎面走來一美女，爸爸失神般地望著，此情景被媽媽逮個正著，於是扯開父子倆，拉起寶寶的左手就快步朝前走去。
3.8.1   單鏈表的插入 54
3.8.2   單鏈表的刪除 56
3.9　單鏈表的整表創建 58
3.10　單鏈表的整表刪除 60
3.11　單鏈表結構與順序存儲結構的優缺點 61
3.12　靜態鏈表 62
對於一些語言，如Basic、Fortran等早期的編程高級語言，由於沒有指針，這鏈表結構，按照前面我們的講法，它就沒法實現了。怎麽辦呢？
3.12.1   靜態鏈表的插入操作 64
3.12.2   靜態鏈表的刪除操作 65
3.12.3   靜態鏈表的優缺點 67
3.13　循環鏈表 67
這個輪回的思想很有意思。它強調了不管你今生是窮是富，如果持續行善積德，下輩子就會好過，反之就會遭到報應。
3.14　雙向鏈表 70
就像每個人的人生一樣，欲收獲就得付出代價。雙向鏈表既然是比單鏈表多瞭如可以反向遍歷查找等的數據結構，那麽也就需要付出一些小的代價。
3.15　總結回顧 72
3.16　結尾語 73
如果你覺得上學讀書是受罪，假設你可以活到80歲，其實你最多也就吃了20年苦。用人生四分之一的時間來換取其餘時間的幸福生活，這點苦不算啥。

第4章　棧與隊列 75

 

4.1　開場白 76

想想看，在你準備用槍的時候，突然這手槍明明有子彈卻打不出來，這不是要命嗎。

4.2　棧的定義 76

類似的很多軟件，比如Word、Photoshop等，都有撤銷（undo）的操作，也是用棧這種思想方式來實現的。

4.2.1?棧的定義 76

4.2.2?進棧出棧變化形式 78

4.3　棧的抽象數據類型 78

4.4　棧的順序存儲結構及實現 79

4.4.1?棧的順序存儲結構 79

4.4.2?棧的順序存儲結構——進棧操作 80

4.4.3?棧的順序存儲結構——出棧操作 81

4.5　兩棧共享空間 81

兩個大學室友畢業同時到北京工作，他們都希望租房時能找到獨自住的一室或一室一廳，可找來找去發現，價格實在是承受不起。

4.6　棧的鏈式存儲結構及實現 83

4.6.1?棧的鏈式存儲結構 83

4.6.2?棧的鏈式存儲結構——進棧操作 84

4.6.3?棧的鏈式存儲結構——出棧操作 85

4.7　棧的作用 85

4.8　棧的應用——遞歸 86

當你往鏡子前面一站，鏡子裡面就有一個你的圖像。但你試過兩面鏡子一起照嗎？如果A、B兩面鏡子相互面對面放著，你往中間一站，嘿，兩面鏡子里都有你的千百個“化身”。

4.8.1?斐波那契數列的實現 86

4.8.2?遞歸的定義 88

4.9　棧的應用——四則運算表達式求值 89

4.9.1?後綴（逆波蘭）表示法的定義 89

4.9.2?後綴表達式的計算結果 90

4.9.3?中綴表達式轉後綴表達式 92

4.10　隊列的定義 93

電腦有時會處於疑似死機的狀態。就當你失去耐心，打算Reset時，突然它像酒醒了一樣，把你剛才單擊的所有操作全部都按順序執行了一遍。

4.11　隊列的抽象數據類型 94

4.12　循環隊列 95

你上了公交車發現前排有兩個空座位，而後排所有座位都已經坐滿，你會怎麽做？立馬下車，並對自己說，後面沒座了，我等下一輛？沒這麽笨的人，前面有座位，當然也是可以坐的。

4.12.1?隊列順序存儲的不足 95

4.12.2?循環隊列的定義 96

4.13　隊列的鏈式存儲結構及實現 99

4.13.1?隊列的鏈式存儲結構——入隊

　　　   操作 100

4.13.2?隊列的鏈式存儲結構——出隊

　　　   操作 100

4.14　總結回顧 101

4.15　結尾語 102

人生，需要有隊列精神的體現。南極到北極，不過是南緯90°到北緯90°的隊列，如果你中途猶豫，臨時轉向，也許你就只能和企鵝相伴永遠。可事實上，無論哪個方向，只要你堅持到底，你都可以到達終點。

第5章　串 103

      

5.1　開場白 104

“枯眼望遙山隔水，往來曾見幾心知？壺空怕酌一杯酒，筆下難成和韻詩。途路阻人離別久，訊音無雁寄回遲。孤燈夜守長寥寂，夫憶妻兮父憶兒。”……可再仔細一讀發現，這首詩竟然可以倒過來讀。

5.2　串的定義 104

我所提到的over、end、lie其實就是lover、friend、believe這些單詞字符串的子串。

5.3　串的比較 105

5.4　串的抽象數據類型 107

5.5　串的存儲結構 108

感情上發生了問題，為了向女友解釋一下，我準備發一條短信，一共打了75個字。最後8個字是“我恨你是不可能的”，點發送。後來得知對方收到的，只有70個字，短信結尾是“……我恨你”。

5.5.1?串的順序存儲結構 108

5.5.2?串的鏈式存儲結構 109

5.6　樸素的模式匹配算法 110

主串為S=“00000000000000000000000000000000000000000000000001”，而要匹配的子串為T=“0000000001”，……在匹配時，每次都得將T中字符循環到最後一位才發現，哦，原來它們是不匹配的。

5.7　KMP模式匹配算法 113

很多年前我們的科學家覺得像這種有多個0和1重復字符的字符串，卻需要挨個遍歷的算法，是非常糟糕的事情。

5.7.1?KMP模式匹配算法的原理 113

5.7.2?next數組值的推導 116

5.7.3?KMP模式匹配算法的實現 117

5.7.4?KMP模式匹配算法的改進 119

5.7.5?nextval數組值的推導 120

5.8　總結回顧 122

5.9　結尾語 122

《璇璣圖》共八百四十字，縱橫各二十九字，縱、橫、斜、交互、正、反讀或退一字、迭一字讀均可成詩，詩有三、四、五、六、七言不等，目前有人統計可組成七千九百五十八首詩。聽清楚哦，是7958首。

第6章　樹 125

 

6.1　開場白 126

無論多高多大的樹，那也是從小到大，由根到葉，一點點成長起來的。俗話說“十年樹木，百年樹人”，可一棵大樹又何止是十年這樣容易。

6.2　樹的定義 126

樹的定義其實就是我們在講解棧時提到的遞歸的方法。也就是在樹的定義之中還用到了樹的概念，這是比較新的一種定義方法。

6.2.1?結點的分類 127

6.2.2?結點間的關系 128

6.2.3?樹的其他相關概念 129

6.3　樹的抽象數據類型 129

6.4　樹的存儲結構 130

6.4.1?雙親表示法 130

6.4.2?孩子表示法 133

6.4.3?孩子兄弟表示法 136

6.5　二叉樹的定義 137

蘇東坡曾說：“人有悲歡離合，月有陰晴圓缺，此事古難全”。意思就是完美是理想，不完美才是人生。我們通常舉的例子也都是左高右低、參差不齊的二叉樹。那是否存在完美的二叉樹呢？

6.5.1?二叉樹的特點 139

6.5.2?特殊二叉樹 140

6.6　二叉樹的性質 142

6.6.1?二叉樹的性質1 142

6.6.2?二叉樹的性質2 143

6.6.3?二叉樹的性質3 143

6.6.4?二叉樹的性質4 144

6.6.5?二叉樹的性質5 144

6.7　二叉樹的存儲結構 145

6.7.1?二叉樹的順序存儲結構 145

6.7.2?二叉鏈表 146

6.8　遍歷二叉樹 147

你人生的道路上，高考填志願要面臨哪個城市、哪所大學、具體專業等選擇，由於選擇方式的不同，遍歷的次序就完全不同。

6.8.1?二叉樹的遍歷原理 147

6.8.2?二叉樹的遍歷方法 148

6.8.3?前序遍歷算法 150

6.8.4?中序遍歷算法 153

6.8.5?後序遍歷算法 156

6.8.6?推導遍歷結果 156

6.9　二叉樹的建立 158

6.10　線索二叉樹 159

我們現在提倡節約型社會，一切都應該節約為本。對待我們的程序當然也不例外，能不浪費的時間或空間，都應該考慮節約。

6.10.1?線索二叉樹的原理 159

6.10.2?線索二叉樹結構的實現 162

6.11　樹、森林與二叉樹的轉換 165

有個鄉鎮企業也買了同樣的生產線，老闆發現這個問題後找了個小工來說：你必須搞定，不然炒你魷魚。小工很快想出了辦法：他在生產線旁邊放了台風扇猛吹，空皂盒自然會被吹走。

6.11.1?樹轉換為二叉樹 166

6.11.2?森林轉換為二叉樹 167

6.11.3?二叉樹轉換為樹 168

6.11.4?二叉樹轉換為森林 169

6.11.5?樹與森林的遍歷 170

6.12　哈夫曼樹及其應用 171

壓縮而不出錯是如何做到的呢？簡單地說，就是把我們要壓縮的文本進行重新編碼，以達到減少不必要的空間的技術。壓縮和解壓縮技術就是基於哈夫曼的研究之上發展而來，我們應該記住他。

6.12.1?哈夫曼樹 171

6.12.2?哈夫曼樹的定義與原理 173

6.12.3?哈夫曼編碼 176

6.13　總結回顧 177

6.14　結尾語 178

人受傷時會流下淚水。樹受傷時，天將不會哭。希望我們的未來不要僅僅是鋼筋水泥建造的高樓，也要有那鬱鬱蔥蔥的森林和草地，我們人類才可能與自然和諧共處。

第7章　圖 181

 

7.1　開場白 182

如果你不善於規劃，很有可能就會出現如玩好新疆後到海南，然後再沖向黑龍江這樣的荒唐決策。

7.2　圖的定義 182

現實中，人與人之間的關系非常復雜，比如我認識的朋友，可能他們之間也互相認識，這就不是簡單的一對一、一對多的關系了，這就是我們今天要研究的主題——圖。

7.2.1?各種圖的定義 183

7.2.2?圖的頂點與邊間的關系 185

7.2.3?連通圖的相關術語 187

7.2.4?圖的定義與術語總結 189

7.3　圖的抽象數據類型 190

7.4　圖的存儲結構 191

因為美國的黑夜就是中國的白天，利用互聯網，他的員工白天上班就可以監控到美國倉庫夜間的實際情況，如果發生了像火災、偷盜這樣的突發事件，及時打電話給美國當地相關人員進行處理。

7.4.1?鄰接矩陣 192

7.4.2?鄰接表 195

7.4.3?十字鏈表 198

7.4.4?鄰接多重表 199

7.4.5?邊集數組 201

7.5　圖的遍歷 202

我有一天早晨準備出門，發現鑰匙不見了。一定是我兒子拿著玩，不知道丟到哪個犄角旮旯去了，你們說，我應該如何找？

7.5.1?深度優先遍歷 203

7.5.2?廣度優先遍歷 205

7.6　最小生成樹 208

如果你加班加點，沒日沒夜設計出的結果是方案一，我想你離被炒魷魚應該是不遠了（同學微笑）。因為這個方案比後兩個方案一半還多的成本會讓老闆氣暈過去的。

7.6.1?普里姆（Prim）算法 209

7.6.2?克魯斯卡爾（Kruskal）算法 213

7.7　最短路徑 218

有人為了省錢，需路程最短，但換乘站間距離長等原因並不省時間；另一些人，他為趕時間，最大的需求是總時間要短；還有一類人，他們不想多走路，關鍵是換乘要少，這樣可以在車上好好休息一下。

7.7.1?迪傑斯特拉（Dijkstra）算法 220

7.7.2?弗洛伊德（Floyd）算法 225

7.8　拓撲排序 229

電影製作不可能在人員到位進駐場地時，導演還沒有找到，也不可能在拍攝過程中，場地都沒有。這都會導致荒謬的結果。

7.8.1?拓撲排序介紹 229

7.8.2?拓撲排序算法 230

7.9　關鍵路徑 234

假如造一個輪子要0.5天、造一個發動機要3天、造一個車底盤要2天、造一個外殼要2天，造其他零部件2天，全部零部件集中到一處要0.5天，組裝成車要2天，請問，在汽車廠造一輛車，最短需要多少天呢？

7.9.1?關鍵路徑算法的原理 236

7.9.2?關鍵路徑算法 237

7.10　總結回顧 242

7.11　結尾語 243

世界上最遙遠的距離，不是牛A與牛C之間的狹小空隙，而是你們當中，有人在通往牛×的路上一路狂奔，而有人步入大學校園就學會放棄。

第8章　查找 245

 

8.1　開場白 246

當你精心寫了一篇博文或者上傳一組照片到互聯網上，來自世界各地的無數“蜘蛛”便會蜂擁而至。所謂蜘蛛就是搜索引擎公司服務器上的軟件，它把互聯網當成了蜘蛛網，沒日沒夜地訪問上面的各種信息。

8.2　查找概論 247

比如網絡時代的新名詞，如 “蝸居”“蟻族”等，如果需要將它們收錄到漢語詞典中，顯然收錄時就需要查找它們是否存在，以及如果不存在時應該收錄的位置。

8.3　順序表查找 249

8.3.1?順序表查找算法 249

8.3.2?順序表查找優化 250

8.4　有序表查找 251

我在紙上已經寫好了一個100以內的正整數請你猜，問幾次可以猜出來。當時已經介紹瞭如何才可以最快猜出這個數字。我們把這種每次取中間記錄查找的方法叫做折半查找。

8.4.1?折半查找 251

8.4.2?插值查找 253

8.4.3?斐波那契查找 255

8.5　線性索引查找 257

我母親年紀大了，經常在家裡找不到東西，於是她用一小本子，記錄了家裡所有小東西放置的位置，比如戶口本放在右手床頭櫃下麵抽屜中，鈔票放在衣……咳，這個就不提了。

8.5.1?稠密索引 258

8.5.2?分塊索引 258

8.5.3?倒排索引 260

8.6　二叉排序樹 262

後來老虎來了，一人拼命地跑，另一人則急中生智，爬到了樹上。而老虎是不會爬樹的，結果……。爬樹者改變了跑的思想，這一改變何等重要，撿回了自己的一條命。

8.6.1?二叉排序樹的查找操作 264

8.6.2?二叉排序樹的插入操作 266

8.6.3?二叉排序樹的刪除操作 267

8.6.4?二叉排序樹總結 272

8.7　平衡二叉樹（AVL樹） 273

平板就是一個世界，當誘惑降臨，人們心中的平衡被打破，世界就會混亂，最後留下的只有孤獨寂寞失敗。這種單調的機械化的社會，禁不住誘惑的侵蝕，最容易被侵蝕的，恰恰是最空虛的心靈。

8.7.1?平衡二叉樹的實現原理 275

8.7.2?平衡二叉樹的實現算法 278

8.8　多路查找樹（B樹） 284

要觀察一個公司是否嚴謹，看他們如何開會就知道了。如果開會時每一個人都只是帶一張嘴，即興發言，這肯定是一家不嚴謹的公司。

8.8.1?2-3樹 285

8.8.2?2-3-4樹 289

8.8.3?B樹 290

8.8.4?B+樹 292

8.9　散列表查找（哈希表）概述 294

你很想學太極拳，聽說學校有個叫張三豐的人打得特別好，於是到學校學生處找人，工作人員拿出學生名單，最終告訴你，學校沒這個人，並說張三豐幾百年前就已經在武當山作古了。

8.9.1?散列表查找定義 294

8.9.2?散列表查找步驟 295

8.10　散列函數的構造方法 296

8.10.1?直接尋址法 297

8.10.2?數字分析法 297

8.10.3?平方取中法 298

8.10.4?折疊法 298

8.10.5?除留餘數法 298

8.10.6?隨機數法 299

8.11　處理散列沖突的方法 300

我們每個人都希望身體健康，雖然疾病可以預防，但不可避免，沒有任何人可以說，生下來到現在沒有生過一次病。

8.11.1?開放尋址法 300

8.11.2?再散列函數法 302

8.11.3?鏈地址法 302

8.11.4?公共溢出區法 302

8.12　散列表查找的實現 303

8.12.1?散列表查找的算法實現 303

8.12.2?散列表查找的性能分析 305

8.13　總結回顧 305

如果我是個喜歡汽車的人，時常搜汽車信息。那麽當我在搜索框中輸入“甲殼蟲”“美洲虎”等關鍵詞時，不要讓動物和人物成為搜索的頭條。

8.14　結尾語 306

第9章　排序 309

 

9.1　開場白 310

假如我想買一臺iPhone 4的手機，於是上了某電子商務網站去搜索。可搜索後發現，有8863個相關的物品，如此之多，這叫我如何選擇。我其實是想買便宜一點的，但是又怕遇到騙子，想找信譽好的商家，如何做？

9.2　排序的基本概念與分類 310

比如我們某些大學為了選拔在主科上更優秀的學生，要求對所有學生的所有科目總分倒序排名，並且在同樣總分的情況下將語數外總分做倒序排名。這就是對總分和語數外總分兩個次關鍵字的組合排序。

9.2.1?排序的穩定性 311

9.2.2?內排序與外排序 312

9.2.3?排序用到的結構與函數 313

9.3　冒泡排序 314

無論你學習哪種編程語言，在學到循環和數組時，通常都會介紹一種排序算法，而這個算法一般就是冒泡排序。並不是它的名稱很好聽，而是說這個算法的思路最簡單，最容易理解。

9.3.1?最簡單排序的實現 314

9.3.2?冒泡排序算法 315

9.3.3?冒泡排序優化 316

9.3.4?冒泡排序復雜度分析 317

9.4　簡單選擇排序 318

還有一種做股票的人，他們很少出手，只是在不斷觀察和判斷，等時機一到，果斷買進或賣出。他們因為冷靜和沉著，以及交易的次數少，而最終收益頗豐。

9.4.1?簡單選擇排序算法 318

9.4.2?簡單選擇排序復雜度分析 319

9.5　直接插入排序 320

哪怕你是第一次玩撲克牌，只要認識這些數字，理牌的方法都是不用教的。將3和4移動到5的左側，再將2移動到最左側，順序就算是理好了。這里，我們的理牌方法，就是直接插入排序法。

9.5.1?直接插入排序算法 320

9.5.2?直接插入排序復雜度分析 322

9.6　希爾排序 323

不管怎麽說，希爾排序算法的發明，使得我們終於突破了慢速排序的時代（超越了時間復雜度為O(n2)），之後，更為高效的排序算法也就相繼出現了。

9.6.1?希爾排序原理 324

9.6.2?希爾排序算法 325

9.6.3?希爾排序復雜度分析 328

9.7　堆排序 329

什麽叫堆結構呢？回憶一下我們小時候，特別是男同學，基本都玩過疊羅漢的惡作劇。通常都是先把某個要整的人按倒在地，然後大家就一擁而上撲了上去……後果？後果當然就是一笑了之。

9.7.1?堆排序算法 331

9.7.2?堆排序復雜度分析 337

9.8　歸並排序 337

即使你是你們班級第一、甚至年級第一名，如果你沒有上分數線，則說明你的成績排不到全省前1萬名，你也就基本失去了當年上本科的機會了。

9.8.1?歸並排序算法 338

9.8.2?歸並排序復雜度分析 343

9.8.3?非遞歸實現歸並排序 343

9.9　快速排序 346

終於我們的高手要登場了，將來你工作後，你的老闆讓你寫個排序算法，而你會的算法中竟然沒有快速排序，我想你還是不要聲張，偷偷去把快速排序算法找來敲進電腦，這樣至少你不至於被大夥兒取笑。

9.9.1?快速排序算法 346

9.9.2?快速排序復雜度分析 349

9.9.3?快速排序優化 350

9.10　總結回顧 354

目前還沒有十全十美的排序算法，有優點就會有缺點，即使是快速排序法，也只是在整體性能上優越，它也存在排序不穩定、需要大量輔助空間、對少量數據排序無優勢等不足。

9.11　結尾語 357

如果你有夢想的話，就要去捍衛它。當別人做不到的時候，他們就想要告訴你，你也不能。如果你想要些什麽，就得去努力爭取。就這樣！