【数据结构取经之路】快速排序的非递归实现

概述

递归实现快速排序在一些场景下有栈溢出的风险，下面就谈谈如何用非递归的方法实现快速排序。

非递归实现的思想

递归实现与非递归实现快速排序的本质是一致的，效率并不会因为用了非递归实现而有所提升。递归实现快速排序的本质就在于通过递归，可以对不同长度的子数组进行快速排序，例如，第一次调用时处理的区间是[0,9]，第二次调用时处理的区间是[0,4]……借助栈，也可以实现递归的本质功能——分割数组，对子数组进行快速排序。

非递归过程展开图

代码

 

void QuickSortNonR(int* a, int begin, int end)
{ST st;//创建栈STInit(&st);//初始化栈STPush(&st, end);//插入数据STPush(&st, begin);//插入数据while (!STEmpty(&st)){int left = STTop(&st);STPop(&st);int right = STTop(&st);STPop(&st);int keyi = PartSort(a, left, right);//判断区间是否为空或只有一个值if (keyi + 1 < right){STPush(&st, right);STPush(&st, keyi + 1);}//判断区间是否为空或只有一个值if (left < keyi - 1){STPush(&st, keyi - 1);STPush(&st, left);}}
}