簡介《算法導(dǎo)論》第四版是麻省理工學(xué)院出版社出版的計算機科學(xué)經(jīng)典教材由四位國際知名學(xué)者合著被全球眾多高校選為算法課程指定教材。資源面向計算機專業(yè)學(xué)生、考研者及從業(yè)工程師系統(tǒng)講解算法的設(shè)計、分析與實現(xiàn)方法無論是課程學(xué)習(xí)、考研復(fù)習(xí)還是技術(shù)面試準(zhǔn)備都能從中獲得扎實的理論支撐與解題思路。全書從基礎(chǔ)概念到高級專題循序漸進涵蓋排序與選擇、堆與快速排序、線性時間排序、數(shù)據(jù)結(jié)構(gòu)、圖算法、動態(tài)規(guī)劃、貪心算法、回溯算法、分治算法、近似算法及NP完全理論等核心主題并對時間復(fù)雜度與空間復(fù)雜度分析、矩陣乘法含斯特拉森算法等進階內(nèi)容做了深入闡述書中配有大量實踐習(xí)題與案例分析幫助讀者在設(shè)計、分析和實現(xiàn)層面完整掌握算法知識。資源為單個PDF文件共1個文件大小19.64MB內(nèi)容清晰完整適合長期收藏與反復(fù)查閱。目前已有1247人學(xué)習(xí)瀏覽是系統(tǒng)學(xué)習(xí)算法、備戰(zhàn)面試或開展科研的高質(zhì)量參考。1. 算法導(dǎo)論第四版PDF從啃不動到能吃透的經(jīng)典大部頭如果只允許我在算法領(lǐng)域保留一份 PDF我會選《算法導(dǎo)論 第四版》。它既不是刷題攻略也不是速成講義而是一份把插入排序、紅黑樹、動態(tài)規(guī)劃、最大流一直延伸到機器學(xué)習(xí)聚類的完整算法地圖。準(zhǔn)備面試補手撕代碼、讀研開始接觸理論、或者工作多年想系統(tǒng)回爐的人都能在這里找到自己缺的那一塊。第一次翻開的人容易被厚度嚇退但真正的難點不是書太厚而是不知道按什么順序讀以及讀到哪一步該停下來驗證。這份 PDF 給出的是一套完整的原理、習(xí)題和偽代碼剩下的問題只有一個怎么把它變成自己的東西。2. 算法導(dǎo)論第四版值得讀嗎第四版改了什么適合哪種讀法2.1 第四版最直觀的變化章節(jié)地圖和配套都變了第四版在結(jié)構(gòu)上做了一個很聰明的調(diào)整把機器學(xué)習(xí)、并行算法、在線算法這些貼近現(xiàn)代工程的話題分別獨立成章放在全書的專題部分。目錄里能看到第 25 章單獨講二分圖匹配穩(wěn)定婚姻問題和匈牙利算法拿到了完整篇幅第 26 章講 fork-join 并行第 27 章講在線算法第 33 章干脆把聚類、乘性權(quán)重、梯度下降這些內(nèi)容寫成了“機器學(xué)習(xí)算法”一章。對老讀者來說這種變化意味著以前要拼湊多個章節(jié)才能理解的主題現(xiàn)在有了一條完整的推導(dǎo)線索。除了章節(jié)調(diào)整第四版在閱讀體驗上的改動也值得說。全書插圖統(tǒng)一換成了彩色版本231 幅圖不再是一團灰分治遞歸樹、紅黑樹旋轉(zhuǎn)、最大流殘存網(wǎng)絡(luò)這些原本依賴想象力的內(nèi)容現(xiàn)在顏色能直接幫你區(qū)分不同的路徑與節(jié)點狀態(tài)。每一章末尾保留了星號標(biāo)記帶 ★ 的小節(jié)和習(xí)題明確面向研究生層次普通人可以整段跳過而不影響主線。這種把“本科基礎(chǔ)”和“科研進階”分開的做法對自學(xué)者非常友好我第一次用的時候甚至覺得有點感動——終于不用在入門階段跟研究生難度的證明死磕了。配套資源也比前幾版完整。全書配有 931 道練習(xí)題和 162 道綜合題每個章節(jié)末尾的 Problems 經(jīng)常能引出教材正文沒講透的新結(jié)論這些題比 Exercises 更值得反復(fù)做。官方配套網(wǎng)頁公布了一部分習(xí)題的參考解答不是全部但足夠用來驗證自己的思路對不對。要注意的是它始終是教材不是題庫不要指望靠刷它的題來應(yīng)付在線評測平臺的算法題它的定位是幫你建立完整的算法設(shè)計和分析能力而不是訓(xùn)練刷題手感。2.2 學(xué)生、面試準(zhǔn)備者、工程師三種讀法面向不同目標(biāo)的人這本書的打開方式差異很大。我見過不少人拿起書就從第 1 頁開始背三周后卡在漸近記號后面全盤放棄也見過把整本書當(dāng)字典查的工程師每次遇到不熟悉的數(shù)據(jù)結(jié)構(gòu)就翻對應(yīng)章節(jié)反而用得得心應(yīng)手。下面這張表可以當(dāng)作選路線的起點人群優(yōu)先章節(jié)主要產(chǎn)出在讀學(xué)生1-5、8-9、14-16、20-24課堂作業(yè)、考試證明、復(fù)雜度分析能力面試準(zhǔn)備者2、6-13、15、22-23、32手撕代碼、復(fù)雜度推導(dǎo)、邊界處理工程實踐者10-13、17-19、21、26-27把偽代碼翻譯成可維護的實現(xiàn)學(xué)生的讀法相對固定第一學(xué)期覆蓋基礎(chǔ)、排序和數(shù)據(jù)結(jié)構(gòu)第二學(xué)期覆蓋動態(tài)規(guī)劃、貪心和圖算法。每一章的 Problems 都要動手做因為它們比 Exercises 更接近真實問題經(jīng)常要綜合三四個算法才能解出來。做不完也沒關(guān)系但至少每章挑兩道最難的硬啃這個過程比讀十頁正文都長本事。面試準(zhǔn)備者的讀法不需要從第 1 頁開始。先讀第 2 章插入排序、第 4 章分治、第 6-7 章堆排序與快速排序、第 12-13 章二叉搜索樹與紅黑樹再攻第 15 章動態(tài)規(guī)劃里的 LCS 和矩陣鏈、第 22-23 章單源與多源最短路、第 32 章 KMP。讀的過程中必須把偽代碼實現(xiàn)成真實代碼配合在線評測平臺按主題刷題。重點不是把書讀完而是把高頻考點對應(yīng)的章節(jié)嚼碎手撕快排、堆排、二分、鏈表反轉(zhuǎn)、二叉樹遍歷、DP 狀態(tài)轉(zhuǎn)移方程這些在面試里出現(xiàn)的頻率遠高于 B 樹刪除和線性規(guī)劃。工程實踐者的讀法更偏功利把第 10-13 章哈希表與平衡樹吃透存儲引擎和緩存設(shè)計背后的原理都在這里第 17 章的區(qū)間樹和動態(tài)順序統(tǒng)計在業(yè)務(wù)查詢場景里經(jīng)常能用上第 18 章 B 樹是數(shù)據(jù)庫索引的地基第 26-27 章并行與在線算法對應(yīng)多核調(diào)度和實時系統(tǒng)附錄的求和、矩陣、概率部分不要當(dāng)作正文讀遇到看不懂的推導(dǎo)回來查就夠。那么什么時候不適合讀這本書如果你只有兩周準(zhǔn)備面試或者只需要完成一個很小的編程任務(wù)直接看精簡的講義或刷題總結(jié)效率更高。這本書的價值在“長期復(fù)利”第一遍建立骨架第二遍填充細節(jié)第三遍開始能自己推導(dǎo)變體算法。真正能把它用起來的人都有不止一次從頭翻閱的經(jīng)歷。3. 拿到PDF后怎么讀三個月路線圖與自檢方法3.1 一條可以照抄的三個月閱讀規(guī)劃我見過太多人拿到這份 PDF 后的第一反應(yīng)是從第 1 頁開始線性閱讀然后把書合上再也沒打開。更有效的做法是給自己定一個“以產(chǎn)出為驗收標(biāo)準(zhǔn)”的路線圖每一周結(jié)束時都能交出一份東西。以下是我整理的一條經(jīng)過實踐驗證的路線適合從零補算法基礎(chǔ)的人和剛?cè)雽W(xué)的學(xué)生參考。時間段主題內(nèi)容驗收產(chǎn)出第 1 周第 1-3 章算法基礎(chǔ)與漸近記號能默寫插入排序并解釋最壞情況復(fù)雜度第 2-3 周第 4 章分治與主定理能畫出歸并排序遞歸樹寫出主定理三個 case第 4-5 周第 6-9 章堆、快排、線性時間排序手寫堆排序、快排、計數(shù)排序并通過對拍測試第 6 周第 10-11 章基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)和哈希實現(xiàn)鏈地址法哈希表和處理沖突第 7-8 周第 12-13 章二叉搜索樹與紅黑樹實現(xiàn) BST 增刪查畫出紅黑樹插入修復(fù)流程第 9-10 周第 14-15 章動態(tài)規(guī)劃與貪心手寫鋼條切割、LCS、Huffman 編碼第 11 周第 16 章攤還分析用勢能法分析動態(tài)表擴張第 12-13 周第 20 章BFS、DFS、拓撲、強連通用鄰接表實現(xiàn)四種圖算法第 14 周第 21 章最小生成樹用并查集優(yōu)化 Kruskal 算法第 15 周第 22-23 章最短路算法實現(xiàn) Bellman-Ford 和 Dijkstra跑通帶權(quán)圖如果已經(jīng)讀過一遍可以直接從第 12 周開始把精力集中在圖算法和動態(tài)規(guī)劃的進階實現(xiàn)上。如果只準(zhǔn)備面試參考上一章的面試路線圖不需要走完這條完整路線。每周結(jié)束時用三個標(biāo)準(zhǔn)自檢能不能合上書寫出本周涉及的全部偽代碼能不能對著復(fù)雜度公式解釋為什么是這個增長階能不能拿一個五元素的小例子手工走一遍算法并追蹤每步狀態(tài)。三個標(biāo)準(zhǔn)都滿足才算過關(guān)否則寧可慢一周也不要把問題沉淀到下個主題。盲目趕進度是自欺欺人后半程你會發(fā)現(xiàn)前面略過的內(nèi)容全部會回來找你。拿到 PDF 的第一步建議先做一件事給文件加書簽。把八個大部分的書名設(shè)為父層每章章名設(shè)為子層第 3 章和第 4 章單獨標(biāo)注成“數(shù)學(xué)工具”和“主定理”。絕大多數(shù) PDF 閱讀器都支持書簽導(dǎo)出后面回查某個算法時不用再靠滾動條在幾百頁里亂翻。提示第 3 章的漸近記號內(nèi)容當(dāng)作參考手冊處理需要時回來查不要在第一遍就花一周死磕形式定義。3.2 用“手動走一遍”的方法吃透插入排序讀第 2 章插入排序時掃一遍偽代碼很容易產(chǎn)生“我懂了”的錯覺合上書一寫就露餡。我常用的方法很簡單把 INSERTION-SORT 翻譯成能在本地單步執(zhí)行的腳本拿一個五元素數(shù)組手動走一遍每一輪外層循環(huán)結(jié)束后把數(shù)組的狀態(tài)打印出來和書上的圖解對照。下面這個模板是 0 基數(shù)組的 Python 實現(xiàn)def insertion_sort(a): # a: 待排序數(shù)組原地修改不返回值 for j in range(1, len(a)): # j 是當(dāng)前要插入的元素位置 key a[j] # 取出當(dāng)前鍵值 i j - 1 # 從 j-1 開始往前掃描 while i 0 and a[i] key: # 把比 key 大的元素逐個右移 a[i 1] a[i] i - 1 a[i 1] key # 在空出來的位置寫回 key return a邏輯說明偽代碼里數(shù)組下標(biāo)從 1 開始翻譯到 Python 時外層循環(huán)從第二個元素開始內(nèi)層 while 根據(jù) 0 基邊界改成i 0。key 暫存當(dāng)前要插入的值所有比 key 大的元素右移一位循環(huán)結(jié)束后把 key 寫回空位。整個算法只用了常數(shù)個額外變量空間復(fù)雜度 O(1)屬于原地排序。參數(shù)說明函數(shù)接受任意可比較元素的列表整數(shù)、浮點數(shù)、字符串都能排但如果列表里混了不同類型比較時會拋 TypeError。最容易翻車的邊界條件是while i 0漏掉等號那會讓第一個元素永遠不參與比較排序從第二步就開始出錯。另外注意穩(wěn)定性的細節(jié)比較條件是a[i] key而不是相等元素不會被交換位置所以插入排序是穩(wěn)定排序這個特點在工程里有時會被特意利用。手動走一遍的方法我一般配合紙筆做紙上畫四列表格分別是數(shù)組快照、j、key、i每走完一輪 while 就更新一次。五元素的例子走完你對為什么插入排序最壞是 O(n2)、最好能到 O(n) 的理解會比只看書上的推導(dǎo)深刻得多。這種“手算追蹤”的方式對后面讀紅黑樹、Dijkstra、KMP 一樣有效算是讀算法導(dǎo)論最值得養(yǎng)成的習(xí)慣之一。3.3 讀分治章節(jié)時用主定理反向推一遍遞歸樹第 4 章是全書第一個真正的數(shù)學(xué)高地覆蓋了替換法、遞歸樹、主定理最后還給了 Akra-Bazzi 遞推的一般形式。對大多數(shù)讀者來說最實用的是主定理T(n) 2T(n/2) Θ(n) 屬于 case 2結(jié)果是 Θ(n log n)T(n) 2T(n/2) Θ(n2) 屬于 case 3結(jié)果是 Θ(n2)。常見誤區(qū)是只看 f(n) 和 n^(log_b a) 的大小忽略了主定理要求的是“多項式意義上的大于或小于”差一個 n^ε 因子就可能不適用。讀這一節(jié)時建議把遞歸樹畫三遍第一遍跟著圖例畫一個九節(jié)點的樹第二遍拿歸并排序畫 n16 的完整分層第三遍把遞歸樹每一層的代價寫成求和式最后算出總和。這個過程走完你會自然理解為什么歸并排序是 n log n 而不是 n2。耳朵聽一百遍“l(fā)og n 來自遞歸深度”不如自己畫一棵樹來得踏實。第 4.7 節(jié) Akra-Bazzi 是帶星號的進階內(nèi)容處理主定理三個 case 都不適用的變體遞歸式。本科生和面試選手可以直接跳過但如果你之后要讀研究論文見到形式奇怪的遞歸式時能認出“這是 Akra-Bazzi 可解的”就夠了。讀分治章節(jié)時還有一個容易被忽略的點Strassen 矩陣乘法。不要只背那個七次乘法的結(jié)論重點看它是怎么通過“減少乘法次數(shù)、增加加法次數(shù)”來改變遞推式的這種思路在后來的 FFT 和快速矩陣求逆里會反復(fù)出現(xiàn)。4. 讀算法導(dǎo)論的常見翻車現(xiàn)場四個高頻坑與排查思路4.1 坑一按目錄線性通讀三個月卡在第三章現(xiàn)象不少讀者拿到 PDF 后信心滿滿地立 flag每周讀一章。第一周順利翻完第 1 章第二周開始接觸插入排序到第 3 章漸近記號就發(fā)現(xiàn)每頁都是新符號一遍看不懂進度徹底卡死后面整個學(xué)習(xí)計劃崩盤。原因第 3 章和第 4 章是全書數(shù)學(xué)符號的集散地O、Ω、Θ、o、ω 加上求和、對數(shù)的性質(zhì)全擠在一起。這些內(nèi)容不是看過一遍就結(jié)束的“導(dǎo)論”而是后續(xù)每章都要回頭查閱的工具集。線性通讀恰好把工具章節(jié)當(dāng)成入門章節(jié)來啃失敗不在于書難而在于閱讀順序不合理。解決第一遍閱讀只保留以具體算法為核心的章節(jié)比如第 2 章的插入排序、第 6-9 章的排序全家桶遇到不認識的記號再回第 3 章查對應(yīng)定義。漸近記號會在后續(xù)章節(jié)里反復(fù)出現(xiàn)看得多了自然就熟了。附錄 A-D 的求和、集合、概率、矩陣也一樣當(dāng)手冊用不要逐頁精讀。我自己的習(xí)慣是在書簽里把第 3 章命名為“查符號”需要時直接跳過去找定義。4.2 坑二偽代碼下標(biāo)從 1 開始翻譯成代碼后邊界全亂現(xiàn)象照著第 2 章的 INSERTION-SORT 寫 Python翻譯完一跑發(fā)現(xiàn)第一個元素總是丟照搬第 6 章 HEAPSORT 的下標(biāo)關(guān)系數(shù)組一直越界堆排序結(jié)果亂成一團。原因偽代碼用 A[1..n] 表示數(shù)組循環(huán)經(jīng)常寫for j 2 to n而 Python、Java、C 全是 0 基數(shù)組。翻譯時如果只把循環(huán)邊界做了簡單的減一處理內(nèi)部訪問就會全面錯位。堆排序更典型偽代碼里left 2*i、right 2*i1是 1 基下的關(guān)系換成 0 基必須變成left 2*i1、right 2*i2漏掉這個換算整個堆的父子關(guān)系都是亂的。解決翻譯前先確定索引基準(zhǔn)。我的做法是先把偽代碼里所有A[k]在草稿紙上換成A[k-1]再對循環(huán)邊界做整體平移最后補三個邊界測試空數(shù)組、單元素數(shù)組、含重復(fù)元素的數(shù)組。這三種情況都能通過不代表正確但能排除一大半低級錯誤。堆排序還要注意另一個隱藏點偽代碼里A.heap-size和A.length是兩個不同概念前者表示堆的有效長度排序過程中會逐步縮小翻譯成 Python 后堆的有效長度要單獨用一個變量維護不能直接用len(a)。4.3 坑三以為看懂證明就能寫出代碼結(jié)果手生得可怕現(xiàn)象每一章的推導(dǎo)都能順暢地跟下來紅黑樹的插入修復(fù)、Dijkstra 的松弛操作、KMP 的失敗函數(shù)都覺得自己看懂了。過兩周回頭連紅黑樹刪除有幾種情況都記不清更別說手撕代碼。原因閱讀是被動跟隨寫代碼是主動構(gòu)建。跟隨敘述路徑時大腦完成的是“識別”而不是“生成”。算法學(xué)習(xí)的檢驗標(biāo)準(zhǔn)不是“看懂了”而是“合上書之后還能不能準(zhǔn)確復(fù)現(xiàn)”。這兩者之間的差距比大多數(shù)人想象中大得多。解決每章結(jié)束后合上書寫三樣?xùn)|西算法要維持的不變式、偽代碼框架、一個五元素手工執(zhí)行跟蹤。寫完再打開書對照只標(biāo)記差異點不要重新讀整章。差異點通常集中在邊界變量、循環(huán)不變式和終止條件上而這些正是后續(xù)面試和工程實現(xiàn)最容易丟分的位置。如果發(fā)現(xiàn)自己寫不出來不要沮喪這是正常的信號說明這一章需要重新過一遍而不是翻書抄一遍假裝會了。4.4 坑四英文原版的長句和術(shù)語把閱讀速度拖成龜速現(xiàn)象非母語讀者直接讀英文原版每段都要停下來查單詞一段三百字的內(nèi)容要讀十分鐘很難堅持到第 4 章。越讀越慢越慢越挫敗最后只能放棄。原因教材的英文是學(xué)術(shù)性敘述大量長從句、被動語態(tài)和術(shù)語堆疊。問題不是英語語法沒過關(guān)而是“查閱功耗”太高大部分精力被消耗在語言上而不是算法邏輯上。解決改用目標(biāo)驅(qū)動的局部閱讀法不逐句翻譯只看四個點位算法輸入輸出、核心步驟描述、復(fù)雜度結(jié)論、證明的關(guān)鍵斷言。術(shù)語方面自己建一張中英對照術(shù)語表每章只記十到十五個核心詞就好。如果長時間閱讀速度上不來可以前五章和附錄部分配合中文譯本一起讀后面章節(jié)再回到英文原版。后期代碼和公式的占比很高語言障礙對理解的影響會明顯降低。讀英文版的目的不是學(xué)英語是抓住算法的骨架別讓語言成為你與好內(nèi)容之間的墻。5. 把算法導(dǎo)論當(dāng)代碼庫用從偽代碼到可運行實現(xiàn)的翻譯技巧5.1 偽代碼約定速查縮進、索引與返回值翻譯偽代碼之前先把它的五條約定記清楚?？s進表示塊結(jié)構(gòu)同一縮進級別是同一個循環(huán)體或分支體翻譯成 Python 時注意嵌套層級不要散掉。數(shù)組索引從 1 開始所有下標(biāo)運算都要做整體平移。變量默認是過程局部變量遞歸調(diào)用時每次調(diào)用重新綁定不要誤寫成共享的全局狀態(tài)。數(shù)組參數(shù)按引用傳遞過程內(nèi)修改數(shù)組會影響調(diào)用方這一點和 Python 列表的行為正好吻合。最后一條容易被忽略A.length和A.heap-size是兩個不同的屬性前者是數(shù)組容量后者是堆的有效長度在堆排序里前者不變后者遞減。下面這張表是翻譯時最常見的對應(yīng)關(guān)系偽代碼表達含義Python 等價寫法A[1..n]長度為 n 的數(shù)組0 基列表或 a [0] arrfor j p to r閉區(qū)間循環(huán)for j in range(p, r1)exchange A[i] with A[j]交換兩個位置a[i], a[j] a[j], a[i]return x返回值return xA.heap-size堆的有效長度heap_size 獨立變量哨兵 ∞無窮占位float(inf)注意偽代碼中A.heap-size的合法下標(biāo)是 1 到 A.heap-size在 0 基語言中有效下標(biāo)變成 0 到 heap_size-1。這是堆排序翻譯中最容易出問題的位置我見過不止一個人在這里翻車最后排查半天發(fā)現(xiàn)只是下標(biāo)差了一位。5.2 三個可直接照抄的經(jīng)典實現(xiàn)二分查找、堆排序、快速排序以下三個實現(xiàn)覆蓋了遍歷查找、完全二叉樹原地排序、遞歸分治三類典型結(jié)構(gòu)分別對應(yīng)第 2 章練習(xí)、第 6 章和第 7 章的核心算法。代碼可以直接復(fù)用到自己的練習(xí)項目里。def binary_search(a, target): 在升序列表中查找 target返回下標(biāo)找不到返回 -1 left, right 0, len(a) - 1 while left right: mid (left right) // 2 if a[mid] target: return mid elif a[mid] target: left mid 1 # 目標(biāo)在右半?yún)^(qū) else: right mid - 1 # 目標(biāo)在左半?yún)^(qū) return -1邏輯說明每次循環(huán)把搜索范圍縮小一半循環(huán)條件left right保證空區(qū)間時正常退出。mid 取左中位當(dāng)a[mid] target時目標(biāo)只可能在 mid 右側(cè)所以left mid 1而不是mid這是避免死循環(huán)的關(guān)鍵。時間復(fù)雜度 O(log n)空間復(fù)雜度 O(1)。參數(shù)說明a 必須是升序數(shù)組否則結(jié)果無意義target 可以是任何可比較類型。在 Python 中(left right) // 2不會溢出但在 C 或 Java 里兩個大整數(shù)相加可能溢出更穩(wěn)的寫法是left (right - left) // 2面試時可以主動提這一點。def max_heapify(a, heap_size, i): 維護以 i 為根的子樹滿足最大堆性質(zhì) left 2 * i 1 # 0 基下左孩子下標(biāo) right 2 * i 2 # 0 基下右孩子下標(biāo) largest i if left heap_size and a[left] a[largest]: largest left if right heap_size and a[right] a[largest]: largest right if largest ! i: a[i], a[largest] a[largest], a[i] max_heapify(a, heap_size, largest) def heapsort(a): n len(a) # 建堆從最后一個非葉節(jié)點開始向上調(diào)整 for i in range(n // 2 - 1, -1, -1): max_heapify(a, n, i) # 依次把堆頂換到末尾再對縮小的堆重新調(diào)整 for i in range(n - 1, 0, -1): a[0], a[i] a[i], a[0] max_heapify(a, i, 0)邏輯說明max_heapify 假設(shè) i 的左右子樹已經(jīng)是合法最大堆只負責(zé)把 i 下沉到正確位置。建堆從n // 2 - 1開始因為這是最后一個非葉節(jié)點在 0 基數(shù)組中的下標(biāo)從它倒序遍歷到 0保證每個子樹先滿足堆性質(zhì)再處理上層。排序階段每輪把堆頂最大值交換到數(shù)組末尾然后對去掉末尾的新堆重新調(diào)整max_heapify(a, i, 0)里的 i 是新的堆大小不是下標(biāo)上界。整個過程原地完成空間復(fù)雜度 O(1)。參數(shù)說明heapsort 原地修改列表要求 a 支持下標(biāo)訪問和元素交換。時間復(fù)雜度穩(wěn)定在 O(n log n)但它是不穩(wěn)定排序如果需要穩(wěn)定排序要用歸并。翻譯時最容易錯的就是下標(biāo)換算偽代碼里left 2*i在 0 基下必須改成2*i1這一步錯了整個堆結(jié)構(gòu)就塌了。def partition(a, lo, hi): 以 a[hi] 為基準(zhǔn)把不大于基準(zhǔn)的元素放到左側(cè)返回基準(zhǔn)最終下標(biāo) pivot a[hi] i lo - 1 # i 是已劃分區(qū)間的右邊界 for j in range(lo, hi): if a[j] pivot: i 1 a[i], a[j] a[j], a[i] a[i 1], a[hi] a[hi], a[i 1] return i 1 def quicksort(a, lo, hi): if lo hi: p partition(a, lo, hi) quicksort(a, lo, p - 1) # 遞歸處理基準(zhǔn)左側(cè) quicksort(a, p 1, hi) # 遞歸處理基準(zhǔn)右側(cè)邏輯說明partition 維護兩個區(qū)間[lo, i] 是已確定不大于 pivot 的部分[i1, j-1] 是等待處理的部分。掃描過程中每次遇到不大于 pivot 的值就把它交換到已劃分區(qū)間的尾部。掃描結(jié)束后把 pivot 從 hi 交換到 i1此時 pivot 已經(jīng)處在最終正確位置所以遞歸區(qū)間必須排除 p 本身否則會無限遞歸。參數(shù)說明lo、hi 是閉區(qū)間端點首次調(diào)用quicksort(a, 0, len(a)-1)。基準(zhǔn)取a[hi]實現(xiàn)簡單但最壞情況下已排序數(shù)組會讓復(fù)雜度退化成 O(n2)第 7.3 節(jié)專門講了隨機化改進方案實際工程中更常用三數(shù)取中。Lomuto 劃分比 Hoare 劃分容易寫對代價是交換次數(shù)略多面試時用 Lomuto 版本基本夠用。如果繼續(xù)翻譯第 8 章的計數(shù)排序、基數(shù)排序、桶排序可以沿用同一套思路先把數(shù)組索引改成 0 基再單獨處理穩(wěn)定性。計數(shù)排序的累加數(shù)組和輸出位置關(guān)系是最大坑點寫錯一次輸出順序就全亂了建議翻譯完立刻用第 5.3 節(jié)的對拍腳本驗證。5.3 對拍測試用隨機數(shù)據(jù)驗證翻譯是否正確翻譯完不測試等于白寫。我自己的習(xí)慣是寫完一個算法馬上用語言內(nèi)置的排序函數(shù)做對拍隨機生成大量數(shù)據(jù)把被測函數(shù)的結(jié)果和內(nèi)置結(jié)果逐一對比。下面這個腳本可以直接復(fù)用import random def check_sort(sort_fn, rounds200, size1000): 用內(nèi)置 sorted 做基準(zhǔn)隨機測試 sort_fn 的原地排序結(jié)果 for _ in range(rounds): arr [random.randint(-10000, 10000) for _ in range(size)] expected sorted(arr) sort_fn(arr) if arr ! expected: print(排序結(jié)果不一致) print(樣例:, arr[:20], expected[:20]) return False print(f{rounds} 輪隨機測試全部通過) return True if __name__ __main__: check_sort(heapsort)邏輯說明每輪生成隨機整數(shù)列表先用內(nèi)置 sorted 得到期望結(jié)果再調(diào)用被測排序函數(shù)原地修改數(shù)組最后逐元素比較。隨機數(shù)據(jù)里包含正負數(shù)、重復(fù)值能覆蓋絕大多數(shù)邊界情況。如果想專門測空數(shù)組和單元素數(shù)組可以額外手寫兩個固定用例調(diào)用排序函數(shù)檢查。參數(shù)說明rounds 控制測試輪數(shù)size 控制數(shù)組長度。對 O(n log n) 的排序來說1000 元素跑 200 輪在毫秒級完成完全不用擔(dān)心性能。這個腳本可以替換成任何排序函數(shù)堆排、快排、插入排序都能用也可以改造成驗證二分查找生成升序數(shù)組后隨機取一個存在的和不存在的值分別檢查返回值是否正確。對拍通過后我還會做一次“可視化小樣”檢查把數(shù)組長度改成 2、3、4 各跑一遍打印每輪排序后的數(shù)組人眼確認執(zhí)行軌跡和第 4 章、第 6 章、第 7 章的圖例一致。這一步不是驗證正確性而是確認自己真的理解算法每一步在做什么。只有機器驗證通過、人眼也看懂了翻譯才算真正完成。6. 高階驗證與延伸用一晚上親手驗證排序算法的增長曲線6.1 最小實驗設(shè)計隨機數(shù)據(jù)測出兩種排序的耗時曲線讀完前九章你會得到一組復(fù)雜度結(jié)論插入排序 O(n2)快速排序 O(n log n)。結(jié)論背起來容易但如果你沒親眼見過這兩種增長曲線的差異遇到復(fù)雜度分析還是容易發(fā)虛。一個成本極低、收益很高的實驗是固定隨機數(shù)據(jù)分布把 n 從 500 翻倍到 16000分別測插入排序和快速排序的耗時觀察 n 翻倍時耗時的增長倍數(shù)。import random import time def timed_run(sort_fn, arr): buf arr[:] # 復(fù)制數(shù)據(jù)避免原地排序污染后續(xù)測量 t0 time.perf_counter() sort_fn(buf) return time.perf_counter() - t0 for n in (500, 1000, 2000, 4000, 8000, 16000): data [random.randint(0, 10**6) for _ in range(n)] t1 timed_run(insertion_sort, data) t2 timed_run(quicksort, data, 0, len(data) - 1) print(fn{n:6d} insertion{t1*1000:8.2f}ms quick{t2*1000:8.2f}ms)邏輯說明timed_run 先把數(shù)組復(fù)制一份再計時確保每次測量都在相同的數(shù)據(jù)分布上進行。插入排序?qū)崿F(xiàn)用第 3.2 節(jié)的版本快速排序用第 5.2 節(jié)的版本。perf_counter 是 Python 里精度最高的計時接口適合這種毫秒級的測量。參數(shù)說明n 從 500 翻倍到 16000插入排序在隨機數(shù)據(jù)下到 16000 時大概耗時幾十到幾百毫秒快速排序則在幾毫秒到幾十毫秒?yún)^(qū)間。如果數(shù)據(jù)已經(jīng)有序快速排序會退化到 O(n2)測出來的曲線會異常陡峭這時要先用 random.shuffle 打亂數(shù)據(jù)再測。6.2 用數(shù)據(jù)反向驗證理論復(fù)雜度把實驗跑完你會看到一組非常有說服力的比值n 從 1000 翻到 2000插入排序的耗時大約翻 4 倍因為 (2n)2 / n2 4快速排序的耗時大約翻 2.1 到 2.4 倍因為 n log n 的增長比線性略快但遠慢于平方。這個觀察直接把第 3 章漸近記號的抽象定義變成了眼前的事實。如果測出來的倍數(shù)遠小于理論預(yù)期先檢查兩種邊界情況一是數(shù)據(jù)是否被排序過有序輸入會讓插入排序退化成 O(n)也會讓固定基準(zhǔn)的快速排序惡化二是測試規(guī)模太小計時器的噪聲蓋過了真實的耗時差異。把 n 的上限提高到 50000 再跑一輪曲線差異會清晰得多。這套方法論不只適用于排序紅黑樹插入、Dijkstra 堆優(yōu)化、KMP 匹配都能用同樣的方式來驗證。從那以后我每次讀完一個復(fù)雜度的結(jié)論都會順手跑一個最小實驗驗證它的增長曲線而不是直接背結(jié)論。這個習(xí)慣幫我避開了很多“看上去合理”的錯誤記憶也讓書里的公式不再是黑匣子。這份算法導(dǎo)論第四版 PDF 值得放進你的算法工具庫但要真正起作用還是要靠你親手把偽代碼跑起來。希望幫到你。本文還有配套的精品資源點擊獲取