1. 希爾排序思想
希爾排序(Shell Sort)是插入排序的一種，是直接插入排序算法的一種更高效的改進(jìn)版本麻昼。具體高效在何處呢？
前面俺講插入排序的時(shí)候，我們會(huì)發(fā)現(xiàn)一個(gè)很費(fèi)勁的事兒抽活，如果已排序的分組元素為{2,5,6,7,8,9}，未排序的分組 元素為{1}政己。
我們需要拿著1從后往前酌壕，依次和2,5,6,7,8,9進(jìn)行交換位置掏愁，才能完成真正的插入，每次交換只能和相鄰的元素交換位置卵牍，這樣比實(shí)在是效率低下果港。但是，在插入排序時(shí)俺說了折半插入糊昙，這算是一種優(yōu)化辛掠，但是如果我要是將1插入到2,5,1,7,8,9當(dāng)中，是不是就不行啦释牺？
那我可不可以這樣做呢萝衩？
把1放到更前面的位置，比如一次交換就能把1插到6和7之間没咙，這樣一次交換1就向前走了3個(gè)位置猩谊，可以減少交換的次數(shù)，然后再通過一次交換祭刚，直接結(jié)束排序牌捷。這樣的需求如何實(shí)現(xiàn)呢？接下來我們來看看希爾排序的原理涡驮。
2. 希爾排序詳解
排序原理：
選定一個(gè)增長(zhǎng)量h暗甥，按照增長(zhǎng)量h作為數(shù)據(jù)分組的依據(jù)，對(duì)數(shù)據(jù)進(jìn)行分組捉捅；
對(duì)分好組的每一組數(shù)據(jù)完成插入排序撤防；
減小增長(zhǎng)量，最小減為1棒口，重復(fù)第二步操作寄月。
增長(zhǎng)量ans：我們這里采用以下規(guī)則
【第一趟排序】
初始增量為ans = length/2 = 4，即將整個(gè)數(shù)組劃分為4個(gè)子組陌凳，分別為4,6剥懒，8,2，9,6合敦，7,1
將每個(gè)子組獨(dú)立的看為一個(gè)要排序的數(shù)組初橘，然后分別進(jìn)行直接排序。
可以看到充岛，每個(gè)子序列現(xiàn)在已經(jīng)有序了保檐。但是將每個(gè)子序列回歸放到整個(gè)數(shù)組中，發(fā)現(xiàn)整個(gè)數(shù)組還是亂序的崔梗。我們接著進(jìn)行第二趟排序夜只。
【第二趟排序】
二次增量為ans = 4/2 = 2，即將整個(gè)數(shù)組劃分為4個(gè)子組蒜魄，分別為4,6,6,9扔亥，2,1,8,7
然后在分別對(duì)兩個(gè)子組進(jìn)行插入排序
【第三趟排序】
第三次增量為ans = 2/2 = 1场躯，即將每個(gè)元素看成一組，子序列合并為一組旅挤，4,1,6,2,6,7,9,8踢关。
其實(shí)，這就是相當(dāng)于直接插入排序粘茄。但是签舞，經(jīng)過第一趟、第二趟的處理之后柒瓣，此時(shí)第三趟要排序的數(shù)組對(duì)比于原數(shù)組儒搭，我們發(fā)現(xiàn)它其實(shí)是被粗略調(diào)整過了，數(shù)組在一定程度上變得相對(duì)有序了芙贫。
此時(shí)搂鲫，僅僅需要對(duì)以上數(shù)列簡(jiǎn)單微調(diào)，無(wú)需大量移動(dòng)操作即可完成整個(gè)數(shù)組的排序磺平。
3. 代碼實(shí)現(xiàn)
public static void shellSort(Integer[] arr) {
//根據(jù)數(shù)組長(zhǎng)度默穴，確定增長(zhǎng)量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) {
//待插入的元素時(shí)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. 復(fù)雜度分析
希爾排序，利用分組粗調(diào)的方式減少了直接插入排序的工作量褪秀，使得算法的平均時(shí)間復(fù)雜度低于0(n^2)。
【時(shí)間復(fù)雜度】O(nlogn)
【空間復(fù)雜度】O(1)
5. 希爾排序與插入排序比較
我們可以使用事后分析法對(duì)希爾排序和插入排序做性能比較薛训。
測(cè)試從100000 ~ 1的逆向數(shù)據(jù)數(shù)組媒吗，我們可以根據(jù)執(zhí)行時(shí)間來完成測(cè)試。
【執(zhí)行時(shí)間】
希爾排序：29ms
直接插入排序：76826ms
折半插入排序：13075ms
可以看出乙埃，希爾排序的效率相比其他兩種效率很高闸英。這就是得益于每趟對(duì)數(shù)組進(jìn)行的粗略調(diào)整。
