目錄

1.引入

?2.非遞歸實現快排的思想

3.非遞歸實現快排圖解

4.完整代碼

---

?

1.引入

遞歸不可避免的話題就是防止棧溢出

所以程序員需要具備遞歸改非遞歸的能力 ，一般來說，抓住遞歸中變化的量是關鍵

void QuickSort(int* a, int left, int right){if (left >= right)return;if (right - left + 1 < 10){InsertSort(a + left, right - left + 1);}else{int keyi = PartSort1(a, left, right);//[left, keyi - 1] keyi [keyi + 1, right]QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}
}

遞歸調用實現快速排序類似于二叉樹的前序遍歷(根、左子樹、右子樹)

仔細觀察可知，棧幀中變化的是具體的區間邊界

?2.非遞歸實現快排的思想

配合使用棧這種結構以模擬遞歸實現快排時的前序遍歷

先將起始區間邊界存入棧中，然后取出邊界，進行快排的單趟排序得到分界位置的下標，以此為界將數組分割為左右兩部分，然后先將右部分的區間邊界存入棧中，再將左部分的區間邊界存入棧中(區間大小大于1才將邊界存入棧中)，再從棧中取出區間邊界進行單趟排序，再分割數組并存入區間邊界....直到棧為空為止

簡單來說就是存邊界、取邊界排序、分數組存邊界、取邊界排序、分數組存邊界.......

3.非遞歸實現快排圖解

依據思想，?存邊界、取邊界排序、分數組存邊界、取邊界排序、分數組存邊界.......

直到棧為空時停止，此時數組有序

4.完整代碼

typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;
//初始化
void STInit(ST* ps);
//銷毀
void STDestroy(ST* ps);
//壓棧
void STPush(ST* ps, STDataType val);
//出棧
void STPop(ST* ps);
//大小
int STSize(ST* ps);
//判空
bool STEmpty(ST* ps);
//訪問棧頂
STDataType STTop(ST* ps);void QuickSortNonR(int* a, int left, int right){//區間不存在就返回if (left >= right)return;//小規模數組直接優化if (right - left + 1 < 10){InsertSort(a + left, right - left + 1);return;}//C語言實現的棧ST st;STInit(&st);//先壓右，再壓左，順次取出就是區間STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);//小規模數組直接優化if (end - begin + 1 < 10){InsertSort(a + begin, end - begin + 1);continue;}int keyi = PartSort3(a, begin, end);//[begin, keyi - 1] keyi [keyi + 1, end]if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}}STDestroy(&st);
}

注意邊界的存入方式 、小規模數組可以進行優化