【非递归版】快速排序算法（4）

前面学习了三种版本的递归快排。面试的时候也经常考察非递归版的快排。考察非递归其实也是在考察递归，因为递归与非递归是有相似之处。不是递归神似递归。

QuickSortNonR快速排序

在数据量过大的情况下，递归版的快排还是会出现栈溢出的现象。要考虑用其他空间实现快排。

区分两个概念

• 数据结构的栈（利用的是内存中的堆空间）
• 内存的栈（利用就是内存中的栈空间）>>>>函数创建函数栈帧
• 堆的空间是远远大于栈的空间

递归改非递归

• 单独递归：改成循环（阶乘/斐波那契数列/链表的遍历/合并）
• 双度递归：循环+借助其他数据结构（二叉树/快排/归并等等）
• 非递归都有一个特点：不是递归胜似递归。

思路

• 快排的分治：左序列+key+右序列
• 递归：把子问题放到函数栈帧（借助栈的空间）
• 非递归：把子问题放到数据结构的栈（借助堆的空间）
• 借助数据结构的栈，非递归实现递归，相当于非递归借助栈来模拟递归的过程
• 模拟递归，并不是递归，思考&体会>>>>>递推和回归这个过程怎样模拟的。
• ❗❗❗❗❗❗快排是一种前序递归，所以可以借助栈（后面详细分析）

整体思路

• 相当于把区间存储在栈里面
• 拿区间序列去单趟排序
• 入栈和出栈，就相当于函数递归
• 限制区间不入栈 ≈ 函数递归的返回条件return

1. 入栈单趟排序的区间。（入栈的条件是只有有一个元素）
2. 出栈区间确定left 和 right。
3. 单趟排序确定keyi。
4. 利用keyi确定再次入栈的区间[left,keyi-1] keyi [keyi+1,right]。
5. 重复上述过程，直到栈为空，则序列排序完成。

易错点

• 入栈的条件left < right。
• 栈为不为空就继续，栈为空就结束。
• 栈的特点：先入后出，后入先出
• 对于区间，先入end，后入begin
• 先出begin,后出end
• 对于子问题，先入右序列，后入左序列
• 先处理左序列，后处理右序列

图解分析

代码实现

//非递归
void QuickSortNonR(int* a, int begin, int end)
{
  //栈
  ST stack;
  STInit(&stack);
  //入栈0~9
  STPush(&stack,end);
  STPush(&stack, begin);
  while (!STempty(&stack))
  {
    //出栈
    int left= STTop(&stack);
    STPop(&stack);
    int right = STTop(&stack);
    STPop(&stack);
    int keyi = PartSort1(a, left, right);//1/2/3都可
    //入栈[left, keyi-1] keyi [keyi+1,right]
    //处理左边
    if (left < keyi-1)
    {
      STPush(&stack, keyi-1);
      STPush(&stack, left);
    }
    //处理右边
    if (keyi+1 < right)
    {
      STPush(&stack, right);
      STPush(&stack, keyi+1);
    }
  }
  STDestroy(&stack);
}

🙂感谢大家的阅读，若有错误和不足，欢迎指正。下篇归并排序。快速排序多总结总结。