一般的快速排序是用递归来实现的，如何将快速排序改写为迭代而不是递归？由于递归函数需要保护现场（在栈中），所以可以认为的构建一个栈。
由于快速排序中处理排序是partition子函数（过程），然后将划分范围减小，来实现排序。所以要保存的是待继续排序（划分）的边界。这样的一个栈很容易自我构建。
#include <iostream>
using namespace std;
//划分子函数
int partition(int a[],int low,int high)
{
int len=high-low+1;
if(len<2) return low ;
int i=low; //前段搜寻标
int j=high+1; //号,注意这里i=
int key=a[low];
for(;;)
{
do i++; while(i<=high&&a[i]<key);
do j--; while(a[j]>key);
if(i>=j) break;
swap(a[i],a[j]);
}
swap(a[low],a[j]);
return j;
}
//递归版本的qsort
void QuickSort2(int a[],int len)
{
if(len<2) return;
int j=partition(a,0,len-1);
QuickSort2(a,j);
QuickSort2(a+j+1,len-j-1);
}
//非递归版本qsort
void QuickSortND(int a[],int low,int high)
{
if(high-low<1) return;
int* stk=new int[high-low+1];
int p=0;
int l,h,m;
stk[p++]=low;
stk[p++]=high;
while(p!=0)
{
h=stk[--p];
l=stk[--p];
if (l<h)
{
m=partition(a,l,h);
if (m-1>l)
{
stk[p++]=l;
stk[p++]=m-1;
}
if (m+1<h)
{
stk[p++]=m+1;
stk[p++]=h;
}
}
}
delete[] stk;
}
//改变接口，重载的非递归版本
void QuickSortND(int a[],int len)
{
if(len<2) return;
int* stk=new int[len];
int p=0;
int l,h,m;
stk[p++]=0;
stk[p++]=len-1;
while(p!=0)
{
h=stk[--p];
l=stk[--p];
if (l<h)
{
m=partition(a,l,h);
if (m-1>l)
{
stk[p++]=l;
stk[p++]=m-1;
}
if (m+1<h)
{
stk[p++]=m+1;
stk[p++]=h;
}
}
}
delete[] stk;
}
int main()
{
int a[30]={0};
for (int i=0;i<30;i++)
a[i]=rand()%500;
for (i=0;i<30;i++)
cout<< a[i]<<endl;
//QuickSortND(a,0,29);
QuickSortND(a,30);
//QuickSort2(a,30);
cout<<"____________________________________"<<endl;
for (i=0;i<30;i++)
cout<< a[i]<<endl;
return 0;
}