算法渣-排序-插入

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

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

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

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

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

算法渣-排序-插入

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

算法

设置监视哨r[0]，将待插入记录的值赋值给r[0]；
设置开始查找的位置j；
在数组中进行搜索，搜索中将第j个记录后移，直至r[0].key≥r[j].key为止；
将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

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

查看所有标签

猜你喜欢:

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

码农书籍

Head First HTML5 Programming（中文版）

埃里克•弗里曼 (Eric Freeman)、伊丽莎白•罗布森 (Elisabeth Robson) / 中国电力出版社 / 2012-9 / 78.00元

《Head First HTML5 Programming(中文版)》内容简介：你可能想创建具有动态性、交互性、包含丰富数据而且互连的Web页面。先等一下，Web页面？为什么不用HTML5创建成熟的Web应用呢？另外，为什么不使用现代技术，像在移动设备上一样轻松地应用到桌面浏览器呢？当然，你肯定希望使用最新的HTML5技术来完成，比如地理定位、视频、2D绘制、Web存储、Web工作线程等，是不是？......一起来看看《Head First HTML5 Programming（中文版）》这本书的介绍吧!

码农工具

HTML 压缩/解压工具

在线压缩/解压 HTML 代码

HSV CMYK 转换工具

HSV CMYK互换工具