解题思路:
①:插入排序思想:把顺序表分为两部分:一部分有序,一部分序
②:把无序的部分向有序的部分里面插,同时保持有序部分依旧有序
③:设置监视哨的目的减少比较次数,提高算法效率
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] ); }
别忘点赞哦-.-
0.0分
9 人评分
printf基础练习2 (C语言代码)浏览:591 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:584 |
ASCII帮了大忙浏览:748 |
C语言程序设计教程(第三版)课后习题6.5 (C++代码)浏览:447 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:561 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:2158 |
【偶数求和】 (C++代码)浏览:698 |
明明的随机数 (C语言代码)浏览:953 |
字符串对比 (C++代码)浏览:555 |
C二级辅导-统计字符 (C语言描述——用函数求解)浏览:1178 |