习题－35.c

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

//本程序只给出了算法思想
//读者可以自己完善本程序

void BiInsert_Sort(SqList &L)//二路插入排序的算法
{
	int d[MAXSIZE]; //辅助存储
	x=L.r .key;d =x;
	first=1;final=1;
	for(i=2;i<=L.length;i++)
	{
		if(L.r[i].key>=x) //插入前部
		{
			for(j=final;d[j]>L.r[i].key;j--)
				d[j+1]=d[j];
			d[j+1]=L.r[i].key;
			final++;
		}
		else //插入后部
		{
			for(j=first;d[j]<L.r[i].key;j++)
				d[j-1]=d[j];
			d[(j-2)%MAXSIZE+1]=L.r[i].key;
			first=(first-2)%MAXSIZE+1; //这种形式的表达式是为了兼顾first=1的情况
		}
	}//for
	for(i=first,j=1;d[i];i=i%MAXSIZE+1,j++)//将序列复制回去
		L.r[j].key=d[i];
}//BiInsert_Sort