排序算法-快速排序(非递归)

排序算法-快速排序(非递归)

1.选则最右则的元素作为划分元素v,然后从左则扫描小于v的元素,然后从右则扫描大于v的元素.
交换那些使扫描停止的元素.
2.重复进行这样的过程直到两个指针相遇.
3.然后分别对左右两步分进行递归处理.最终得到一个排好序的数组.

// 全局数据
int stack[128];// 堆栈
int ps;// 堆栈指针
//初始化堆栈
void init()
{
ps = 0;
}

//堆栈是否为空
int IsEmpty()
{
if(ps == 0)
return 1;
else
return 0;
}

// 压入
void push(int v)
{
stack[ps]=v;
++ps;// 指针加一
}

// 弹出
int pop()
{
if(ps == 0)
return = 0;
–ps;// 指针减一
return stack[ps];
}

下面给出C代码的实现.
//快速排序(非递归)
//a:数组
//l:数组的左则索引
//r:数组的右则索引
void quicksort(int a[],int l,int r)
{
init();
push(l);
push(r);

while(IsEmpty())
{
l=pop();
r=pop();
if(r<=l)
continue;
i=partition(a,l,r);
if(i-l < r-i)
{
push(l);
push(i-1);

push(i+1);
push(r);
}
else
{
push(i+1);
push(r);

push(l);
push(i-1);
}
}

}

// 划分算法
//a:数组
//l:数组的左则索引
//r:数组的右则索引
int partition(int a[],int l,int r)
{
int i,j,v,t;
i = l;
j = r;
v = a[j];//选则最右则的元素作为划分元素v
while(true)
{
while(a[i]<v)
++i;// i的左则小与v

while(v<a[j])
{
++j;// j的右则大与v
if(j==l)
break;// 跳出
}

if(i>=j)
break;// 两个指针相遇跳出扫描.

// 交换i,j,交换那些使扫描停止的元素.
t=a[i];
a[i]=a[j];
a[j]=t;
}

// 交换i,r,保证v的左则小于于它,v的右则大于它.
t=a[i];
a[i]=a[r];
a[r]=t;

return i;
}