Java插入排序实现详解编程语言

插入排序的思想是：每次将一个待排序的记录，按其大小插入到前面已经排序的子序列的合适位置，直到全部插入。本文是插入排序的JAVA实现，包括直接插入排序，二分法插入排序和希尔排序。

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. 希尔排序：改进的直接插入算法，速度快，但不是稳定排序。