数据结构之 【排序】(非递归实现快速排序)

目录

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);}

注意边界的存入方式 、小规模数组可以进行优化