文档章节

插入排序(JAVA)

郭寻抚
 郭寻抚
发布于 2015/02/05 15:50
字数 942
阅读 284
收藏 12
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. 希尔排序:改进的直接插入算法,速度快,但不是稳定排序。



© 著作权归作者所有

共有 人打赏支持
郭寻抚
粉丝 57
博文 26
码字总数 20965
作品 0
东城
程序员
私信 提问
java 通配符的应用— java 排序算法

这几天无聊,又重新学起java的排序算法,为DualPivotQuickSort做准备。为了更好地适应各种情况,我们选择使用通用类型T和通配符的上下界来实现,同时这次谈的是对数组对象的排序。如果你对j...

天地一MADAO_
2014/03/02
0
0
程序员必知的8大排序(java实现)

8种排序之间的关系:  1、 直接插入排序   (1)基本思想:   在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好...

小帅帅丶
2015/01/09
0
7
java或js,ajax或jquery分页代码吗最好就是含有一些高级的算法来分页,

谁有更好的java或js,ajax或jquery分页代码吗最好就是含有一些高级的算法来分页,S2SH框架使用 1 分钟前Thomas8sky | 分类:JAVA相关 | 浏览1次 最近想学会优化代码,学习一些高级的算法,来提...

天池番薯
2014/02/23
323
1
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

IceRainYWC
2014/03/17
0
0
JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。 快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。 冒泡法是运用遍历数组进...

闫三
2012/05/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Kafka+Flink 实现准实时异常检测系统

1.背景介绍 异常检测可以定义为“基于行动者(人或机器)的行为是否正常作出决策”,这项技术可以应用于非常多的行业中,比如金融场景中做交易检测、贷款检测;工业场景中做生产线预警;安防...

架构师springboot
13分钟前
1
0
DecimalFormat 类基本使用

/* * DecimalFormat 类主要靠 # 和 0 两种占位符号来指定数字长度 * 0 表示如果位数不足则以 0 填充 * # 表示只要有可能就把数字拉上这个位置 * */ public static void main(String[] args){...

嘴角轻扬30
30分钟前
3
0
This APT has Super Cow Powers.

在Debian/Ubuntu上,apt包管理器内嵌着一个彩蛋. 如果你在命令行界面输入 apt help 在最后一行能找到This APT has Super Cow Powers. 说明该apt具有超级牛力 牛力是个什么梗? 则说明你的系统...

taadis
47分钟前
2
0
起薪2万的爬虫工程师,Python需要学到什么程度才可以就业?

爬虫工程师的的薪资为20K起,当然,因为大数据,薪资也将一路上扬。那么,Python需要学到什么程度呢?今天我们来看看3位前辈的回答。 1、前段时间快要毕业,而我又不想找自己的老本行Java开发...

糖宝lsh
56分钟前
6
0
携手开发者共建云生态 首届腾讯云+社区开发者大会在京举办

本文由云+社区发表 北京时间12月15日,由腾讯云主办,极客邦科技、微信、腾讯TEG协办的首届腾讯云+社区开发者大会在北京朝阳悠唐皇冠假日酒店举办。在会上,腾讯云发布了重磅产品开发者平台以...

腾讯云加社区
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部