（1）设计一个快速排序的非递归算法并上机实现。
（2）编写双向冒泡排序算法并上机实现。
（3）编写一个快速排序的非递归算法并上机实现。
（1）使用一个栈保存中间子区间，非递归算法如下：
#include <stdio.h>
#define MaxSize 20 /*最多记录个数*/
typedef int KeyType; /*关键字类型*/
typedef char ElemType[10]; /*其他数据项类型*/
typedef struct
{
KeyType key; /*关键字域*/
ElemType data; /*其他数据域*/
} LineList; /*线性表元素类型*/
void Split(LineList R[],int low,int high,int &i) /*以R[low]为基准划分R*/
{
int j;
LineList tmp;
i=low;j=high;tmp=R[i]; /*初始化*/
while(i<j)
{
while(R[j].key>=tmp.key && i<j) /*从右向左扫描*/
j--;
R[i]=R[j]; /*相当于交换R[i]与R[j]*/
while(R[i].key<=tmp.key && i<j) /*从左向右扫描*/
i++;
R[j]=R[i]; /*相当于交换R[i]与R[j]*/
}
R[i]=tmp; /*tmp定位在位置i处*/
}
void QSort(LineList R[],int n)
{
int i,low,high;
int St[MaxSize][2],top=-1;
low=0;high=n-1;
top++; /*进栈*/
St[top][0]=low;St[top][1]=high;
while(top>=0) /*栈不空时循环*/
{
low=St[top][0];high=St[top][1]; /*出栈*/
top--;
Split(R,low,high,i);
if(low<high) /*当low<high时继续划分，否则只有一个元素,保持不变*/
{
top++; /*左区间进栈*/
St[top][0]=low;St[top][1]=i-1;
top++; /*右区间进栈*/
St[top][0]=i+1;St[top][1]=high;
}
}
}
（2）双向冒泡排序是指相邻的两趟排序向相反的方向冒泡，即一次将最大值向后移，另一次将最小值向前移。
void BiBubble_Sort(ReeType r[],int n)
{
int I,j,k;
ReeType x;
j=1;k=1;
while((j<=n/2)&&(k>0))
{
k=0;
for(i=j-1;i<n-j;i++)
if(r[i+1].key<r[i].key)
{
k++;
x=r[i];
r[i]=r[i+1];
r[i+1]=x;
}
if(k==0)break;k=0;
for(i=n-j-1;i>j-1;i--)
if(r[i].key<r[i-1].key)
{
k++;
x=r[i];
r[i]=r[i-1];
r[i-1]=x;
}
j++;
}
}
（3）快速排序的非递归算法描述如下（其中s为顺序栈）：
Void Quicksortl(ReeType r[],int n)
{
int top,low=0,high=n,i,j,*s;
ReeType x;
S=(int*)malloc(sizeof(int)*2*n);
top=0;
do{
while(low<high)
{
i=low;j=high;x=r[i];
do{
while((r[j].key>=x.key)&&(i<j))
j--;
if(i<j)
{
r[i]=r[j];
i++;
}
while((r[i].key<=x.key)&&(j>i))
i++;
if(i<j)
{
r[j]=r[i];
j--;
}
}while(i<j);
r[i]=x;
if((i+1)<high)
{
S[+ +top]=i+1;
S[+ +top]high;
}
high=i-1;
}
if(top>0)
{
low=S[top--];
high=S[top--];
}
}while(top>0||low<high);
}