前面一口氣寫了冒泡炭剪、選擇练链、插入三個排序算法，感覺今天和他們死磕上了奴拦。媒鼓。。
就不該十一點多還看了幾眼粱坤。隶糕。。然后又掉坑里了站玄，大半夜果然的效率低枚驻，看個希爾排序然后居然寫了1個小時。株旷。再登。哇，難受
WTF
抄起鍵盤一頓梭晾剖，就是干
嚴格來說锉矢，希爾排序是基于插入排序的思想的，稍后在代碼里可以看出齿尽，希爾排序又稱縮小增量排序沽损，是簡單插入排序的增強版本，于1959年由Donald Shell提出循头。
算法基本思想：
- 將有n個元素的數組分成n/2份绵估，第1個數據與第n/2+1個數據屬于同一份炎疆。。国裳。
- 使用類似插入排序的方法形入，將同一份的數據排序
- 然后，再變?yōu)閚/4份缝左，同樣的操作再次排序
- 不斷重復上述3個步驟之后亿遂，最后分成n份數據，再通過一次插入排序就完成了全部的排序渺杉。
示意圖
（網上搜的圖蛇数，自己不想畫了，大半夜要睡覺去了少办，偷個懶）
代碼實現：
import java.util.Arrays;
public class ShellSort {
public static void sort(int[] arr) {
int len = arr.length;
int gap;//步長
int istIndex;//插入位置索引
int tmp;
System.out.println("原始順序： "+ Arrays.toString(arr));
//按照步長來分組
for(gap = len / 2; gap >= 1; gap /= 2) {
//類似插入排序的方法
for (int i = gap; i < len; i++) {
tmp = arr[i];//取出暫存
istIndex = i;//插入的位置
while ((istIndex > (gap-1) && tmp < arr[istIndex - gap])) {
//插入位置往前移苞慢，尋找合適位置
arr[istIndex] = arr[istIndex - gap];
istIndex -= gap;
}
arr[istIndex] = tmp;
}
System.out.println("步長為"+gap+"的排序: "+ Arrays.toString(arr));
}
}
public static void main(String[] args) {
int[] arr = new int[10];
//初始化數組
for (int i = 0; i < 10; i++) {
arr[i] = (int) (Math.random() * (100 + 1));
}
ShellSort.sort(arr);
}
}
分析小結：
其實希爾排序就是分了組的插入排序，通過這樣做可以減少大部分的情況下英妓，數據的移動次數，從而減小時間復雜度绍赛，同時希爾排序也是當時沖破O(n^2）的第一批算法之一蔓纠。
在代碼中可以看到，當我們將第二層for循環(huán)里的gap視為1的時候吗蚌，其實接下來的代碼就和之前的插入排序一模一樣了Ｍ纫小！蚯妇！
其實對于該算法敷燎，還可以繼續(xù)優(yōu)化，就是改善步長的計算部分箩言，現在是每次變?yōu)樵瓉淼?/2硬贯，其實有個公式h=3*h+1來計算步長，有興趣的話可以自己研究一下陨收，對于步長的選擇是一種魔力饭豹，我就不多說了。务漩。拄衰。睡覺睡覺了，不能在修仙了zzz
