以下是 **十大經典排序算法** 的時間復雜度、空間復雜度及穩定性總結，適用于面試快速回顧：
排序算法對比表
| 排序算法 | 最佳時間復雜度 | 平均時間復雜度 | 最差時間復雜度 | 空間復雜度 | 穩定性 | 核心思想 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n2) | O(n2) | O(1) | 穩定 | 相鄰元素交換，大數沉底。 |
| 選擇排序 | O(n2) | O(n2) | O(n2) | O(1) | 不穩定 | 每次選最小元素放到已排序末尾。 |
| 插入排序 | O(n) | O(n2) | O(n2) | O(1) | 穩定 | 將未排序元素插入已排序序列。 |
| 希爾排序 | O(n log n) | O(n log2 n) | O(n log2 n) | O(1) | 不穩定 | 分組(增量)插入排序，逐步縮小間隔。 |
| 歸并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 穩定 | 分治法，合并有序子序列。 |
| 快速排序 | O(n log n) | O(n log n) | O(n2) | O(log n) | 不穩定 | 分治法，基準值分區遞歸排序。 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不穩定 | 構建堆結構，交換堆頂與末尾。 |
| 計數排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | 穩定 | 統計元素出現次數，累加輸出。 |
| 桶排序 | O(n + k) | O(n + k) | O(n2) | O(n + k) | 穩定 | 分桶后對每個桶單獨排序。 |
| 基數排序 | O(nk) | O(nk) | O(nk) | O(n + k) | 穩定 | 按位分配收集，從低位到高位。 |
關鍵說明
-
穩定性：穩定排序算法保證相等元素的相對順序不變（如
歸并排序），不穩定算法可能改變（如快速排序）。 -
適用場景：
- 小規模數據：冒泡、插入、選擇排序（簡單但效率低）。
- 大規模數據：快速、歸并、堆排序（O(n log n) 復雜度）。
- 特定數據分布：
- 整數且范圍小：計數排序。
- 均勻分布數據：桶排序。
- 多關鍵字排序：基數排序。
-
空間復雜度：
- 原地排序：冒泡、插入、選擇、希爾、堆排序（O(1) 空間）。
- 非原地排序：歸并、計數、桶、基數排序（需額外空間）。
-
快速排序優化：
- 三數取中法：避免最壞情況 O(n2)。
- 小數組切換插入排序：遞歸到小數組時用插入排序提升效率。
面試常見問題
-
為什么快速排序在實際應用中比歸并排序更常用？
- 快速排序是原地排序，緩存友好；歸并排序需要 O(n) 額外空間。
-
堆排序為什么不如快速排序快？
- 堆排序數據訪問方式跳躍（非局部性原理），緩存命中率低。
-
如何選擇排序算法？
- 數據規模、內存限制、穩定性需求、數據分布特征。
