习题－39.c

这些是数据结构结构的经典实现算法

//本程序只给出了算法思想
//读者可以自己完善本程序
typedef struct {
	int low;
	nt high;
} boundary; //子序列的上下界类型 
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 
int Partition(SQList &L,int low,int high)//一趟划分的算法,与书上相同
{
	L.r[0]=L.r[low];
	pivotkey=L.r[low].key;
	while(low<high)
	{
		while(low<high&&L.r[high].key>=pivotkey)
			high--;
		L.r[low]=L.r[high];
		while(low<high&&L.r[low].key<=pivotkey)
			low++;
		L.r[high]=L.r[low];
	}//while
	L.r[low]=L.r[0];
	return low;
}//Partition 
void Easy_Sort(SQList &L,int low,int high)//对长度小于3的子序列进行比较排序
{
	if(high-low==1) //子序列只含两个元素
		if(L.r[low].key>L.r[high].key) L.r[low]<->L.r[high];
		else //子序列含有三个元素
		{
			if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1];
			if(L.r[low+1].key>L.r[high].key) L.r[low+1]<->L.r[high];
			if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1];
		}
}//Easy_Sort