文档章节

插入排序(JAVA)

郭寻抚
 郭寻抚
发布于 2015/02/05 15:50
字数 942
阅读 282
收藏 12
点赞 0
评论 0
package org.rev.algorithm;

/**
 * 插入排序:每次将一个待排序的记录,按其大小插入到前面已经排序的子序列的合适位置,直到全部插入。
 * 
 * 1. 直接插入排序:和已经排序的部分逐一比较找到合适位置
 * 
 * 2. 二分插入排序:使用二分法找到合适的位置
 * 
 * 3. 希尔排序(Shell Sort):分组的直接插入排序
 * 
 */
public class InsertionSort {

  public static void main(String[] args) {
    int[] data = {11, 39, 38, 55, 86, 5, 37, 12, 4, 11, 18};
    InsertionSort is = new InsertionSort();
    is.directInsertionSort(data); // 直接插入排序
    // is.binaryInsertionSort(data); // 二分法插入排序
    // is.ShellSort(data); // 希尔排序
    is.print(data); // 输出排序后的数组
  }

  /**
   * 直接插入排序,时间复杂度复杂度O(n^2)
   * 
   * 1. 第1个元素是一个length为1的有序数列,第2-第n元素为待排序的数列。
   * 
   * 2. 从第2个元素开始,和前面的有序数列中的元素比较(从后向前),找到合适的位置,并插入。
   * 
   * 3. 直到第n个元素插入完毕。
   * 
   * @param data 待排序的数列
   */
  public void directInsertionSort(int[] data) {

    for (int i = 1; i < data.length; i++) {

      int tmp = data[i];
      int j;
      // data[0]--data[j]是有序数列
      for (j = i - 1; j >= 0; j--) {
        if (tmp < data[j]) { // 比tmp大都往后挪一下
          data[j + 1] = data[j];
        } else {
          break;
        }
      }
      // 把tmp插进前面空出的位置。
      data[j + 1] = tmp;
    }

  }



  /**
   * 
   * 二分法插入排序,时间复杂度复杂度O(n^2)
   * 
   * 思想和直接插入一样,只是找合适的插入位置的方式采用二分法查找,可以减少比较的次数。
   * 
   * @param data 待排序的数列
   */
  public void binaryInsertionSort(int[] data) {

    for (int i = 0; i < data.length; i++) {
      int tmp = data[i];
      // data[0] -- data[i-1]是有序数列
      int left = 0;
      int right = i - 1;

      int mid = 0; // 中间值,初始为0

      // 通过二分法找到要插入的位置,即left
      while (left <= right) {
        mid = (left + right) / 2;
        if (tmp < data[mid]) { // 如果小于中数
          right = mid - 1;
        } else { // 如果大于等于中间的数
          left = mid + 1;
        }
      }
      // 大家都往后挪一下,一人挪一下
      for (int j = i - 1; j >= left; j--) {
        data[j + 1] = data[j];
      }
      // 插进去
      data[left] = tmp;
    }
  }



  /**
   * 希尔排序,实质上是分组插入算法。
   * 
   * 对于数列a1……an
   * 
   * 1. 取小于n的整数d作为第一个增量,把序列分成d个组,形如 {a[1],a[d+1],a[2d+1]),…}, {a[2],a[d+2],a[2d+2]),…}
   * 
   * 2. 分别在各个组内进行直接插入排序,完成第一次排序。
   * 
   * 3. 再取第二个增量d2(d2 < d),把序列分成d2 个组,分别在各个组中进行直接插入排序。
   * 
   * 4. 直到增量等于1。
   * 
   * @param data 待排序的数列
   */
  public void ShellSort(int[] data) {
    int d = data.length;
    while (d > 1) {
      d = d / 2; // 取一个小于length的整数
      for (int x = 0; x < d; x++) { // 分成d个组
        // 组内直接插入排序
        for (int i = x + d; i < data.length; i = i + d) {
          int tmp = data[i];
          int j;
          for (j = i - d; j >= 0 && data[j] > tmp; j = j - d) {
            data[j + d] = data[j];
          }
          data[j + d] = tmp;
        }
      }
    }
  }



  /*
   * 打印输出数组中的数据
   */
  private void print(int[] data) {
    for (int i = 0; i < data.length; i++) {
      System.out.print(data[i] + "\t");
    }
    System.out.println();
  }

}

  三种插入排序之间的比较:

   1. 直接插入排序: 稳定排序,在数列相对有序的时候比二分插入块。

   2. 二分插入排序:稳定排序,当n较大时,对无序数列排序比直接插入要快。

   3. 希尔排序:改进的直接插入算法,速度快,但不是稳定排序。



© 著作权归作者所有

共有 人打赏支持
郭寻抚
粉丝 56
博文 26
码字总数 20965
作品 0
东城
程序员
【目录导航】JAVA零基础进阶之路

【JAVA零基础入门系列】(已完结)导航目录 Day1 开发环境搭建 Day2 Java集成开发环境IDEA Day3 Java基本数据类型 Day4 变量与常量 Day5 Java中的运算符 Day6 Java字符串 Day7 Java输入与输出...

MFrank ⋅ 06/21 ⋅ 0

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

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

飞哥-Javaer ⋅ 05/03 ⋅ 0

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

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

长沙千锋 ⋅ 05/17 ⋅ 0

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

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

easonjim ⋅ 2017/06/16 ⋅ 0

CentOS 6.5 安装JDK(包含卸载原有默认JDK)

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

阿白 ⋅ 05/23 ⋅ 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

Java学习---Java简单认识

前言 小编在学习Java方面的基础知识,发现里面有很多是结合之前的语言的特点发展过来的,不同的地方是,Java有它自己的发展和特点。下面小编先简单地做一下总结,结合看过的1-2章的J2SE视频,...

m18633778874 ⋅ 04/01 ⋅ 0

sharding-jdbc源码解析全集

sharding-jdbc源码解析之词法解析 sharding源码解析之api分析 sharding-jdbc源码解析之spring集成 sharding-jdbc源码解析之spring集成分片构造实现 sharding-jdbc源码解析之jdbc规范重写 sh...

天河2018 ⋅ 05/03 ⋅ 0

深入理解JVM学习笔记(一、总览)

1、JVM历史 2、JVM内存结构 3、JVM垃圾回收机制 4、JVM性能监控工具 5、JVM性能调优案例时间 6、JVM类文件结构 7、JVM类加载机制 8、JVM字节码执行引擎 9、JVM虚拟机编译及其运行时优化 10、...

jintaohahahaha ⋅ 05/28 ⋅ 0

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

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

糖宝_d864 ⋅ 06/08 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

tcp/ip详解-链路层

简介 设计链路层的目的: 为IP模块发送和接收IP数据报 为ARP模块发送ARP请求和接收ARP应答 为RARP模块发送RARP请求和接收RARP应答 TCP/IP支持多种链路层协议,如以太网、令牌环往、FDDI、RS-...

loda0128 ⋅ 今天 ⋅ 0

spring.net aop代码例子

https://www.cnblogs.com/haogj/archive/2011/10/12/2207916.html

whoisliang ⋅ 今天 ⋅ 0

发送短信如何限制1小时内最多发送11条短信

发送短信如何限制1小时内最多发送11条短信 场景: 发送短信属于付费业务,有时为了防止短信攻击,需要限制发送短信的频率,例如在1个小时之内最多发送11条短信. 如何实现呢? 思路有两个 截至到当...

黄威 ⋅ 昨天 ⋅ 0

mysql5.7系列修改root默认密码

操作系统为centos7 64 1、修改 /etc/my.cnf,在 [mysqld] 小节下添加一行:skip-grant-tables=1 这一行配置让 mysqld 启动时不对密码进行验证 2、重启 mysqld 服务:systemctl restart mysql...

sskill ⋅ 昨天 ⋅ 0

Intellij IDEA神器常用技巧六-Debug详解

在调试代码的时候,你的项目得debug模式启动,也就是点那个绿色的甲虫启动服务器,然后,就可以在代码里面断点调试啦。下面不要在意,这个快捷键具体是啥,因为,这个keymap是可以自己配置的...

Mkeeper ⋅ 昨天 ⋅ 0

zip压缩工具、tar打包、打包并压缩

zip 支持压缩目录 1.在/tmp/目录下创建目录(study_zip)及文件 root@yolks1 study_zip]# !treetree 11└── 2 └── 3 └── test_zip.txt2 directories, 1 file 2.yum...

蛋黄Yolks ⋅ 昨天 ⋅ 0

聊聊HystrixThreadPool

序 本文主要研究一下HystrixThreadPool HystrixThreadPool hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java /** * ThreadPool used to executed {@link Hys......

go4it ⋅ 昨天 ⋅ 0

容器之上传镜像到Docker hub

Docker hub在国内可以访问,首先要创建一个账号,这个后面会用到,我是用126邮箱注册的。 1. docker login List-1 Username不能使用你注册的邮箱,要用使用注册时用的username;要输入密码 ...

汉斯-冯-拉特 ⋅ 昨天 ⋅ 0

SpringBoot简单使用ehcache

1,SpringBoot版本 2.0.3.RELEASE ①,pom.xml <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.0.3.RELE......

暗中观察 ⋅ 昨天 ⋅ 0

Spring源码解析(八)——实例创建(下)

前言 来到实例创建的最后一节,前面已经将一个实例通过不同方式(工厂方法、构造器注入、默认构造器)给创建出来了,下面我们要对创建出来的实例进行一些“加工”处理。 源码解读 回顾下之前...

MarvelCode ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部