Manchester


私信TA

用户名:wenyajie

访问量:23902

签 名:

男孩

排  名 3
经  验 13188
参赛次数 0
文章发表 154
年  龄 0
在职情况
学  校 Qing Dao University
专  业 计算机科学

  自我简介:

干大事,12月26号之后长期回归

TA的其他文章

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

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

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

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] );
}

别忘点赞哦-.-

  评论区