一、排序思想

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

1. 案例：

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

17*   3    25   14   20   9

那么開(kāi)始的時(shí)候，17就是有序表，剩余元素是一個(gè)無(wú)序表。

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

3*   17*    25   14   20   9

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

3*   17*    25*   14   20   9

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

3*   14*    17*   25*   20   9

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

3*   14*    17*   20*   25*   9

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

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

二、代碼實(shí)現(xiàn)

代碼中有詳細(xì)的注釋：

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

三、存在的問(wèn)題

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

16, 23, 12, 8, 1

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