1溉卓、希爾排序簡介
希爾排序铜异，是插入排序的一種進(jìn)階排序算法，通過一個(gè)不斷縮小的增量序列庶喜，對(duì)無序序列反復(fù)的進(jìn)行拆分并且對(duì)拆分后的序列使用插入排序的一種算法小腊，所以也叫作“縮小增量排序”或者“遞減增量排序”。
既然希爾排序也是使用插入排序進(jìn)行序列排序操作的久窟，為什么會(huì)有希爾排序呢秩冈？
這是基于插入排序的兩點(diǎn)性質(zhì)而來：
第一：對(duì)一個(gè)“幾乎”已經(jīng)排好序的無序序列，插入排序的效率是很高的斥扛，可以達(dá)到線性排序的效率入问。比如，當(dāng)序列中只有一位元素沒有在適當(dāng)?shù)奈恢孟“洌敲凑麄€(gè)序列只需要移動(dòng)該序列的位置即可達(dá)到完成排序的任務(wù)芬失。
第二：但是一般的無序序列不是一個(gè)“幾乎”已經(jīng)排好序的序列，所以插入排序是低效的匾灶。因?yàn)樗看沃荒芤苿?dòng)一位元素棱烂。
基于以上兩點(diǎn)出現(xiàn)了希爾排序，那么希爾排序到底如何利用了這兩個(gè)性質(zhì)呢阶女？
2颊糜、希爾排序的步驟
- 首先根據(jù)初始序列的長度，選定一個(gè)遞減增量序列t1秃踩，t2衬鱼，t3......tk，其中ti>tj憔杨，tk = 1鸟赫。
- 根據(jù)選定的增量序列元素個(gè)數(shù)k，對(duì)初始序列進(jìn)行k趟排序消别。
- 根據(jù)增量序列的值ti抛蚤，每趟排序會(huì)把初始序列劃分成若干個(gè)元素的子序列，然后對(duì)這些子序列使用插入排序妖啥，因?yàn)檫@是遞減增量序列霉颠，所以第一趟的排序，增量值最大荆虱，那么劃分的子序列數(shù)量也就最多蒿偎，每個(gè)子序列的元素也就越少，可以看做是一個(gè)“幾乎”已經(jīng)排好序的序列怀读，當(dāng)增量值越來越小的時(shí)候诉位，子序列數(shù)量也就越少，每個(gè)子序列的元素也就越多菜枷，但是苍糠，基于前幾次的排序，這些子序列雖然元素多啤誊，但是已經(jīng)是一個(gè)“幾乎”排好序的序列了岳瞭，當(dāng)最后一次排序的時(shí)候拥娄，即增量序列的值為1時(shí)，就是對(duì)整個(gè)無序序列進(jìn)行排序瞳筏，這時(shí)整個(gè)序列已經(jīng)是一個(gè)“幾乎”排好序的序列了稚瘾。
以圖為例進(jìn)行說明，假設(shè)給定的初始無序序列如下：
| 4 | 5 | 8 | 2 | 3 | 9 | 7 | 1 |
首先姚炕，我們選擇一個(gè)增量序列摊欠，這個(gè)增量序列如何選擇呢？首先我們得保證第一次的所有子序列元素?cái)?shù)量應(yīng)該至少保證為2個(gè)或以上柱宦，這樣是用插入排序才有意義些椒，如果元素?cái)?shù)量為1，也就是增量序列的第一個(gè)值為初始序列的長度或者更大掸刊，那么這次遍歷將“無功而返”免糕，所以至少應(yīng)該保證子序列元素?cái)?shù)量為2或以上，當(dāng)子序列數(shù)量退化到初始序列長度時(shí)痒给，希爾排序也退化成了插入排序说墨。事實(shí)上，希爾排序的效率依賴于增量序列的選擇苍柏，好的增量序列可以大大的提高希爾排序的效率尼斧，但是增量序列的選擇是和初始序列有關(guān)系的。
一個(gè)好的遞減增量序列選取的標(biāo)準(zhǔn)是：第一试吁、遞減增量序列最后一個(gè)值應(yīng)該為1棺棵；第二、遞減增量序列中的值熄捍，尤其是相鄰的值最好不要互為倍數(shù)的關(guān)系烛恤，如果是互為倍數(shù)的關(guān)系，那么根據(jù)這兩個(gè)序列值的分組將會(huì)有重復(fù)的情況余耽，可能會(huì)做“無用功”缚柏。
該示例中，我們選取的遞減增量序列位[3,2,1]碟贾。
遞減增量序列已經(jīng)有了币喧，下面開始進(jìn)行3趟（增量序列長度為3）排序，先取增量序列第一個(gè)值3袱耽，然后將初始序列分組杀餐，如下：
對(duì)三組子序列[4,2,,7]，[5,3,1]朱巨，[8,9]分別使用插入排序史翘，結(jié)果如下：
然后，對(duì)該序列再次進(jìn)行增量序列的分組，這次增量序列的值為2琼讽，分組情況如下：
對(duì)兩組子序列分別使用插入排序必峰，結(jié)果如下：
最后，對(duì)整個(gè)序列做插入排序（增量序列值為1）即可钻蹬。
從整個(gè)過程可以看出自点，每次的排序，都會(huì)將較小的值轉(zhuǎn)移到序列的前邊脉让，整個(gè)序列的有序性不斷的變強(qiáng)，可以使插入排序達(dá)到更高的效率功炮。
3溅潜、代碼實(shí)現(xiàn)（java版本）
public class ShellSort {
public static void shellSort(int[] arr) {
if (arr == null || arr.length == 0) {
return;
}
int len = arr.length;
// 首先選取一個(gè)增量序列
int gap = 1;
while (gap < len) {
// 先找出增量序列最大的增量值，也就是將序列分為gap組
gap = gap * 3 + 1;
}
while (gap > 0) {
for (int i = gap; i < len; i++) {
int tmp = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > tmp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = tmp;
}
gap = (int) Math.floor(gap / 3);
}
}
}
4薪伏、復(fù)雜度分析
希爾排序的效率依賴于遞減增量序列的選擇滚澜，時(shí)間復(fù)雜度最壞的情況是O(nlog2n)。
