1. 希爾排序思想
希爾排序(Shell Sort)是插入排序的一種，是直接插入排序算法的一種更高效的改進版本。具體高效在何處呢？
前面俺講插入排序的時候，我們會發(fā)現(xiàn)一個很費勁的事兒，如果已排序的分組元素為{2,5,6,7,8,9}，未排序的分組 元素為{1}。
我們需要拿著1從后往前，依次和2,5,6,7,8,9進行交換位置，才能完成真正的插入，每次交換只能和相鄰的元素交換位置，這樣比實在是效率低下。但是，在插入排序時俺說了折半插入，這算是一種優(yōu)化，但是如果我要是將1插入到2,5,1,7,8,9當中，是不是就不行啦？
那我可不可以這樣做呢？
把1放到更前面的位置，比如一次交換就能把1插到6和7之間，這樣一次交換1就向前走了3個位置，可以減少交換的次數(shù)，然后再通過一次交換，直接結束排序。這樣的需求如何實現(xiàn)呢？接下來我們來看看希爾排序的原理。
2. 希爾排序詳解
排序原理：
選定一個增長量h，按照增長量h作為數(shù)據(jù)分組的依據(jù)，對數(shù)據(jù)進行分組；
對分好組的每一組數(shù)據(jù)完成插入排序；
減小增長量，最小減為1，重復第二步操作。
增長量ans：我們這里采用以下規(guī)則
【第一趟排序】
初始增量為ans = length/2 = 4，即將整個數(shù)組劃分為4個子組，分別為4,6，8,2，9,6，7,1
將每個子組獨立的看為一個要排序的數(shù)組，然后分別進行直接排序。
可以看到，每個子序列現(xiàn)在已經(jīng)有序了。但是將每個子序列回歸放到整個數(shù)組中，發(fā)現(xiàn)整個數(shù)組還是亂序的。我們接著進行第二趟排序。
【第二趟排序】
二次增量為ans = 4/2 = 2，即將整個數(shù)組劃分為4個子組，分別為4,6,6,9，2,1,8,7
然后在分別對兩個子組進行插入排序
【第三趟排序】
第三次增量為ans = 2/2 = 1，即將每個元素看成一組，子序列合并為一組，4,1,6,2,6,7,9,8。
其實，這就是相當于直接插入排序。但是，經(jīng)過第一趟、第二趟的處理之后，此時第三趟要排序的數(shù)組對比于原數(shù)組，我們發(fā)現(xiàn)它其實是被粗略調(diào)整過了，數(shù)組在一定程度上變得相對有序了。
此時，僅僅需要對以上數(shù)列簡單微調(diào)，無需大量移動操作即可完成整個數(shù)組的排序。
3. 代碼實現(xiàn)
public static void shellSort(Integer[] arr) {
//根據(jù)數(shù)組長度，確定增長量ans
int ans = 1;
while (ans < arr.length/2) {
ans = 2 * ans + 1;
}
while (ans >= 1) {
//找到待插入的元素
for (int i = ans; i < arr.length; i++) {
//待插入的元素插入到分組的有序序列中
for (int j = i; j >= ans; j-=ans) {
//待插入的元素時arr[j],比較arr[j-ans]
if(arr[j] < arr[j-ans]) {
int temp = arr[j];
arr[j] = arr[j-ans];
arr[j-ans] = temp;
}else {
//待插入元素在分組中已有序
break;
}
}
}
//減小ans的值
ans = ans / 2;
}
}
4. 復雜度分析
希爾排序，利用分組粗調(diào)的方式減少了直接插入排序的工作量，使得算法的平均時間復雜度低于0(n^2)。
【時間復雜度】O(nlogn)
【空間復雜度】O(1)
5. 希爾排序與插入排序比較
我們可以使用事后分析法對希爾排序和插入排序做性能比較。
測試從100000 ~ 1的逆向數(shù)據(jù)數(shù)組，我們可以根據(jù)執(zhí)行時間來完成測試。
【執(zhí)行時間】
希爾排序：29ms
直接插入排序：76826ms
折半插入排序：13075ms
可以看出，希爾排序的效率相比其他兩種效率很高。這就是得益于每趟對數(shù)組進行的粗略調(diào)整。
