文档章节

插入排序

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

暂无文章

kernel version does not match DSO version

错误信息: kernel version 384.11 does not match DSO version 384.130.0 原因是: cuda driver版本太低,不匹配DSO 简单有效的修复方法,升级nvidia driver, 步骤如下: 1. google seach ...

刘小米
今天
0
0
maven坐标和依赖

一、maven坐标详解 <groupId>com.fgt.club</groupId><artifactId>club-common-service-facade</artifactId><version>3.0.0</version><packaging>jar</packaging> maven的坐标元素说......

老韭菜
今天
1
0
springmvc-servlet.xml配置表功能解释

问:<?xml version="1.0" encoding="UTF-8" ?> 答: xml version="1.0"表示是此xml文件的版本是1.0 encoding="UTF-8"表示此文件的编码方式是UTF-8 问:<!DOCTYPE beans PUBLIC "-//SPRING//......

隐士族隐逸
今天
1
0
基于TP5的微信的公众号获取登录用户信息

之前讲过微信的公众号自动登录的菜单配置,这次记录一下在TP5项目中获取自动登录的用户信息并存到数据库的操作 基本的流程为:微信设置自动登录的菜单—>访问的URL指定的函数里获取用户信息—...

月夜中徘徊
今天
0
0
youTrack

package jetbrains.teamsys.license.runtime; 计算lis package jetbrains.ring.license.reader; 验证lis 安装后先不要生成lis,要把相关文件进行替换 ring-license-checker-1.0.41.jar char......

max佩恩
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部