插入排序——C语言
插入排序
插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
(每步将一个待排序的元素,按其排序码大小插入到前面已经排好序的一组元素的适当位置上去,直到元素全部插入为止)
(图片来源:https://www.cnblogs.com/fivestudy/p/10212306.html)
具体算法描述如下:
1、将待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列;
2、取出下一个元素,在已经排序的元素序列中从后向前扫描;
3、如果该元素(已排序)大于新元素,将该元素移到下一位置;
4、重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
5、将新元素插入到该位置后;
6、重复步骤2~5。
排序过程示例如下图:
(图片来源:https://www.cnblogs.com/chengxiao/p/6103002.html)
代码实现:
/* 插入排序*/
int num[] = {, , , , };
int pos, cur;
int i;
int length = sizeof(num)/sizeof(num[]); for (i = ; i < length; i++)
{
pos = i - ; //有序序列的最后一个元素位置
cur = num[i]; //保存待排序元素的值
while ( pos >= && num[pos] > cur)
{
num[pos + ] = num[pos];
pos--;
}
num[pos + ] = cur; //将待排序元素插入数组中
}
也可以写成两个for循环的形式,效果相同
/* 插入排序*/
int num[] = {, , , , };
int cur;
int i, j;
int length = sizeof(num)/sizeof(num[]); for (i = ; i < length; i++)
{
cur = num[i]; //待排序元素
for (j = i - ; j >= && num[j] > cur; j--)
{
num[j + ] = num[j];
}
num[j + ] = cur;
}
排序过程:以上面的例子来说排序的对象是 3,7,1,8,5 数组长度为5,因为第一个元素可以认为已经被排序,所以for循环的次数是:5(数组长度) - 1 = 4
第一次for循环:
3>7不成立,插入待排序元素,数组不变,此时有序序列为3,7
第二次for循环:
7>1成立,数组变成3,7,7,8,5
3>1成立,数组变成3,3,7,8,5
插入待排序元素,此时数组为1,3,7,8,5,有序序列为1,3,7
第三次for循环:
7>8不成立,插入待排序元素,数组不变,此时有序序列为1,3,7,8
第四次for循环:
8>5成立,数组变成1,3,7,8,8
7>5成立,数组变成1,3,7,7,8
3>5不成立,插入待排序元素,此时数组为1,3,5,7,8,有序序列为1,3,5,7,8,排序完成
最新文章
- Vue.js&mdash;&mdash;使用$.ajax和vue-resource实现OAuth的注册、登录、注销和API调用
- jvm系列(二):JVM内存结构
- 《征服 C 指针》摘录1:什么是空指针?区分 NULL、0 和 &#39;\0&#39;
- winform 进程,线程
- activitygroup下的activity不回调onactivityresult的解决方法
- Eclipse安装python注意事项
- require.js基本认识
- C#中() =>;是什么意思
- Supervisor的一些基础使用
- PHP上传图片至阿里云
- Linux系统的时区和时间调整
- ERP各个模块的缩写
- [转]Setting Keystone v3 domains
- html学习笔记之2——多媒体
- Java gc中的那些事
- operator的itemgetter和attrgetter
- C++Builder6.0 新建和打开项目软件死机
- js封装正则验证
- 【GIS新探索】算法实现在不规则区域内均匀分布点
- CentOS-Linux系统下安装Tomcat