算法渣-排序-插入

栏目: 编程工具 · 发布时间: 6年前

内容简介:插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序它的基本思想是:每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止联想打扑克牌时理顺手中牌的时候,你从左往右依次检查你的牌,并将其和前面的牌进行比较,然后将其插入正确的位置

插入 排序 的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序

它的基本思想是:每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止

联想打扑克牌时理顺手中牌的时候,你从左往右依次检查你的牌,并将其和前面的牌进行比较,然后将其插入正确的位置

算法渣-排序-插入

理解起来,比 《快速排序》 容易多了

算法

  1. 设置监视哨r[0],将待插入记录的值赋值给r[0];
  2. 设置开始查找的位置j;
  3. 在数组中进行搜索,搜索中将第j个记录后移,直至r[0].key≥r[j].key为止;
  4. 将r[0]插入r[j+1]的位置上。

演示

算法渣-排序-插入

也可以通过动画更清晰了解整个排序过程

动画: http://www.zhuxingsheng.com/tools/sort/sort.html

实现

插入排序包括:直接插入排序,二分插入排序(又称折半插入排序),链表插入排序,希尔排序(又称缩小增量排序)

static void insertSort1(int []sorts) {
    for(int i = 1;i<sorts.length;i++) {
        int tmp = sorts[i];//哨兵
        int j= i-1;
        while(j >=0 && tmp < sorts[j]) {
            sorts[j+1] = sorts[j];//比tmp大的全部往右移动
            j--;
        }
        //别的移完位置,把哨兵放到正确的位置
        sorts[++j] = tmp;
    }
}

复杂度

当问题规模为n时

最好情况(原本就是有序的)

比较次数:Cmin=n-1

移动次数:Mmin=0

最差情况(逆序)

比较次数:Cmax=2+3+4+……+n=(n+2)n/2

移动次数:Mmax=1+2+3+……+n-1=n*n/2

Best Average Worst Memory Stable
n n^2 n^2 1 Yes

以上所述就是小编给大家介绍的《算法渣-排序-插入》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Java5.0Tiger程序高手秘笈

Java5.0Tiger程序高手秘笈

BrettMclaughlin / 东南大学出版社 / 2005-10 / 28.00元

代号为 “Tiger”的下一个 Java 版本,不只是个小改动版。在语言核心中有超过 100 项以上的变动,同时有大量的对 library 与 API 所做的加强,让开发者取得许多新的功能、工具与技术。但在如此多的变化下,应该从何处开始着手?也许可以从既长又无趣的语言规范说明书开始看起;或等待最少 500 页的概念与理论巨著出版;甚至还可以直接把玩新的 JDK 看看能够有什么发现;或者借由《Jav......一起来看看 《Java5.0Tiger程序高手秘笈》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

html转js在线工具
html转js在线工具

html转js在线工具