直接插入排序.cpp

这里面包括数据结构多数的算法

#include <stdio.h>
typedef int InfoType;

#define n 10					//假设的文件长度，即待排序的记录数目
typedef int KeyType;			//假设的关键字类型
typedef struct {				//记录类型
	KeyType key;				//关键字项
	InfoType otherinfo;			//其它数据项，类型InfoType依赖于具体应用而定义
} RecType;
typedef RecType SeqList[n+1];	//SeqList为顺序表类型，表中第0个单元一般用作哨兵

void main()
{
	void InsertSort(SeqList R);
	int i;
	SeqList R;
	printf("请输入欲排序的数：");
	for (i=1;i<=n;i++)
		scanf("%d",&R[i].key);
	printf("排序前：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
	InsertSort(R);
	printf("排序后：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
}

void InsertSort(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];				//R[0]是哨兵，且是R[i]的副本
			j=i-1;
			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]插入到正确的位置上
		}
}