文档章节

插入排序

镜子哥哥
 镜子哥哥
发布于 2016/08/12 09:40
字数 330
阅读 8
收藏 0

原理

插入排序外循环标记未排序部分最左端的数据,内循环从该位置左侧开始向左移动,直到找到合适该数据插入的位置。

如下图所示,每次选择一个元素K插入到之前已排好序的部分A[1…i]中,插入过程中K依次由后向前与A[1…i]中的元素进行比较。若发现发现A[x]>=K,则将K插入到A[x]的后面,插入前需要移动元素。 插入排序原理

不变性

(算法运行时保持不变的条件):它总是局部有序的。

效率

比较 平均 N(N-1)/4 次; 复制 N(N-1)/4 次 ;

总时间级 O(N2)

复制与交换速度不同,所以对于随机数据,比冒泡快一倍,比选择略快。

实现代码

//这是错的,有不必要的复制
public void insert(int[] array) {
   int len = array.length;
   for (int a = 1; a < len; a++) {
       int temp = array[a];
       for (int b = a - 1; b >= 0; b--) {
           if (array[b + 1] < array[b]) {
               array[b + 1] = array[b];
               array[b] = temp;
               }
           }
       }
   }

下面才是真正的

public void insert(int[] array) {
        int len = array.length;
        for (int a = 1; a < len; a++) {
            int temp = array[a];
            int b = a - 1;
            for (; b >= 0 && temp < array[b]; b--) {
                array[b + 1] = array[b];
            }
            array[b + 1] = temp;
        }
    }

© 著作权归作者所有

共有 人打赏支持
镜子哥哥
粉丝 1
博文 19
码字总数 14425
作品 0
广州
私信 提问

暂无文章

深入理解Java PriorityQueue

ava中PriorityQueue通过二叉小顶堆实现,可以用一棵完全二叉树表示。本文从Queue接口函数出发,结合生动的图解,深入浅出地分析PriorityQueue每个操作的具体过程和时间复杂度,将让读者建立对...

java菜分享
15分钟前
2
0
玩手机与做实验

看过这样一个故事:说的是在二十世纪二十年代初的一个深夜,担任英国剑桥大学卡文迪许实验室主任的卢瑟福来实验室检查,发现一位学生还在做实验。卢瑟福就问他:“你上午做什么了?”学生回答...

Bob2100
25分钟前
1
0
Kafka流式处理

Kafka Streams 初识流式处理 什么是数据流 数据流(也叫事件流)是无边界数据集的抽象表示。无边界意味着无限和持续增长。无边界数据集之所以是无限的,是因为随着时间的推移,新记录会不断加...

东都大狼狗
34分钟前
3
0
Mysql主从复制(拓展博客文章扩充知识面)

#不停库不锁表在线主从配置 使用 Xtrabackup 在线对MySQL做主从复制 1.数据量大的话还是建议使用工具例如xtrabackup,mysqldump比较适合操作10G以下的数据备份复制。 2.做业务之前考虑清楚具...

robertt15
39分钟前
1
0
docker快速搭建几个常用的第三方服务

本次和大家分享的内容是使用docker快速搭建工作中常用的第三方的服务,对于有一些互联网背景的公司来说,以下几个服务都是很需要的:redis,rabbit,elasticsearch; 如果想学习Java工程化、...

编程SHA
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部