文档章节

java插入排序

Demens
 Demens
发布于 2017/05/19 11:35
字数 380
阅读 3
收藏 0
点赞 0
评论 0

一、基本概念

      插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中。

二、java代码实现

public class InsertSort {
    public static void inserSort(int[] array){
        if (array==null||array.length<2){
            return;
        }

        for (int i=1;i<array.length;i++){  //默认第一个元素为有序队列,从第二个元素开始循环插入
           int position=array[i];          //设置第二个元素为要插入的数据
           int j=i-1;
            while (j>=0&&position<array[j]){
                array[j+1]=array[j];      //如果插入发数小于第j个元素,将第j个数向后移
                j--;
            }
            array[j+1]=position;         //插入
        }
    }

    public static void main(String ags[]){
        int[] array={2,6,4,7,3,-1};
        inserSort(array);
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
    }
}

三、性能分析

  • 稳定 
  • 空间复杂度O(1) 
  • 时间复杂度O(n2) 
  • 最差情况:反序,需要移动n*(n-1)/2个元素 
  • 最好情况:正序,不需要移动元素

© 著作权归作者所有

共有 人打赏支持
Demens
粉丝 0
博文 11
码字总数 14760
作品 0
CentOS 6.5 安装JDK(包含卸载原有默认JDK)

卸载原有1.7 JDK 查看是否安装了JDK 若有内容就进一步查看JDK信息 卸载 安装jdk ===================================== 安装wget 新建目录 进入目录 下载JDK 安装JDK 配置环境变量 往文件内...

阿白 ⋅ 05/23 ⋅ 0

Java就业变难了?你需要对自己有点信心

伴随着IT的火热,越来越多的人进入了IT领域,这在进一步推动着IT发展的同时也极大增加了就业压力。伴随着激烈的岗位竞争,越来越多的人开始感叹工作难找,越火的行业越是如此,Java自是首当其...

糖宝_d864 ⋅ 06/08 ⋅ 0

sharding-jdbc源码分析—准备工作

原文作者:阿飞Javaer 原文链接:https://www.jianshu.com/p/7831817c1da8 接下来对sharding-jdbc源码的分析基于tag为源码,根据sharding-jdbc Features深入学习sharding-jdbc的几个主要特性...

飞哥-Javaer ⋅ 05/03 ⋅ 0

MVN package install error javac: invalid target release: 1.8

现象: --------------------------------- [ERROR] Failure executing javac, but could not parse the error: javac: invalid target release: 1.8 Usage: javac <options> <source files>......

孟飞阳 ⋅ 05/04 ⋅ 0

Oracle Java Mission Control 帮助

缩写 含义 JDK Java 开发工具包 JDP Java Discovery Protocol JFR Java 飞行记录器 JMC Java Mission Control JMX Java Management Extensions JVM Java 虚拟机 MBean 托管 Bean (Java) RCP ......

光斑 ⋅ 04/27 ⋅ 0

培训云计算学校,虚拟机基本结构讲解

我们要对JVM虚拟机的结构有一个感性的认知。毕竟我们不是编程人员,认知程度达不到那么深入。一个运行时的Java虚拟机实例的天职是:负责运行一个java程序。当启动一个Java程序时,一个虚拟机...

长沙千锋 ⋅ 05/17 ⋅ 0

云计算高级培训,Tomcat运维JVM 虚拟机常识

云计算高级培训,Tomcat运维JVM 虚拟机常识,作为了解JVM 虚拟机的开始。我们很有必要弄明白以下问题。 所谓虚拟机,就是一台虚拟的计算机。他是一款软件,用来执行一系列虚拟计算机指令。大...

长沙千锋 ⋅ 05/17 ⋅ 0

14、Java并发性和多线程-Java ThreadLocal

以下内容转自http://ifeve.com/java-theadlocal/: Java中的ThreadLocal类可以让你创建的变量只被同一个线程进行读和写操作。因此,尽管有两个线程同时执行一段相同的代码,而且这段代码又有...

easonjim ⋅ 2017/06/16 ⋅ 0

Java开发学习之三版本简介 java编程

  Java编程语言,在更迭迅速的互联网领域多年屹立不倒,足以得见Java这门语言旺盛的生命力,因此,会有很多想要进入互联网领域的朋友,想要学Java来转行开发。但是,所谓“隔行如隔山”,j...

老男孩Linux培训 ⋅ 06/05 ⋅ 0

PHP调用java的class

PHP调用java的class 转:http://hi.baidu.com/lei0827/blog/item/28439a4e923234ced1c86a18.html PHP调用java的class有2种方法 1、种是用php自身带的模块调用java(不过经过网友的证明发现这...

thinkyoung ⋅ 2015/07/02 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Java Web如何操作Cookie的添加修改和删除

创建Cookie对象 Cookie cookie = new Cookie("id", "1"); 修改Cookie值 cookie.setValue("2"); 设置Cookie有效期和删除Cookie cookie.setMaxAge(24*60*60); // Cookie有效时间 co......

二营长意大利炮 ⋅ 今天 ⋅ 0

【每天一个JQuery特效】淡入淡出显示或隐藏窗口

我是JQuery新手爱好者,有时间就练练代码,防止手生,争取每天一个JQuery练习,在这个博客记录下学习的笔记。 本特效主要采用fadeIn()和fadeOut()方法显示淡入淡出的显示效果显示或隐藏元...

Rhymo-Wu ⋅ 今天 ⋅ 0

Spring JDBC使用方法

普通实现: 1、创建数据表customer。 可以使用任何数据库实现,在项目中要引入相应数据库驱动包并配置相应数据库连接。 2、创建Customer pojo。 Customer类的属性对应数据库的属性,除了为每...

霍淇滨 ⋅ 今天 ⋅ 0

Contos 7 安装Jenkins

Jenkins是一款能提高效率的软件,它能帮你把软件开发过程形成工作流,典型的工作流包括以下几个步骤 开发 提交 编译 测试 发布 有了Jenkins的帮助,在这5步中,除了第1步,后续的4步都是自动...

欧虞山 ⋅ 今天 ⋅ 0

revel

revel install go get github.com/revel/revelgo get github.com/revel/cmd create new app revel new git.oschina.net/zdglf/myapp run app revel run git.oschina.net/zdglf/myapp ot......

zdglf ⋅ 今天 ⋅ 0

49. Group Anagrams - LeetCode

Question 49. Group Anagrams Solution 思路:维护一个map,key是输入数组中的字符串(根据字符排好序) Java实现: public List<List<String>> groupAnagrams(String[] strs) { Map<Strin......

yysue ⋅ 今天 ⋅ 0

spring Email

使用spring发Email其实就是使用spring自己封装携带的一个javamail.JavaMailSenderImpl类而已。这个类可以当一个普通的java对象来使用,也可以通过把它配置变成spring Bean的方式然后注入使用...

BobwithB ⋅ 今天 ⋅ 0

spark 整理的一些知识

Spark 知识点 请描述spark RDD原理与特征? RDD全称是resilient distributed dataset(具有弹性的分布式数据集)。一个RDD仅仅是一个分布式的元素集合。在Spark中,所有工作都表示为创建新的...

tuoleisi77 ⋅ 今天 ⋅ 0

思考

时间一天天过感觉自己有在成长吗?最怕的是时光匆匆而过,自己没有收获!下面总结下最近自己的思考。 认识自己 认识另一个自己,人们常说要虚心听取别人意见和建议。然而人往往是很难做到的,...

hello_hp ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部