一恼蓬、基本思想
希爾排序（Shell Sort）的基本思想是使數(shù)組中任意間隔為h的元素都是有序的蟆炊。
換句話說，一個h有序數(shù)組就是h個相互獨立的有序數(shù)組編織在一起組成的數(shù)組膜蛔。
希爾排序基于插入排序坛猪，交換不相鄰的元素以對數(shù)組的局部進行排序，并最終用插入排序?qū)⒕植坑行虻臄?shù)組排序皂股。
1-1 希爾排序示意圖
具體步驟：
- 產(chǎn)生一個從大到小的遞增序列：h=M墅茉，N，J呜呐，Q就斤，…，1卵史；
- 對于每個遞增序列战转，對其所有元素進行插入排序；
-
當(dāng)h=1排序完成后以躯，整個數(shù)組即有序槐秧。
1-2 希爾排序用例圖
二、算法實現(xiàn)
public static void sort(Comparable[] a) {
int n = a.length;
// 產(chǎn)生一個遞增序列: 1, 4, 13, 40, 121, 364, 1093, ...
int h = 1;
while (h < n/3) h = 3*h + 1;
while (h >= 1) {
// h-sort the array
for (int i = h; i < n; i++) {
for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
exch(a, j, j-h);
}
}
h /= 3;
}
assert isSorted(a);
}
三忧设、性能分析
- 特點
希爾排序是插入排序的變形應(yīng)用刁标，最優(yōu)時間復(fù)雜度目前仍無法證明；
對于一般大小的數(shù)組址晕，可以采用希爾排序解決膀懈；
希爾排序的困難之處在于遞增序列h的選擇，目前尚未有證明某個序列是最好的谨垃。 - 時間復(fù)雜度
最壞情況：O( N^(3/2) )启搂，無法確認(rèn)其平均時間復(fù)雜度
