java代碼
public static void sort(Comparable[] a)
{
int N = a.length;
h = 1;
while(h < N/3) h = h*3 + 1;//步長(zhǎng)可為1,4,13,40,121.......
while(h >= 1)
{
for (int i = h; i < N; i++)
{
for (int j = i; j >= h &&less(a[j], a[j - h]); j -= h)//函數(shù)less(a,b)比較a,b的大小，a<b返回YES
exch(a, j, j - h);//交換數(shù)組a中a[j],a[j-h]兩個(gè)元素的位置
}
h = h/3;
}
}
解釋
希爾排序是一個(gè)基于插入排序的改進(jìn)型插入排序算法吐辙。由于插入排序一次只能交換相鄰的元素宣决，因此元素只能一點(diǎn)點(diǎn)的從數(shù)組的一端移動(dòng)到另一端。如果最小的元素在數(shù)組的末尾的話昏苏，那就需要N-1次移動(dòng)尊沸，因此對(duì)于插入排序的效率是非常低的。
- 希爾排序的思想是使數(shù)組中任意間隔為h的元素是有序的贤惯。這樣的數(shù)組也稱為h有序數(shù)組洼专，也即一個(gè)數(shù)組是h個(gè)互相獨(dú)立的有序數(shù)組編制在一起組成的數(shù)組。如圖1所示為一個(gè)h有序數(shù)組包含了4個(gè)有序子數(shù)組孵构。
圖1:一個(gè)h有序數(shù)組包含的4個(gè)有序子數(shù)組
排序算法解析
以步長(zhǎng)h=2*h+1(即h為1腥刹，3朝群，7...)對(duì)圖2輸入數(shù)列進(jìn)行排序?yàn)槔馕鱿査惴ǖ牟襟E。
注意：實(shí)際就是a[0]和a[h]比較玛追，a[1]和a[h+1]比較但两。胳施。奇适。每比較完一輪后，就縮小h的值叹俏。
圖2:輸入數(shù)組
- 根據(jù)
while(h < N/2) h = h*2 + 1;得到步長(zhǎng)h=7妻枕， - 第一輪排序，間隔為7的兩個(gè)元素比較，如果符合交換條件就交換數(shù)組a中a[j],a[j-h]兩個(gè)元素的位置屡谐，得到結(jié)果如圖3所示述么。
for (int i = 7; i < N; i++)
{
for (int j = i; j >= h &&less(a[j], a[j - h]); j -= h)//如果a[j]小于a[j - h]
exch(a, j, j - h); // 就交換數(shù)組a中a[j],a[j-h]兩個(gè)元素的位置
}
圖3:步長(zhǎng)為7的排序結(jié)果
- 第一輪排序結(jié)束后，縮小步長(zhǎng)h愕掏，此時(shí)h=3;
-
繼續(xù)比較度秘，與步驟2相似，得到結(jié)果如圖4所示
圖4:步長(zhǎng)為3的排序結(jié)果 -
繼續(xù)縮小步長(zhǎng)h饵撑，重復(fù)步驟4剑梳，（最后這一步的排序也就是普通的插入排序）得到結(jié)果如圖5所示
圖5:步長(zhǎng)為1的排序結(jié)果 -
雖然插入的效率不高，但是插入排序在對(duì)幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)滑潘，效率卻非常高垢乙。得到結(jié)果如圖6所示。
圖6：排序結(jié)果
希爾排序動(dòng)態(tài)圖
圖8：以23, 10, 4, 1的步長(zhǎng)序列進(jìn)行希爾排序
