參考資料：
http://www.cnblogs.com/jingmoxukong/p/4303279.html
http://www.cnblogs.com/jingmoxukong/p/4303279.html
在任意算法能夠正常運行之前，必須猴誊，有一些前置條件潦刃；
1. 插入排序
算法導(dǎo)論中，插入排序的例子舉得不錯：
前置條件：
- 假設(shè)整個撲克牌懈叹，是一個大數(shù)組乖杠，我們需要對撲克牌進行排序；
- 先摸一張牌澄成，這個時候胧洒，假設(shè)手上的第一張牌，是排序好的墨状；
- 然后卫漫，從桌上摸牌，從手中的牌中肾砂，找到合適的位置汛兜，并插入進去；
- 重復(fù)第三步通今，直到?jīng)]桌上的牌都被摸完；
java代碼的實現(xiàn)：
/** * 插入排序 */
public static void sort3(int[] a) {
// 類似于手中的撲克牌肛根，假設(shè)是排序好的辫塌，每摸一張，我們得找個位置插入進去
// 1.從下標1開始派哲，遍歷整個數(shù)組（桌上的牌）臼氨，下標為0的為已排序好的 （手中的牌）
// 2.不斷獲取數(shù)組中的數(shù)（類似于摸牌）用變量 key 記錄其值，表示待插入的數(shù)據(jù)（摸到的牌）
// 3.從后往前芭届，遍歷已排序好的數(shù)組（遍歷手中的牌）储矩，找到要插入的位置，并插入
// 4.重復(fù)上面的步驟 下標++
int length = a.length; // 牌的長度
int i = 1; // 桌上牌的索引下標
for (; i < length; i++) { // 不斷摸牌
int key = a[i]; // 摸到的牌
int j = i - 1; // 手中的牌褂乍，遍歷的下標
// 從后往前遍歷手中的牌,將手中的牌與 摸到的牌持隧，對比
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j]; // 元素向后移動
j--;
}
a[j + 1] = key; // 插入 摸到的牌
}
}
2. 希爾排序
希爾排序，是對插入排序的補充逃片，通過分組并分組插入排序屡拨，來形成局部有序的數(shù)組，最后走的還是 原始的插入排序，不過此時的序列呀狼，差不多已排序的差不多了裂允。所以，比較哥艇，交換次數(shù)就少绝编。對比采用 插入排序 與 希爾排序，來說貌踏，用希爾的速度 隨著待排序數(shù)組長度的 增大十饥，而更快；
java代碼：
public class SheellSort {
public static void main(String[] args) {
int[] array = { 10, 5, 3, -1, 88, 0, 2, 100, 22, 89,-9,78,34 };
sheellSort(array);
}
public static void sheellSort(int[] list) {
// 相比插入排序哩俭，希爾排序引入了步長與分組
// 相鄰步長長度的數(shù)绷跑，形成分組，并分組進行插入排序
// 當(dāng)步長等于1時凡资，排序整個數(shù)組砸捏，結(jié)束分組循環(huán)
System.out.print("排序前\t");
printAll(list);
int length = list.length;
int gap = length / 2; // 初始化步長為數(shù)組長度的一半
while (gap >= 1) {
for (int i = gap; i < length; i++) { // 步長為gap的編為1組，進行插入排序（分組并進行插入排序）
int key = list[i]; // 摸牌
int j = i - gap; // 手中的牌隙赁，遍歷的下標
for (; j >= 0 && list[j] > key; j = j - gap) { // 從后往前遍歷垦藏，步長為gap，排序手中的牌
list[j + gap] = list[j];
}
list[j + gap] = key; // 插入摸到的牌
}
System.out.format("gap=%d\t", gap);
printAll(list);
gap = gap / 2; // gap繼續(xù)縮小伞访，也就是進行下一次分組
}
System.out.print("排序后\t");
printAll(list);
}
public static void printAll(int[] list) {
for (int value : list) {
System.out.print(value + "\t");
}
System.out.println();
}
}
