排序算法的重要性#

• 排序算法在歷史上是人們研究最多的一類算法，至今仍是程序中使用頻率最高的算法之一
• 排序算法是打開計算機科學之門的一把鑰匙
• 根據時間複雜度，排序算法大致可分為 O(N^2) 的算法和 O(NlogN) 的算法
• 理解排序算法的關鍵是要掌握兩個計算機科學的精髓——遞歸和分治

1.4.1 直觀的排序算法：時間到底浪費在哪裡#

選擇排序（Selection Sort）— O(N^2)#

• 每一次從序列中挑出一個最大值，放到序列的最後，重複多次直到排序完畢
• 步驟 1：從頭到尾比較相鄰元素，將大的放後面（冒泡），最後一個一定是最大的
• 步驟 2：再從頭到倒數第二個元素重複上述過程
• 總比較次數為 (N-1)+(N-2)+…+1 = N(N-1)/2 = O(N^2)

插入排序（Insert Sort）— O(N^2)#

• 類似打撲克牌時的抓牌過程：一邊抓牌，一邊將新牌插入到相應的位置
• 從後向前掃描，對每個元素找到相應的插入位置
• 插入一個元素的操作不是一次而是 O(N) 次（需要挪動後面的元素）
• 雖然可以用二分查找（logN 時間）找到插入位置，但挪動元素的時間省不了

兩種算法的共同問題#

• 選擇排序：做了很多無謂的比較（已知 X<Y, Y<Z 就不需再比較 X 和 Z）和無謂的位置互換
• 插入排序：做了很多無謂的數據移動
• 核心問題是存在大量重複或無用的操作

1.4.2 有效的排序算法：效率來自哪裡#

歸併排序（Merge Sort）— O(NlogN)#

• 由馮·諾依曼於 1945 年發明，是分治算法和遞歸的典型應用
• 核心思路：假設序列的前後兩部分各自已排好序，只需將兩個有序子序列合併起來
• 合併過程：用三個指針 p、q、r 分別指向合併後的序列 A、子序列 B 和子序列 C，每次比較 b[q] 和 c[r]，將較小的放入 A
• 遞歸分析：每一次遞歸將元素數量減半，只要 logN 次遞歸就到結束條件；每一層的計算量都是 O(N)，因此總複雜度為 O(NlogN)
• 省時原因：利用了「已知 X<Y, Y<Z 則 X<Z」的邏輯，省去了無謂的比較
• 缺點：需要額外的 O(N) 存儲空間保留中間結果

堆排序（Heap Sort）— O(NlogN)#

• 由約翰·威廉斯（John W.J. Williams）於 1964 年提出
• 滿足 O(NlogN) 的時間複雜度，且不佔用額外空間（就地特征）
• 額外空間複雜度為 O(1)

快速排序（Quick Sort）— O(NlogN) 平均#

• 由托尼·霍爾（Tony Hoare）發明
• 比歸併排序和堆排序算法快兩三倍，額外空間只需 O(logN)
• 缺點：極端情況下時間複雜度為 O(N^2)；不具有穩定性

三種高效排序算法的對比#

在計算機科學中很難有絕對的最好。衡量好的標準有很多維度，因此有時不存在一種算法就比另一種絕對好的情況。某些算法只是在設定的邊界條件下比其他的更適合罷了。

1.4.3 針對特殊情況的改進：蒂姆排序#

混合排序算法的趨勢#

• 今天人們對排序算法的改進大多是結合幾種排序算法的思想，形成混合排序算法（Hybrid Sorting Algorithm）
• 典型例子：內省排序（Introsort）——結合快速排序和堆排序，是 C++ STL 中排序函數使用的算法

蒂姆排序（Timsort）#

• 由蒂姆·彼得斯（Tim Peters）於 2002 年發明
• 今天 Java 和 Android 操作系統內部使用的排序算法
• 核心思想：利用數據中已有的遞增和遞減子序列（稱為「塊」或 run），減少比較和數據移動
• 步驟 1：找出序列中各個遞增和遞減的子序列，用插入排序將小塊整理為有序的 run，再用二分查找尋找插入位置
• 步驟 2：按照規則合併這些塊，先合併兩個最短的塊，效率更高。合併時採用跳躍式（galloping）預測方式，與傳統歸併排序不同
• 最壞時間複雜度為 O(NlogN)，是一種穩定的排序算法
• 靈活地利用了插入排序簡單直觀以及歸併排序效率高的特點

附錄：為什麼排序算法的複雜度不可能小於 O(NlogN)#

• N 個元素的數組能排出 N! 種可能的序列
• 區分 M 種序列的大小，需要 logM 次比較
• 因此排序至少需要 logN! 次比較
• 利用斯特林（Stirling）公式：logN! = NlnN - N + O(lnN)，得出 logN! = O(NlogN)
• 結論：任何排序算法的複雜度不會低於 O(NlogN)

要點#

• 歸併排序、堆排序、快速排序、遞歸、分治
• 平均時間複雜度、最壞時間複雜度、就地特征、排序的穩定性
• 少做無用功是提高算法效率的核心原則