11-1.c

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

#include  < stdio.h>
#define n 100 //假设的文件长度,即待排序的记录数目
typedef int KeyType; //假设的关键字类型
typedef struct{ //记录类型
   	 	KeyType key; //关键字项
    	//其它数据项,类型InfoType依赖于具体应用而定义
}RecType;
typedef RecType SeqList[n+1];
//SeqList为顺序表类型,表中第0个单元一般用作哨兵
void lnsertSort(SeqList R)
{ //对顺序表R中的记录R[1..n]按递增序进行插入排序
	int i,j;
    for(i=2;i<=n;i++) //依次插入R[2],……,R[n]
    if(R[i].key<R[i-1].key){//若R[i].key大于等于有序区中所有的keys,则R[i]
                             //应在原有位置上
       	R[0]=R[i];j=i-1; //R[0]是哨兵,且是R[i]的副本
       	do{ //从右向左在有序区R[1．．i-1]中查找R[i]的插入位置
       	 	R[j+1]=R[j];//将关键字大于R[i].key的记录后移
       		j-- ;
       	}while(R[0].key<R[j].key);//当R[i].key≥R[j].key时终止
    	R[j+1]=R[0];//R[i]插入到正确的位置上
   	}//endif
}//InsertSort
void Initial(SeqList R)
{
	//初始化
}
void main()
{
	SeqList R;
	Initial(R);
	lnsertSort(R);
}