注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ocean's blog

平常心——可以寂寞,但不允许空虚

 
 
 

日志

 
 

排序算法之插入排序  

2009-05-30 15:18:10|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

版权所有,转载请注明:本文出自学与思编程网

插入排序算法应该是使用最为广泛的一种排序算法了,从我们会玩扑克起我们就应该会这种算法了,现在的人有几个不会玩扑克呢?你说这种算法使用广泛不。

插入排序的基本思想是:取出未排序序列中的第一个元素,把它插入到已排序序列的合适位置。想象一下我们玩扑克,每从下面摸上来一张牌,我们就会把插入手中已有扑克的合适位置中,到最后摸完牌后,我们手上的扑克也已经按顺序排列好了。我们还是以一个简单的整数升序排序为例看看其排序过程:

假定有一组待排序整数:3,5,2,1,7    现在我们要把这5个数按升序排列。

我们把这5个数分成两部分,第一部分只有一个数3,因此它是排好序的,第二部分有 5,2,1,7  四个数,它们处于未排好序状态。下面我们就用插入排序算法把第二部分中的数插入到第一部分,直至排序完成。

第一步,取出第二部分第一个元素 5 插入第一部分,很明显它应该插入3的后面。这样结果为:3,5,2,1,7 。这时,已排好序的第一部分就有两个元素了,未排序的第二部分还有3个数。

第二步,取出第二部分第一个元素 2 插入第一部分,结果为:2,3,5,1,7 。这时第一部分有三个数,第二部分只剩下2个数了。

第三步,取出第二部分第一个元素1插入第一部分,结果为:1,2,3,5,7。排序完成。

下面是插入排序算法的c语言代码

void insertion_sort(int a[], int n)

{

int i, j;

int tmp;

for (i = 1; i < n; i++) {

tmp = a[i];

j = i - 1;

while(j >= 0 && a[j] > tmp) {

a[j + 1] = a[j];

j = j - 1;

}

a[j + 1] = tmp;

}

}

版权所有,转载请注明:本文出自学与思编程网

  评论这张
 
阅读(75)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018