直接插入排序

直接插入排序：是一种简单的排序方法，它的基本操作时将一个记录插入到已排好的有序表中，从而得到一个新的，记录加一的有序表。

#include<stdio.h>
#define MAXSIZE 20
#define N 10
typedef int KeyType;
typedef char InfoType;
typedef struct
{
    KeyType key;
    InfoType otherinfo;
}ReadType;
typedef struct
{
    ReadType r[MAXSIZE+1];
    int length;
}Sqlist;
void InitSq(Sqlist * L);
void InsertSort(Sqlist *L);
void main()
{
    Sqlist Sqlist1;
    int i;
    InitSq( &Sqlist1);
    printf("请输入%d个数字用插入法进行排序\n",N-1);
    for(i=1;i<N;i++)//第i=0位留着作为哨兵
    {
        scanf("%d",&Sqlist1.r[i].key);
        Sqlist1.length++;
    }
    printf("排序前：\n");
        for(i=1;i<N;i++)
    {
        printf("%d",Sqlist1.r[i].key);
    }

    InsertSort(&Sqlist1);

    printf("排序后：\n");
    for(i=1;i<N;i++)
    {
        printf("%d ",Sqlist1.r[i].key);
    }
    system("pause");
}
void InitSq(Sqlist * L)
{
    int i;
    for(i=0;i<=MAXSIZE;i++)
    {
        L->r[i].key=0;
        L->length=0;

    }
}
void InsertSort(Sqlist *L)
{
    int i,j,k;
    for(i=2;i<N;i++)
    {
        L->r[0]=L->r[i];//把要插入的数据保存的第一位，作为哨兵
        for(j=i;j>0;j--)
        {
         if(L->r[j-1].key <= L->r[0].key)//从后面往前对比大小
         {

            for(k=i;k>j;k--)
            {
                L->r[k]=L->r[k-1];
            }
            L->r[j]=L->r[0];
            break ;//插入数据后后就退出本次循环
         }

        }
    }
}

排序算法改进如下：
 

void InsertSort(Sqlist *L)
{
    int i,j;
    for(i=2;i<=L->length;i++)
    {
        if(L->r[i].key<L->r[i-1].key)
        {
            L->r[0]=L->r[i];
            L->r[i]=L->r[i-1];
            for(j=i-2;L->r[0].key<L->r[j].key;--j)
                L->r[j+1]=L->r[j];
            L->r[j+1]=L->r[0];
        }
    }
}