插入排序的效率：O(N*N), 比较N*N/4，复制N*N/4，插入排序在随机数的情况下，比冒泡快一倍，比选择稍快，在基本有序的数组中，插入排序几乎只需要O(N)，在逆序的情况下，并不比冒泡快。

代码：

1 package sorts; 2  3 public class InsertionSort { 4     /** 5      * @param a the array 6      * @param low the lower bound (inclusive) 7      * @param high the upper bound (exclusive) 8      * */ 9     public static 
     
      > void sort(T[] a, int low, int high) {10         --high;11         for (int i = low+1; i <= high; i++) { // index from  the second character in a12             T cur = a[i]; // the current character to  be inserted13             int j = i - 1; // start comparing with cell left of i14             while ((j>=low) && (a[j].compareTo(cur) > 0)) { // while a[j]  is  out of order with cur15                 a[j+1] = a[j];16                 j = j - 1;17             }18             a[j+1] = cur;19         }20     }21 }