如何优化这种非递归快速排序以减少堆栈使用(c语言)

Question

这是一个实现快速排序的非递归程序，我使用数组来模拟堆栈的实现，但每次对数组的一部分进行排序时，占用空间都会呈指数级增加。如何优化此程序以减少使用量？就像重复使用以前丢弃的空间(X被遍历的地方(或其他什么，我真的很想弄清楚，提前谢谢。

#include <stdio.h>
#include <stdlib.h>
int stack[1000];
int partion(int a[],int begin,int end)
{
int l= begin;
int r= end;
int pole = a[begin];
while(l<r)
{
while(l<r && a[r]>=pole)
r--;
if(l<r)
{
a[l] = a[r];
l++;
}
while(l<r && a[l]<= pole)
l++;
if(l<r)
{
a[r] = a[l];
r--;
}
}
a[r]= pole;
return r;
}
void nonRecursiveQuickSort(int a[], int begin, int end);
int main()
{
int i;
int a[10]={0,1,-3,4,2,6,-9,0,8,10};
nonRecursiveQuickSort(a, 0, 10);
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
}
void nonRecursiveQuickSort(int a[], int begin, int end)
{
int l = begin;
int r = end;
//replace the stack with an array, which stores the split boundaries
int x = 0;
int y = 0;
//add left boundary
stack[y++] = l;
//add right boundary
stack[y++] = r;
// If the left boundary is smaller than the right boundary, the data to be processed is indicated
while (x < y)
{
// Simulate stack popout left boundary
int left = stack[x++];
//Simulate stack popout right boundary
int right = stack[x++];
// Call partition function 
int pos = partion(a, left, right);
//if Meet the conditions, repress the stack
if (left < pos - 1)
{
stack[y++] = left;
stack[y++] = pos - 1;
}
if (pos + 1 < right)
{
stack[y++] = pos + 1;
stack[y++] = right;
} 
}
}

Answer 1

调用nonRecursiveQuickSort(a, 0, 10)是错误的，因为这会导致在partion中引用[10]；正确的是CCD_ 3。

重用先前丢弃的空间(其中X已被遍历(

为此，名为stack的FIFO中的索引x和y将环绕在数组的末尾。nonRecursiveQuickSort中循环的这个修改版本可以做到这一点，还带有防止溢出的检查：

#define DIM sizeof stack / sizeof *stack    // DIM must be even
while (x != y)
{
// Simulate stack popout left boundary
int left = stack[x++];
//Simulate stack popout right boundary
int right = stack[x++];
if (x == DIM) x = 0;    // wrap around
// Call partition function 
int pos = partion(a, left, right);
//if Meet the conditions, repress the stack
if (left < pos - 1)
{
stack[y++] = left;
stack[y++] = pos - 1;
if (y == DIM) y = 0;    // wrap around
if (y == x) puts("FIFO full"), exit(1);
}
if (pos + 1 < right)
{
stack[y++] = pos + 1;
stack[y++] = right;
if (y == DIM) y = 0;    // wrap around
if (y == x) puts("FIFO full"), exit(1);
} 
}