Manchester- 数据结构-直接插入排序

解题思路:
①：插入排序思想：把顺序表分为两部分：一部分有序，一部分序

②：把无序的部分向有序的部分里面插，同时保持有序部分依旧有序

③：设置监视哨的目的减少比较次数，提高算法效率

1）：在插入过程从后向前找，直到找到小于监视哨元素的位置结束，或者没找到

2）：以上一般的过程为：当i<0,或者找到找到小于监视哨元素结束循环，每循环一次两次比较

3）：把0号元素作为监视哨(等于要插入的元素)，循环直接可设置为for(j=i-1;L->Data[0]<L->Data[j];j--)，仅有一次比较  也就是说不需要判断，指针是否到达了顺序表的头部，不用判断是否越界

④：查找到插入位置后，插入

⑤：输出结果

参考代码:

#include <stdio.h>
#include <malloc.h>
typedef struct L_ {
    int    *Data;
    int    length;
}*sqlist, SQLIST;

void InsertSort( sqlist L );

void In_put( sqlist L );

void Out_put( sqlist L );
/*===================================================*/
int main()
{
    SQLIST L;
    L.Data = NULL;

    while ( scanf( "%d", &L.length ) != EOF )  /*输入长度*/
    {
        L.Data = (int *) malloc( (L.length + 1) * sizeof(int) );  /*分配空间,比长度多一，0号位置用于放监视哨*/
        In_put( &L );/*输入数据*/
        InsertSort( &L );/*插入排序*/
        Out_put( &L );/*输出结果*/
        free(L.Data);/*释放空间*/
    }
    return(0);
}

/*===================================================*/
void InsertSort( sqlist L )
{
    int i, j;
    for ( i = 2; i <= L->length; i++ )        /*小于等于length因为起始元素下标为1*/
    {
        if ( L->Data[i] < L->Data[i - 1] )
        {
            L->Data[0] = L->Data[i];                /*把要插入的元素设置监视哨*/
            for ( j = i - 1; L->Data[0] < L->Data[j]; j-- )
                L->Data[j + 1] = L->Data[j];    /*查找插入位置*/
            L->Data[j + 1] = L->Data[0];            /*插入元素*/
        }
    }
}

/*===================================================*/
void In_put( sqlist L )
{
    for ( int i = 1; i <= L->length; i++ )
        scanf( "%d", &L->Data[i] );
}

/*===================================================*/
void Out_put( sqlist L )
{
    for ( int i = 1; i < L->length; i++ ) /*0号元素位置作为监视哨，整个有序列从1号元素开始*/
        printf( "%d ", L->Data[i] );
    printf( "%d\n", L->Data[L->length] );
}

别忘点赞哦-.-