文档章节

插入排序

镜子哥哥
 镜子哥哥
发布于 2016/08/12 09:40
字数 330
阅读 7
收藏 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
广州

暂无文章

shell特殊符号、cut、sort、uniq、wc、tee、tr、split命令

10月15日任务 8.10 shell特殊符号cut命令 8.11 sort_wc_uniq命令 8.12 tee_tr_split命令 8.13 shell特殊符号下 cut 命令 cut作用:截取字符串 用法如下:cat /etc/passwd |head -2 |cut -d ...

hhpuppy
24分钟前
0
0
Springboot实现filter拦截token验证和跨域

背景 web验证授权合法的一般分为下面几种 1使用session作为验证合法用户访问的验证方式 使用自己实现的token 使用OCA标准 在使用API接口授权验证时,token是自定义的方式实现起来不需要引入其...

funnymin
59分钟前
2
0
linux使用ntfs-3g操作ntfs格式硬盘

Linux内核目前只支持对微软NTFS文件系统的读取。 NTFS-3G 是微软 NTFS 文件系统的一个开源实现,同时支持读和写。NTFS-3G 开发者使用 FUSE 文件系统来辅助开发,同时对可移植性有益。 安装 ...

linuxprobe16
今天
1
0
kubeadm部署kubernetes集群

一、环境要求 这里使用RHEL7.5 master、etcd:192.168.10.101,主机名:master node1:192.168.10.103,主机名:node1 node2:192.168.10.104,主机名:node2 所有机子能基于主机名通信,编辑...

人在艹木中
今天
14
0
Shell特殊符号总结以及cut,sort,wc,uniq,tee,tr,split命令

特殊符号总结一 * 任意个任意字符 ? 任意一个字符 # 注释字符 \ 脱义字符 | 管道符 # #号后的备注被忽略[root@centos01 ~]# ls a.txt # 备注 a.txt[root@centos01 ~]# a=1[root@centos01...

野雪球
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部