非遞歸快速排序實現：高效處理大規模數據

非遞歸快速排序算法詳解

快速排序是經典的分治算法，但遞歸實現容易導致棧溢出，尤其在處理大量數據時。本文介紹一種基於自定義棧結構的非遞歸快速排序實現，經測試可穩定排序 500 萬個整數數據。

核心思路

傳統遞歸利用系統調用棧保存分區邊界，非遞歸版本則手動維護一個棧結構 BUFF，存儲待排序區間的左右邊界。每次從棧頂取出一個區間進行分區，將產生的子區間壓入棧中，直到棧為空。

關鍵數據結構

typedef struct _BUFF {
    int *LeftBuff;   // 左邊界緩衝區
    int *RightBuff;  // 右邊界緩衝區
    DWORD number;    // 當前棧中元素個數
    struct _BUFF *next; // 擴展塊指針
} BUFF;

為應對極端情況（如已有序數組導致棧深度過大），採用鏈表式動態擴展：預分配 100 萬個邊界槽位，不足時分配新塊串聯。

分區邏輯

採用雙指針法，以區間首元素為基準值 key：

• left 從左向右找第一個 ≥ key 的元素
• right 從右向左找第一個 < key 的元素
• 交換兩者，直到 left >= right
• 最後將基準值換至 right 位置，完成一次分區

內存管理細節

• 初始分配雙緩衝區各 100 萬 int，約 8 MB
• 分配失敗時釋放已申請內存並報錯
• 棧擴展時同步分配新緩衝區，失敗則回滾釋放整條鏈
• 子區間入棧前檢查長度，長度 ≤ 1 不入棧
• 當前塊棧空且存在下一塊時，釋放下一塊回收內存

測試驗證

測試代碼生成 500 萬隨機數，調用 QuickSort 後以 ExamineArr 遍歷驗證有序性。輸出生成耗時與排序耗時，便於性能分析。

適用場景與優化建議

• 嵌入式環境或棧空間受限系統
• 大規模數據排序（百萬級以上）
• 可進一步優化：引入三數取中法選基準、小區間改用插入排序、尾遞歸消除

摘自 kevinshq 的專欄