Manchester- 数据结构-直接插入排序(简化版增强版)

解题思路:

总思路简述：

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

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

别忘点赞哦-.-