插入排序的思想是：每次將一個待排序的記錄，按其大小插入到前面已經(jīng)排序的子序列的合適位置，直到全部插入。本文是插入排序的JAVA實現(xiàn)，包括直接插入排序，二分法插入排序和希爾排序。

package org.rev.algorithm;
 
/**
 * 插入排序：每次將一個待排序的記錄，按其大小插入到前面已經(jīng)排序的子序列的合適位置，直到全部插入。
 * 
 * 1. 直接插入排序：和已經(jīng)排序的部分逐一比較找到合適位置
 * 
 * 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); // 輸出排序后的數(shù)組
  }
 
  /**
   * 直接插入排序，時間復(fù)雜度復(fù)雜度O(n^2)
   * 
   * 1. 第1個元素是一個length為1的有序數(shù)列，第2-第n元素為待排序的數(shù)列。
   * 
   * 2. 從第2個元素開始，和前面的有序數(shù)列中的元素比較（從后向前），找到合適的位置，并插入。
   * 
   * 3. 直到第n個元素插入完畢。
   * 
   * @param data 待排序的數(shù)列
   */
  public void directInsertionSort(int[] data) {
 
    for (int i = 1; i < data.length; i++) {
 
      int tmp = data[i];
      int j;
      // data[0]--data[j]是有序數(shù)列
      for (j = i - 1; j >= 0; j--) {
        if (tmp < data[j]) { // 比tmp大都往后挪一下
          data[j + 1] = data[j];
        } else {
          break;
        }
      }
      // 把tmp插進前面空出的位置。
      data[j + 1] = tmp;
    }
 
  }
 
 
 
  /**
   * 
   * 二分法插入排序，時間復(fù)雜度復(fù)雜度O(n^2)
   * 
   * 思想和直接插入一樣，只是找合適的插入位置的方式采用二分法查找，可以減少比較的次數(shù)。
   * 
   * @param data 待排序的數(shù)列
   */
  public void binaryInsertionSort(int[] data) {
 
    for (int i = 0; i < data.length; i++) {
      int tmp = data[i];
      // data[0] -- data[i-1]是有序數(shù)列
      int left = 0;
      int right = i - 1;
 
      int mid = 0; // 中間值，初始為0
 
      // 通過二分法找到要插入的位置，即left
      while (left <= right) {
        mid = (left + right) / 2;
        if (tmp < data[mid]) { // 如果小于中數(shù)
          right = mid - 1;
        } else { // 如果大于等于中間的數(shù)
          left = mid + 1;
        }
      }
      // 大家都往后挪一下，一人挪一下
      for (int j = i - 1; j >= left; j--) {
        data[j + 1] = data[j];
      }
      // 插進去
      data[left] = tmp;
    }
  }
 
 
 
  /**
   * 希爾排序，實質(zhì)上是分組插入算法。
   * 
   * 對于數(shù)列a1……an
   * 
   * 1. 取小于n的整數(shù)d作為第一個增量，把序列分成d個組，形如 {a[1],a[d+1],a[2d+1]),…}， {a[2],a[d+2],a[2d+2]),…}
   * 
   * 2. 分別在各個組內(nèi)進行直接插入排序，完成第一次排序。
   * 
   * 3. 再取第二個增量d2（d2 < d），把序列分成d2 個組，分別在各個組中進行直接插入排序。
   * 
   * 4. 直到增量等于1。
   * 
   * @param data 待排序的數(shù)列
   */
  public void ShellSort(int[] data) {
    int d = data.length;
    while (d > 1) {
      d = d / 2; // 取一個小于length的整數(shù)
      for (int x = 0; x < d; x++) { // 分成d個組
        // 組內(nèi)直接插入排序
        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;
        }
      }
    }
  }
 
 
 
  /*
   * 打印輸出數(shù)組中的數(shù)據(jù)
   */
  private void print(int[] data) {
    for (int i = 0; i < data.length; i++) {
      System.out.print(data[i] + "\t");
    }
    System.out.println();
  }
 
}

  三種插入排序之間的比較：

   1. 直接插入排序： 穩(wěn)定排序，在數(shù)列相對有序的時候比二分插入塊。

   2. 二分插入排序：穩(wěn)定排序，當n較大時，對無序數(shù)列排序比直接插入要快。

   3. 希爾排序：改進的直接插入算法，速度快，但不是穩(wěn)定排序。

標簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。