直接插入排序算法

 //编写一个插入排序的算法，并且在main函数中验证其功能已实现

#include<iostream>
using namespace std;
const int maxsize=100;//排序表容量，假设为100
typedef int datatype;
typedef struct
{
datatype key;//关键字域
datatype other;//其他域
} rectype;//记录类型
typedef rectype list[maxsize+1];//排序表类型，0号单元不用

void InsertSort(list R,int n)
{
int i,j;
for(i=2;i<=n;i++)//依次插入R[2],R[3],、、、R[n]
{                       //R[i]大于有序区最后一个记录，则本躺不需要插入
if(R[i].key>=R[i-1].key) continue;
R[0]=R[i];//保存R[i]的副本
j=i-1;
do//查找R[i]的插入位置
{
R[j+1]=R[j];j--;//记录后移，继续向前搜索
} while(R[0].key<R[j].key);//当搜索到完后退出循环
R[j+1]=R[0];//插入R[i]
}
}

int main()
{
list R;
const int n=10;
cout<<"输入所有数据的关键字："<<endl;
for(int i=1;i<=n;i++)
{
cin>>R[i].key;
}
cout<<"调用直接插入排序函数InsertSort："<<endl;
InsertSort(R,n);
cout<<"输出排序后的关键字："<<endl;
for(int i=1;i<=n;i++)
cout<<R[i].key<<" ";
system("pause");
return 0;
}