四大經典排序算法效能比較：Shell、Quick、Heap、Merge 實戰測試

排序算法效能比較系統：設計與實現

本文介紹一個完整的排序算法比較程式，實現了 Shell Sort、Quick Sort、Heap Sort、Merge Sort 四大經典算法，並提供互動式選單系統，可對相同資料集進行排序耗時、比較次數、移動次數的量化分析。適用於演算法課程教學與效能評估參考。

系統架構與功能模組

程式採用模組化設計，主要包含：

• 資料管理：支援手動輸入、檔案匯入、結果儲存
• 排序引擎：四種算法獨立實現，統一介面
• 效能統計：全域變數 compCount、shiftCount 記錄比較/移動次數
• 計時機制：採用 clock() 測量 CPU 時間
• 選單系統：多層巢狀選單控制流程

四大算法核心實現亮點

Shell Sort（希爾排序）

採用 gap = n/2 遞減增量序列，實現分組插入排序。程式碼中嵌入詳細的計數邏輯，精確統計每次比較與移動。

Quick Sort（快速排序）

採用單向掃描分區策略（Partition），以首元素為基準，透過 key[0] 暫存基準值。遞迴實現 QSort，展示經典分治思想。

Heap Sort（堆積排序）

底層以 sift 下沉操作維護大頂堆。先建堆（length/2 到 1），再重複交換堆頂與末尾元素並縮小堆範圍。空間複雜度 O(1)。

Merge Sort（合併排序）

非遞迴自底向上實現（Merge + Mergesort），雙緩衝區交替合併，避免遞迴開銷。動態分配暫存陣列 temp，體現空間換時間策略。

效能指標測量方法

每次排序前歸零計數器，排序後輸出：

SHELLSORT COST TIME : 0.001234 SECONDS.
Compare 1245 times. Shift 832 times.

此設計便於分析算法在不同資料分佈（有序、逆序、隨機）下的真實表現。

教學與實用價值

1. 直觀比較 O(n²) 與 O(n log n) 算法的實際效能差距
2. 理解比較次數與移動次數對不同算法的影響權重
3. 學習模組化 C 程式設計：函數指標、結構體傳遞、檔案 I/O
4. 體驗選單驅動式介面的狀態管理（鎖旗標 LOCK* 控制操作順序）

完整程式碼包含錯誤處理、記憶體檢查、跨平台考量（CLK_TCK），可直接在 Turbo C / GCC 環境編譯執行。