各類排序算法的 C++ 實現與效能比較分析

前言

排序演算法是電腦科學中最基礎也最重要的課題之一。從簡單的冒泡排序到複雜的基數排序，每種演算法都有其獨特的適用場景與效能特徵。本文將以 C++ 實現七種經典排序演算法，並透過實際效能測試，深入剖析它們在不同情況下的表現差異。

演算法實現

1. 最小堆實現（堆排序基礎）

minheap.h 提供了完整的最小堆模板類，支援插入、刪除最小元素、建堆等核心操作。關鍵方法包括：

• FilterDown：自上而下調整堆，維持堆性質
• FilterUp：自下而上調整堆，用於插入新元素後的修復
• RemoveMin：移除並返回堆頂最小元素

2. 核心排序函數集（sort.cpp）

冒泡排序 - O(n²)

採用雙重迴圈反向掃描，設交換旗標優化：若某趟無交換則提前終止。

插入排序 - O(n²)

將陣列分為已排序與未排序區間，逐個將元素插入有序區間適當位置。

快速排序 - O(n log n) 平均

採用雙向掃描分區策略，選取基準值將陣列分為兩部分遞迴排序。

希爾排序 - O(n^1.3) 約略

改進的插入排序，按增量分組進行插入排序，增量序列採用 gap = gap/3 + 1。

計數排序 - O(n + k)

非比較型排序，適用於已知範圍整數（本例 0-1000），利用輔助陣列統計頻率。

基數排序 (MSD) - O(d·n)

從高位到低位遞迴分桶排序，小區間改用插入排序優化。

3. 效能測試框架（maintest.cpp）

測試環境：100,000 個 0-999 亂數整數，執行 40 次取平均。使用 clock() 計時，結果輸出至檔案與控制台。

效能測試結果分析

關鍵發現

1. 計數排序壓倒性勝利：在資料範圍已知且較小（0-1000）時，O(n+k) 複雜度碾壓所有比較型排序。
2. 希爾排序表現驚人：平均 0.032 秒，甚至優於基數與堆排序，證明其在中等規模資料上的實用價值。
3. 快速排序非絕對最快：受亂數資料分布影響，分區不平衡導致效能波動大於希爾排序。
4. O(n²) 演算法完全不可用：插入與冒泡排序在 10 萬筆資料下需 15-60 秒，實務上僅適合極小規模或近乎有序資料。

選擇建議

• 資料範圍小、整數排序：首選計數排序
• 通用高效排序：希爾排序實作簡單、效能穩定、無遞迴開銷
• 大規模通用排序：快速排序（需隨機化基準值）或堆排序（保證 O(n log n) 最壞情況）
• 穩定排序需求：歸併排序（本文未實作）或基數排序（LSD 版本）

結語

效能測試證明：沒有萬能的排序演算法，只有最適合特定場景的選擇。理解各演算法的時間/空間複雜度、穩定性、資料敏感度，才能在實際工程中做出最佳決策。