深入理解希爾排序
希爾排序
是一種基於插入排序的演算法，相較於插入排序一點一點的移動元素，希爾排序實現了快速移動一大步。
對於大規模亂序陣列插入排序很慢，因為它只會交換相鄰的元素，因此元素只能一點一點地從陣列的一端移動到另一端。假如，如果主鍵最小的元素正好在陣列的盡頭，要將它挪到正確的位置就需要N-1次移動。希爾排序為了加快速度簡單的改進了插入排序，交換不相鄰的元素對陣列的區域性進行排序，並最終用插入排序將區域性有序的陣列排序。
希爾排序的思想是使陣列中任意間隔為h的元素都是有序的。這樣的陣列被稱為h有序陣列。換句話說，一個h有序的陣列就是h個互相獨立的有序陣列編織在一起組成的一個數組。
在進行排序的時候，如果h很大，我們就能將元素移動到很遠的地方，為實現跟小的h有序創造方便。用這種方式，對於任意以1結尾的h序列，我們都能夠將陣列排序。這就是希爾排序。
以下演算法實現使用了序列1/2（3^k-1），從N/3開始遞減至1，我們可以稱這個序列稱為遞增序列。
public
static
void
sort
（
Comparable
［］
a
）
{
//將a［］按升序排列
int
N
=
a
。
length
；
int
h
=
1
；
while
（
h
<
N
/
3
）
h
=
3
*
h
+
1
；
while
（
h
>=
1
）
{
//將陣列變為h有序
for
（
int
i
=
h
；
i
<
N
；
i
++）
{
//將a［i］插入到a［i-h］，a［i-2*h］，a［i-3h］。。。之中。
for
（
int
j
=
i
；
j
>=
h
&&
less
（
a
［
j
］，
a
［
j
-
h
］）；
j
-=
h
）
exch
（
a
，
j
，
j
-
h
）；
}
h
=
h
/
3
；
//使間隔逐步變小
}
}
實現希爾排序的另一種方法是對於每個h，用插入排序將h個子陣列獨立地排序。但因為子陣列使相互獨立的，一個更簡單的方法是在h-子陣列中將每個元素交換到比它大的元素之前去（將比它大的元素向右移動一格）。只需要在插入排序的程式碼中將移動元素的距離由1改為h即可。這樣，希爾排序的實現就轉化為了一個類似於插入排序但使用不同增量的過程。
希爾排序更高效的原因使它權衡了子陣列的
規模
和
有序性
。在排序之初，各個子元素都很短，排序之後子陣列都是部分有序的，這兩種情況都很適合插入排序。子陣列有序的程度取決於遞增序列的選擇。
如何選擇遞增序列呢？
要回答這個問題並不簡單。演算法的效能不僅取決於h，還取決於之間的數學性質，比如它們的公因子等。首先遞增序列應該是互質的。
和選擇排序以及插入排序形成對比的是，希爾排序也可以用於大型陣列。它對任意排序（不一定是隨機的）的陣列表現的也很好。
希爾排序詳細軌跡
希爾排序可視軌跡
透過提升速度來解決其他方式無法解決的問題是研究演算法設計和效能的主要原因之一
有經驗的程式設計師又是會選擇希爾排序，因為對於中等大小的陣列它的執行時間是可以接受的。它的程式碼量很小，且不會使用額外的記憶體空間。
