求快速排序的非递归算法

longwen

快速排序的递归算法
[code:1]

void quicksort(int data[],int low,int high)
{
int i,pivotkey,j;

if(low<high)
{
i=pivotkey=low;
j=high;

while(i<j)
{
while(i<j && data[j]>=data[pivotkey] )  --j;
if(i<j)  data[i+1]=data[j];

while(i<j && data[i]<=data[pivotkey])  ++i;
if(i<j)  data[j--]=data[i];
}
}
data[i]=data[pivotkey];
quicksort(data,low,i-1);
quicksort(data,i+1,high);
}
[/code:1]

sagaeon

求？你的程序不对吗？

longwen

我想要一个 非递归 算法，谢谢

sagaeon

哦，没看清楚。网上搜搜吧。我搜的[code:1]void QSort_NotRecurve(int SQList &L)//快速排序的非递归算法
{
  low=1;high=L.length;
  InitStack(S); //S的元素为boundary类型
  while(low<high&&!StackEmpty(S)) //注意排序结束的条件
  {
    if(high-low>2) //如果当前子序列长度大于3且尚未排好序
    {
      pivot=Partition(L,low,high); //进行一趟划分
      if(high-pivot>pivot-low)
      {
        Push(S,{pivot+1,high}); //把长的子序列边界入栈
        high=pivot-1; //短的子序列留待下次排序
      }
      else
      {
        Push(S,{low,pivot-1});
        low=pivot+1;
      }
    }//if
    else if(low<high&&high-low<3)//如果当前子序列长度小于3且尚未排好序
    {
      Easy_Sort(L,low,high); //直接进行比较排序
      low=high; //当前子序列标志为已排好序
    }
    else //如果当前子序列已排好序但栈中还有未排序的子序列
    {
      Pop(S,a); //从栈中取出一个子序列
      low=a.low;
      high=a.high;
    }
  }//while
}//QSort_NotRecurve [/code:1]