本人使用栈外栈模拟递归的过程。 以下是堆栈的结构、递归代码和非递归。
类型结构
{
int*base；
inttop；
}堆叠；
voidnonrec_quicksort(sqlistl，intlow，inthigh ) )。
//非递归快速排序
{
if(low=high ) )。
返回；
intleft；
intright；
intpivot；
星巴克；
S.base=newint[24]；
//log2300024
S.top=0；
S.base[S.top ]=high；
S.base[S.top ]=low；
while(s.top ) )。
{
left=S.base[--S.top]；
right=S.base[--S.top]；
pivot=get_pivotloc(L，left，right )；
//Get_pivotloc函数得到各支点的最终位置
if(pivot1)
{
S.base[S.top ]=right；
S.base[S.top ]=pivot 1；
}
左足
{
S.base[S.top ]=pivot-1；
S.base[S.top ]=left；
}
}
}
语音快速排序(sqlistl，intlow，inthigh ) )。
//递归快速排序
{
低电平
{
intpivot=get_pivotloc(L，low，high )；
快速排序(l，low，pivot-1 )；
快速排序(l，pivot 1，high )；
}
}
本人每次实验数据：排序6组，3000个元素
现在我有两个问题：
本人分别用递归排序和非递归排序对几乎相同的随机数据进行排序，但递归总是比非递归快，但并不快。 9秒左右。 为什么在同一堆栈的过程中，递归堆栈会很快，而本人写的堆栈过程会很慢呢？ 是本人优化不够，还是其他因素影响了？
本人进一步对一组初始状态顺序的数据进行排序，发现在非递归排序中，如果本人组元素有3000个，本人只需要给堆栈分配3个空间
S.base=newint[3]；
在本人分析并执行后，发现确实可以。 但是快速排序的空间复杂性不是o(log2n )吗？ 这个空间的复杂性是指堆栈空间还是其他？
这两个问题触及了本人知识的盲点…
虽然没有要求那样做
但是我很好奇，想知道……
大家有想法或答案吗？