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