一、快速排序回顧

????????快速排序本質上是**“分而治之”（Divide and Conquer）策略的遞歸應用。但遞歸其實就是函數棧的一種體現，因此我們也可以顯式使用棧（stack）來模擬遞歸過程**，從而實現非遞歸版本的快速排序。

往期“快速排序算法回顧”：

快速排序--挖坑法
快速排序-- 分而治之

快速排序--前后指針法

注意：我們這里只是利用棧來模擬遞歸過程，遞歸算法會多次開辟額外的棧幀，利用棧的實現可以有效優化，避免爆棧。

🧱 二、利用棧實現非遞歸：

1. 創建一個棧（保存左右區間的邊界值）；

2. 把整個初始區間?[0, size-1]?入棧；

3. 當棧不為空時：

   • 彈出一個區間?[left, right]；

   • 對該區間做一次?Partition（分區）；可利用前面我們學過的”前后指針“，”挖坑法“等

   • 得到劃分下標?pivot；

   • 如果?[left, pivot-1]?有效，則入棧；

   • 如果?[pivot+1, right]?有效，則入棧；

4. 重復，直到棧為空。

思維導圖：

代碼實現：

void QuickSort_stack(int* arr,int left,int right){assert(arr);if(left>=right){return;}int size = right+1;int* stack  = (int*)malloc(2*size*sizeof(int));//建立棧int top = 0;//先入左邊，再入右邊stack[top++] = left;stack[top++] = right;while (top>0){// 先進后出，所以先出右邊int right  = stack[--top]; //注意 -- 的用法int left  = stack[--top];if(left<right){int div = PartSort2(arr,left,right); //利用分而治之的思想if(left<div-1){stack[top++] = left;stack[top++] = div-1;}if(div+1<right){stack[top++] = div+1;stack[top++] = right;}}}
}

三、遞歸以及棧調用對比

項目	遞歸版	非遞歸（棧模擬）
結構	簡潔，易讀	稍復雜，需維護棧
系統棧	占用系統調用棧	手動棧，控制更靈活
棧溢出風險	有，尤其數據近似有序	可優化，避免爆棧
應用場景	一般排序足夠	資源受限場景、控制棧深度
可改進性	難以精細控制	可結合尾遞歸優化、棧平衡策略

四、📘 總結

棧實現快速排序的核心是把遞歸中“待處理的區間”壓入一個顯式棧，依次取出處理，用 迭代方式完成原本的遞歸流程。這樣做不僅可以避免函數棧溢出，還可以為后續的性能優化提供空間。

?五、進一步優化建議

1. 棧小區間優先處理（如先壓小區間）可以避免棧過深；

2. 對小區間（如 <16 元素）可以切換為插入排序，提高性能；

3. 使用“三數取中”或“隨機選主元”策略改善最壞情況；