直接插入排序（Straight Insertion Sort）的C语言实现

原创文章，转载请注明来自钢铁侠Mac博客http://www.cnblogs.com/gangtiexia

直接插入排序（Straight Insertion Sort）的基本思想是将新记录插入到已经排好序的有序表中，初始有序表只有无序表的第一个数据，依次对无序表每个数据进行直接插入排序，从而得到了有序表，具体步骤为

1. 若新记录<有序表高位l.r[j]，则设置哨兵
2. 有序表后移，j+1=j
3. 重复第2步，直至新纪录>=有序表中的j记录，则j+1就是要插入的位置

从而得到一个新的、记录数增加1的有序表。

演示实例：

C语言实现（编译器Dev-c++5.4.0，源代码后缀.cpp）

 #include <stdio.h>

 typedef float keyType;
 typedef struct{
     keyType score;
     char name[];
 }student;
 typedef struct{
     int length=;
     student stu[];
 }sqList;

 void SIS(sqList &L){
     for(int i=;i<L.length;i++){
         if(L.stu[i].score>L.stu[i-].score){
             L.stu[]=L.stu[i];//设置哨兵
             int j;
             for(j=i-;L.stu[].score>L.stu[j].score;j--)
                 L.stu[j+]=L.stu[j];//记录后移
             L.stu[j+]=L.stu[];//找到位置，插入元素
         }
     }
 }

 int main(){
     sqList L;

     for(int i=;i<L.length;i++){
         printf("\n请输入第%d个学生的姓名:",i);
         gets(L.stu[i].name);
         printf("分数:");
         scanf("%f",&(L.stu[i].score));
         getchar();
     }

     SIS(L);
     for(int i=;i<L.length;i++){
         printf("\n学生%s 分数%f 第%d名",L.stu[i].name,L.stu[i].score,i);
     }
 }