加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

直接插入排序

(2013-08-26 23:06:27)
标签:

直接插入排序

insertsort

算法

it

分类: 数据结构

直接插入排序

直接插入排序为稳定排序,基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增加1的有序表。直接插入排序属于稳定的排序,时间复杂度为O(n*n),辅助空间为O(1)。

基本思想:假设在排序过程中,记录序列R[1..n],将记录R[i]插入到有序子序列R[1..i-1]中,使记录的有序序列从R[1..i-1]变为R[1..i]。R[i]的插入过程就是完成排序中的一趟,随着有序序列的不断扩大,最终使全部有序,完成排列。

直接插入排序

直接插入排序

直接插入排序(straight insertion sort)的作法是:

每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。

第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。

值得注意的是,我们必需用一个存储空间来保存当前待比较的数值,因为当一趟比较完成时,我们要将待比较数值置入比它小的数值的后一位插入排序类似玩牌时整理手中纸牌的过程。插入排序的基本方法是:每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置,直到全部记录插入完毕为止。

void InsertSort(inr r[],int n)//0号单元用作存储单位和监视哨
{
 for (i=2;i<=n;i++)
 {
  r[0]=r[i];//暂存待插关键码,设置哨兵
  for(j=i-1;r[0]
   r[j+1]=r[j];//记录后移              
   r[j+1]=r[0];
 }
}

直接插入排序算法InsertSort

排序特点:

1.是一种稳定的排序方法。

2.适用于接近排好序的情况。

3.适用于n较小的情况。

4.直至最后一趟排序过程才能确定一个元素的最终位置。

 

 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有