解题思路:
总思路简述:
从第二个数起,依次选取一个数,和其前面的数比较,把其前面的比它大的数后移,直到找到第一个小于等于它的数,或者它前面的所有数遍历完为止,再把该数插入。
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"); }
别忘点赞哦-.-
0.0分
7 人评分
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:528 |
WU-蓝桥杯算法提高VIP-Quadratic Equation (C++代码)浏览:1742 |
C语言程序设计教程(第三版)课后习题6.11 (C语言代码)浏览:549 |
关于float,double变量的几点说明浏览:1810 |
1052题解(链表操作)浏览:651 |
字符逆序 (C语言代码)浏览:504 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:518 |
简单的a+b (C语言代码)浏览:635 |
母牛的故事 (C语言代码)浏览:451 |
C语言训练-最大数问题 (C语言代码)浏览:584 |