一、排序思想

把n個待排的元素看成一個有序表和一個無序表，開始時，有序表只包含1個元素，無序表中有n - 1個元素。排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼比較，將它插入適當?shù)奈恢?，使之成為新的有序表?/p>

1. 案例：

假如現(xiàn)有待排序列如下(帶 * 號的是有序表元素)：

17*   3    25   14   20   9

那么開始的時候，17就是有序表，剩余元素是一個無序表。

• 第一次：讓3和有序表最后一個元素17比較，發(fā)現(xiàn)3比17小，那么就讓17往后挪一位，然后讓3再和前面的比較，發(fā)現(xiàn)前面沒有元素了，所以第一次排序后的結果是：

3*   17*    25   14   20   9

• 第二次：讓25和17比較，發(fā)現(xiàn)25比17大，那么就不用變換位置，第二次排序后的結果是：

3*   17*    25*   14   20   9

• 第三次：讓14和有序表元素比較，結果是：

3*   14*    17*   25*   20   9

• 第四次：讓20和有序表元素比較，結果是：

3*   14*    17*   20*   25*   9

• 第五次：讓9和有序表元素比較，結果是：

3*   9*   14*    17*   20*   25*

二、代碼實現(xiàn)

代碼中有詳細的注釋：

public static void sort(int[] arr) {
 if (arr == null || arr.length == 1) {
  return;
 }
 for(int i=1; i<arr.length; i++) { // 默認第一個是有序表，從第二個元素開始進行插入排序
  int insertVal = arr[i]; // 待排元素
  int insertIndex = i - 1; // 從有序表最后一個元素開始比較
  while (insertIndex >= 0 && insertVal < arr[insertIndex]) { // 如果還沒有將有序表比較完 && 待排元素還沒找到位置
   arr[insertIndex + 1] = arr[insertIndex]; // 比待排元素大的元素后移一位
   insertIndex --; // 繼續(xù)往前比較
  }
  // 找到位置后，其他元素都后移了，自己占坑
  if (insertIndex + 1 != i) {
   arr[insertIndex + 1] = insertVal;
  }
 }
}

三、存在的問題

假如現(xiàn)在有如下序列：

16, 23, 12, 8, 1

要求按照從小到大的順序排列，你會發(fā)現(xiàn)，最小的1在最后面，第二小的8在倒數(shù)第二個位置，那么在排序的時候，就會發(fā)生很多次交換，即while循環(huán)里面的代碼會執(zhí)行很多次，1在排序的時候就會執(zhí)行四次，這樣性能就下降了。有沒有優(yōu)化的空間呢？有，那就是希爾排序……敬請期待