直接插入排序

直接插入排序的思路很容易理解，它是這樣的：
1.把待排序的數(shù)組分成已排序和未排序兩部分，初始的時候把第一個元素認(rèn)為是已排好序的。
2.從第二個元素開始，在已排好序的子數(shù)組中尋找到該元素合適的位置并插入該位置。
3.重復(fù)上述過程直到最后一個元素被插入有序子數(shù)組中。
4.排序完成。

示例：
思路很簡單，但代碼并非像冒泡排序那么好寫。首先，如何判斷合適的位置？大于等于左邊、小于等于右邊？不行，很多邊界條件需要考慮，而且判斷次數(shù)太多。其次，數(shù)組中插入元素，必然需要移動大量元素，如何控制它們的移動？
實際上，這并不是算法本身的問題，而多少和編程語言有點關(guān)系了。有時候算法本身已經(jīng)很成熟了，到了具體的編程語言還是要稍作改動。這里講的是Java算法，那就拿Java說事兒。
為了解決上述問題，我們對第二步稍作細(xì)化，我們不從子數(shù)組的起始位置開始比較，而從子數(shù)組尾部開始逆序比較，只要比需要插入的數(shù)大，就向后移動。直到不大于該數(shù)的數(shù)，那么，這個空出來的位置就安放需要插入的數(shù)字。因此，我們可以寫出以下代碼：
InsertArray.java

public class InsertArray {
  // 數(shù)組
  private long[] arr;

  // 數(shù)組中有效數(shù)據(jù)的大小
  private int elems;

  // 默認(rèn)構(gòu)造函數(shù)
  public InsertArray() {
    arr = new long[50];
  }

  public InsertArray(int max) {
    arr = new long[max];
  }

  // 插入數(shù)據(jù)
  public void insert(long value) {
    arr[elems] = value;
    elems++;
  }

  // 顯示數(shù)據(jù)
  public void display() {
    for (int i = 0; i < elems; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

  // 插入排序
  public void insertSort() {
    long select = 0L;
    for(int i = 1; i < elems; i++) {
      select = arr[i];
      int j = 0;
      for(j = i;j > 0 && arr[j - 1] >= select; j--) {
        arr[j] = arr[j - 1];
      }
      arr[j] = select;
    }
  }
}

測試類：
TestInsertArray.java

public class TestInsertArray {
  public static void main(String[] args) {
    InsertArray iArr = new InsertArray();
    iArr.insert(85);
    iArr.insert(7856);
    iArr.insert(12);
    iArr.insert(8);
    iArr.insert(5);
    iArr.insert(56);

    iArr.display();
    iArr.insertSort();
    iArr.display();
  }

}

打印結(jié)果：

算法性能/復(fù)雜度
現(xiàn)在討論下直接插入算法的時間復(fù)雜度。無論輸入如何，算法總會進(jìn)行n-1輪排序。但是，由于每個元素的插入點是不確定的，受輸入數(shù)據(jù)影響很大，其復(fù)雜度并不是一定的。我們可以分最佳、最壞、平均三種情況討論。
1.最佳情況：由算法特點可知，當(dāng)待排數(shù)組本身即為正序（數(shù)組有序且順序與需要的順序相同，于我們的討論前提，即為升序）時為最佳，理由是這種情況下，每個元素只需要比較一次且無需移動。算法的時間復(fù)雜度為O(n);
2.最壞情況：很顯然，當(dāng)待排數(shù)組為逆序時為最壞情況，這種情況下我們的每輪比較次數(shù)為i-1, 賦值次數(shù)為i。總的次數(shù)為級數(shù)2n-1的前n項和，即n^2.算法的時間復(fù)雜度為O(n^2);
3.平均情況：由上述分析可以得到平均情況下算法的運(yùn)算次數(shù)大約為（n^2）/2（注：這里計算以賦值和比較計，若按移動和比較，則大約為n^2/4），顯然，時間復(fù)雜度還是O(n^2)。
至于算法的空間復(fù)雜度，所有移動均在數(shù)據(jù)內(nèi)部進(jìn)行，唯一的開銷是我們引入了一個臨時變量（有的數(shù)據(jù)結(jié)構(gòu)書上稱為“哨兵”），因此，其空間復(fù)雜度（額外空間）為O(1)。

算法穩(wěn)定性
由于只需要找到不大于當(dāng)前數(shù)的位置而并不需要交換，因此，直接插入排序是穩(wěn)定的排序方法。

算法變種
如果待排列的數(shù)據(jù)比較多，那么每次從后往前找就造成了很大的開銷，為了提高查找速度，可以采用二分查找（Binary Search）進(jìn)行性能優(yōu)化。由于二分查找的效率很高，保證了O(㏒n)復(fù)雜度，在數(shù)據(jù)比較多或輸入數(shù)據(jù)趨向最壞情況時可以大幅提高查找效率。在有些書上將這種方法稱為折半插入排序。它的代碼實現(xiàn)比較復(fù)雜，以后有時間可以貼出來。
此外，還有2-路插入排序和表插入排序。2-路插入排序是在折半插入排序的基礎(chǔ)上進(jìn)一步改進(jìn)，其移動次數(shù)大為降低，大約為n^2/8。但是，它并不能避免移動次數(shù)，也不能降低復(fù)雜度級別。表插入排序則完全改變存儲結(jié)構(gòu)，不移動記錄，但需要維護(hù)一個鏈表，以鏈表的指針修改代替移動記錄。因此，其復(fù)雜度仍然是O(n^2)。
有關(guān)2-路插入排序和表插入排序，可以參考嚴(yán)蔚敏、吳偉民編著的《數(shù)據(jù)結(jié)構(gòu)》一書。

算法適用場景
插入排序由于O(n^2)的復(fù)雜度，在數(shù)組較大的時候不適用。但是，在數(shù)據(jù)比較少的時候，是一個不錯的選擇，一般做為快速排序的擴(kuò)充。例如，在STL的sort算法和stdlib的qsort算法中，都將插入排序作為快速排序的補(bǔ)充，用于少量元素的排序。又如，在JDK 7 java.util.Arrays所用的sort方法的實現(xiàn)中，當(dāng)待排數(shù)組長度小于47時，會使用插入排序。

最新評論