算法小记：插入排序

一、思想

插入排序：首先，从1个元素子数组元素开始，将第2个元素依次与子数组的元素比较大小，找个合适的位置（并将相应的子数组元素后移）并插入；再次，将第3个元素依次与子数组（2个元素）的元素比较大小，并插入到响应的位置；如此往复，直道将整个数组排序；

二、与选择排序比较

• 相同：当前索引左边的元素都是有序的，但是插入最终位置还不确定，为了给更小的元素腾出空间，可能会移动；

• 不同：插入排序所需的时间取决于输入中的元素的初始顺序（对于很大且数组元素已经有序（或接近有序）的数组进行排序将会比随机顺序的数组或逆序数组排序快得多；

  三、代码

  /** 
   * 插入排序 
   *  
   * @author pengcx 
   *  
   */ 
  public class Insertion  extends Sort{ 
   
      public static void main(String[] args) { 
          String[] a = { "d", "a", "w", "b", "q" }; 
          Insertion.sort(a);  
          show(a); 
      } 
   
      /**  
      * 排序数组a 
      *  
      * @param a 
      *            排序的数组a 
      */ 
     private static void sort(Comparable[] a) { 
          int N = a.length; 
          for (int i = 0; i < N; i++) { 
              for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) { 
                  exch(a, j, j - 1); 
              } 
          } 
    } 
  }