搜索

直接插入排序

gecimao 发表于 2019-07-15 02:04 | 查看: | 回复:

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  展开全部直接插入排序的作法是:每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。

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

  展开全部直接插入排序属于稳定的排序,时间复杂性为,空间复杂度为O(1)。

  直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。值得注意的是,我们必需用一个存储空间来保存当前待比较的数值,因为当一趟比较完成时,我们要将待比较数值置入比它小的数值的后一位

  插入排序类似玩牌时整理手中纸牌的过程。插入排序的基本方法是:每步将一个待排序的记录按其关字的大小插到前面已经排序的序列中的适当位置,直到全部记录插入完毕为止。常用的插入排序有:直接插入排序、折半插入排序、表插入排序和希尔排序。本节着重介绍直接插入排序。

  直接插入排序(straight insertion sort)是一种最简单的排序方法,它的基本思想是依次将每个记录插入到一个有序中去。就是说,第i(i=1)遍整理时,A1,A2,...,Ai-1已经是排好序的子序列;取出第i个元素Ai,在已排好序的子序列为Ai找到一个合适的位置,并将它插到该位置上。易知上述排序当i=1时实际上为空操作,故可直接从i=2开始。

  例8-1应用直接插入排序算法,对图8-1所示的一组键值进行排序。过程如图。

  为了便于控制循环结束,引入元素a0,行时可以节省时间,直接插入排序的算法如下:

  //将第j个记录赋值给第j+1个记录,直至关键字不大于待插入记录的关键字//

  算法中引进附加记录A[0]有两个作用:其一是进入查找循环之前,它保存了A[ i ]的值,使得不致于因记录的后移而丢失A[ i ]中的内容;其二是在While循环监视下变量j是否越界,一旦越界(即j1),A[0]自动控制While循环的结束,从而避免了在While循环中每一次都要检测j是否越界(即省略了循环条件j=1)。因此我们把称为监视哨,这种技巧,使得测试循环条件的时间大约减少一半,对于记录数较大的文件,节约的时间相当可观。希望读者能掌握这种技巧。

  由此可见,直接插入排序算法简洁,易理解,容易实现。当序列中的记录“基本有序”或n值较小时,它是最佳的排序方法。但是,通常待排记录的数量n很大,此时直接插入排序就不适用了。

本文链接:http://baumseelen.com/duipaixu/672.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部