Manchester


私信TA

用户名:wenyajie

访问量:20739

签 名:

男孩

排  名 3
经  验 12580
参赛次数 0
文章发表 152
年  龄 0
在职情况
学  校 Qing Dao University
专  业

  自我简介:

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

TA的其他文章

Manchester-汽水瓶问题
浏览:644  赞:39
Manchester- A+B for Input-Output Practice (IV)
浏览:203  赞:18
Manchester-A+B for Input-Output Practice
浏览:139  赞:15

解题思路:

总思路简述:

从第二个数起,依次选取一个数,和其前面的数比较,把其前面的比它大的数后移,直到找到第一个小于等于它的数,或者它前面的所有数遍历完为止,再把该数插入。


1):设带排序数为 5 4 3 2 1

①:选取第二个数 4,5>4

5后移一位,这次排序结果为:4 5    3 2 1

②:选取第三个数3,5>3

5后移一位,再4>3,4后移一位,这次排序结果为3 4 5    2 1

③:选取第四个数2,5>2后移,4>2后移,3>2后移,这次排序结果为2 3 4 5     1

④:选取第五个数1,5>1后移,4>1后移,3>1后移,2>1后移,这次排序结果为1 2 3 4 5


void InsertSort(int R[],int n)
{
    /*从第二个数开始依次选取一个数*/
    int term;/*保存选取的数*/
    int j;/*保存选取的数的前一个数的下标*/
    for(int i=1;i<n;i++)
    {
        term=R[i];/*保存选取的数*/
        j=i-1;/*保存选取的数的前一个数的下标*/
         /*开始依次向前比较,term前所有数比较完或者找到一个比term小的数结束循环*/
         while(j>=0&&term<R[j])
         {
             /*每次比较比若R[j]比term大,R[j]后移一位*/
             R[j+1]=R[j];
             j--;
         }
         R[j+1]=term;
         /*这里为R[j+1]=term;j要加1,可以这样理解①:假设上面循环以j<0结束,那么此时j=-1,要插
         入的位置为第一个元素位置,即j+1=0号位置
         ②:若找到第一个小等于于term的数时结束循环:即不满足term<R[j]时,term插入的位置为R[j]后,
         故依旧是R[j+1]=term;*/
         
    }
}


参考代码:

#include<stdio.h>
#include<malloc.h>

void InsertSort(int R[],int n);
void input(int R[],int n);
void output(int R[],int n);

int main()
{
    int n;/*元素个数*/
    int *R;/*数组指针*/
    while(scanf("%d",&n)!=EOF)
    {
        R=(int *)malloc(n*sizeof(int));/*开辟空间*/
        /*输入数据*/
        input(R,n);
        /*插入排序*/
        InsertSort(R,n);
        /*输出数据*/
        output(R,n);
        /*释放空间*/
        free(R);
    }
 return 0;
}
/*------------------------------------------------------------*/
void InsertSort(int R[],int n)
{
    /*从第二个数开始依次选取一个数*/
    int term;/*保存选取的数*/
    int j;/*保存选取的数的前一个数的下标*/
    for(int i=1;i<n;i++)
    {
        term=R[i];/*保存选取的数*/
        j=i-1;/*保存选取的数的前一个数的下标*/
         /*开始依次向前比较,term前所有数比较完或者找到一个比term小的数结束循环*/
         while(j>=0&&term<R[j])
         {
             /*每次比较比若R[j]比term大,R[j]后移一位*/
             R[j+1]=R[j];
             j--;
         }
         R[j+1]=term;
    }
}
/*------------------------------------------------------------*/
void input(int R[],int n)
{
    for(int i=0;i<n;i++)
        scanf("%d",&R[i]);
}
/*------------------------------------------------------------*/
void output(int R[],int n)
{
    for(int i=0;i<n;i++)
        printf("%d ",R[i]);
    printf("\n");
}

别忘点赞哦-.-

  评论区