数据结构笔记 – 排序算法 直接插入排序算法
本文由发表于6年前 | 数据结构与算法 | 暂无评论 |  被围观 5,910 views+

直接插入排序:

将一个元素通过和当前已经排序好的数组的最大元素进行比较,并在待插入数组较小的情况下通过设置哨兵,整体移动,插入正确位置的步骤,从此得到一个新的排序好的数组的过程。

#include <stdio.h>    

#define MAXSIZE 100  /* 待排序数组的大小 */

typedef struct
{
	int r[MAXSIZE+1];	/* 待排序数组r,r[0]为哨兵或临时变量 */
	int length;			/* 待排序数组的长度,为了方便理解,不包含r[0]元素 */
}SortList;

/* 直接插入排序算法 */
void InsertSort(SortList *L)
{
	int i,j;
	for(i=2;i<=L->length;i++)
	{
		/* 将r[i]插入有序数组前进行判断 */
		if (L->r[i]<L->r[i-1])
		{
			L->r[0]=L->r[i];	/* 设置哨兵 */
			for(j=i-1;L->r[j]>L->r[0];j--)
				/* 循环向右移动数据元素 */
				L->r[j+1]=L->r[j];
			L->r[j+1]=L->r[0]; /* 把r[i](此时存在r[0]中)插入到循环移动腾出的位置 */
		}
	}
}
直接插入排序时间复杂度分析:

最好的情况下,即每次需要插入的元素都是最大的,这样只需要比较n-1次,没有移动记录,所以时间复杂度为O(n)。

最坏的情况下,即待排序的是逆序的,此时需要比较的次数为:2+3+4+…+n=(n+2)(n-1)/2,而移动的次数为:(n+4)(n-1)/2。总得时间复杂度为O(n^2)。直接插入排序算法比冒泡和简单排序算法的性能要好一点。

除了文章中有特别说明,均为IT宅原创文章,转载请以链接形式注明出处。
本文链接:http://www.itzhai.com/data-structure-notes-directly-into-the-sorting-algorithm-sorting-algorithm.html
arthinking Java技术交流群:280755654,入门群:428693174 more
分享到:
 
如果您有更好的原创技术博文或者观点,欢迎投稿:admin@itzhai.com,或者关注订阅左侧浮动面板的微信号订阅IT宅itread)发送消息。
数据结构与算法推荐专题
文章评论
    没有评论
给我留言

有人回复时邮件通知我
数据结构与算法的相关文章
随机文章 本月热门 热评
1 jQuery中使用正则表达式验证电子邮件 2011/5/11
2 使用masm for windows编译并跟踪调试程序 2011/4/14
3 Hibernate关联映射创建数据库中存在的对象设置关联关系不级联保存的方法 2011/10/2
4 设计模式笔记 – Proxy 代理模式 (Design Pattern) 2011/10/8
5 密码保护:2014年计划和执行情况 2014/1/1
6 Java多线程FAQ汇总 2012/3/6
友情推荐 更多
破博客 文官洗碗安天下,武将打怪定乾坤。多么美好的年代,思之令人泪落。
Mr.5's Life 白天是一名程序员,晚上就是个有抱负的探索者
行知-追寻技术之美 关注大数据,分布式系统
我爱编程 编程成长轨迹
Cynthia's Blog 学习笔记 知识总结 思考感悟
 
猜您喜欢
欢迎关注我的公众号 IT宅
关于IT宅 文章归档

IT宅中的文章除了标题注明转载或有特别说明的文章,均为IT宅的技术知识总结,学习笔记或随笔。如果喜欢,请使用文章下面提供的分享组件。转载请注明出处并加入文章的原链接。 感谢大家的支持。

联系我们:admin@itzhai.com

Theme by arthinking. Copyright © 2011-2015 IT宅.com 保留所有权利.