插入排序算法,C语言插入排序算法详解
那么插入排序到底是怎样的呢?比如有十个人从左往右无序地排列,现在要你按身高从低到高排列,你会怎么排?
首先第二个人和第一个人比,如果第二个人比第一个人矮,那么它们互换位置,否则不动,此时前两个人的顺序就排好了;然后第三个人再与前两个已经排好的比,怎么比?第三个人先站出来,看看前面在哪个位置中自己比左边的高比右边的矮,然后就插进去,如果自己与前面的人相比是最高的,那么就不动,此时前三个人的顺序就排好了 就这样一直往后比较。
那么怎么找比左边高比右边矮的那个位置呢?因为左边都是已经排好序的,所以依次与左边的比,直到遇到一个比他矮的,那么那个位置就是比左边高比右边矮的位置。如果没找到一个比他矮的那么他就是最矮的,那么他就排在最左边。那么是怎么插入的呢?因为每个与左边一个一个比较的那个人都是先站出来的,所以他的那个位置是空的。这时在找到比他矮的那个人之前,每比完一个,与他进行比较的那个人就往右挪一个位置,将空依次补上。直到找到比他矮的人,那时比他矮的那个人的前面就空出了一个位置,然后他就可以插进去。所以在程序中要先用一个变量保存这个 站出来的 数。
下面来写一个插入排序的算法实现从小到大排序。
# include stdio.h int main(void) int i, j; int temp; //用于存储站出来的数 int a[] = {900, 2, 3, -58, 34, 76, 32, 43, 56, -70, 35, -234, 532, 543, 2500}; int n = sizeof(a) / sizeof(a[0]); //存放数组a中元素的个数 for (i=1; i i++) /*i从1开始, 即从第二个人开始比, 每循环一次比较一轮*/ temp = a[i]; j = i - 1; //与它前一个数比较 while ((j =0) (a[j] temp)) /*与左边所有人都比完了或找到一个比他矮的为止*/ a[j+1] = a[j]; //与他比完之后比它高的向右挪一个位置 --j; /*最经典的地方, 每次减1, 再与前一个比较, 直到与左边所有的都比完或比到有一个数小于等于它为止, while循环退出, 此时左边形成一个新的有序序列*/ if (j != i-1) /*这句也很经典, j != i-1说明执行过上面的while, 并且找到位置了, 那么就插进去;如果j = i-1, 则说明没有执行过while, 说明他和左边的相比是最高的, 则不用换位置*/ a[j+1] = temp; /*之所以j要加1是因为while在退出之前又执行了一次--j*/ for (i=0; i ++i) printf( %d/x20 , a[i]); printf( /n return 0; }
输出结果是:
-234 -70 -58 2 3 32 34 35 43 56 76 532 543 900 2500
冒泡排序是从左往右比,而插入排序是从右往左比,但也是一轮一轮地比较。原序列中从左边第二个数开始,每轮比较一个数。每个数依次与它左边的所有数相比较,左边的都是已经排好的序列,该数与这些排好的序列逐个比较,然后插入其中,形成一个新的排好的序列。
从程序中也可以看出,如果是将一个数据插入已经排好的序列中,使用插入排序无疑是最好的选择。此时计算量只不过是冒泡排序的一轮比较而已。比如向序列 1 3 4 5 7 9 11 13 20 插入一个 6,用插入排序就非常简单了。程序如下:
# include stdio.h int main(void) int a[10] = {1, 3, 4, 5, 7, 9, 11, 13, 20}; int i = 8; //存储数组有效数据的最大下标 int data = 0; //存储要插进来的数 printf( 请输入要插进来的数: scanf( %d , data); while ((i =0) (a[i] data)) /*找到data应该插入的位置, 并把那个位置空出来*/ a[i+1] = a[i]; --i; a[i+1] = data; //将data插入那个位置 for (i=0; i ++i) printf( %d/x20 , a[i]); printf( /n return 0; }
输出结果是:
请输入要插进来的数:6
1 3 4 5 6 7 9 11 13 20
需要注意的是,前面的程序中数组的长度都没有手动指定,而上面这个程序是手动指定了数组的长度为 10。这是为什么?
这是因为,如果不手动给定还是写成 int a[]={1,3,4,5,7,9,11,13,20}; 这种形式的话,那么系统就会根据初始化数据的个数认为该数组的长度为 9。但是现在要往该数组中插入一个元素,那么数组的长度至少是 10,不然插入数据后,数组的最后一个元素就会向后覆盖一个 int 型的未分配给它的内存空间。
所以为了避免这种情况的发生,就只能手动指定数组的长度。但是这样的话就意味着不能再通过 sizeof(a)/sizeof(a[0]) 来计算数组中存放的有意义的数据的长度,因为 sizeof(a)/sizeof(a[0]) 计算的是数组的总长度。这也就意味着只能通过手动的方式指定数组中存放有意义的数据的元素的最大下标 i。
综上所述,这种情况就需要程序员自己手动维护数组的长度。这也从某一方面体现出了数组的缺陷,即它无法动态地扩充长度。动态数组和链表就不存在数组的这个缺陷,这两种结构后续会讲。
21498.html
相关文章
- 浙大版《C语言程序设计(第3版)》题目集 71~80
- 简单常用滤波算法C语言实现「建议收藏」
- 使用回溯法解0/1背包问题n=3,c=9_背包问题C语言算法
- 马拉车算法 (最长回文串 例题 密码截获)----C语言—菜鸟级
- 欧拉函数模板-----------C语言—菜鸟级
- 二分匹配 匈牙利算法 模板-------------------C语言——菜鸟级
- 一个c语言程序能实现几种算法_C语言实现算法
- 【安全算法之SHA256】SHA256摘要运算的C语言源码实现
- 数组倒序排列,数组倒置,C语言数组倒序算法详解
- 冒泡排序算法,C语言冒泡排序算法详解
- 快速排序算法,C语言快速排序算法详解
- gets函数,C语言gets函数详解
- C语言二分查找算法,折半查找算法
- 学会用Linux C语言熟练替换字符!(linuxc字符替换)
- 改变世界的Linux在C语言下的崛起(linuxatc)
- C语言MySQL实现存储文件的功能(c mysql存储文件)
- 实践C语言连接Oracle数据库的最佳实践(c oracle最佳)
- C语言实现魔方阵算法(幻方阵奇魔方单偶魔方实现)
- C语言快速幂取模算法小结
- C语言实现二叉树遍历的迭代算法