網站:
JavaEye 作者:
shenyu 鏈接：
http://shenyu.javaeye.com/blog/189563 發表時間: 2008年05月05日
聲明：本文系JavaEye網站發布的原創博客文章，未經作者書面許可，嚴禁任何網站轉載本文，否則必將追究法律責任！
插入排序 對基本有序的數組效果非常好，但是對于通常情況則表現一般。假設最小的數字在最右邊，升序排序時，這個數則要經過n次交換比較換到最左邊。希爾排序則是對插入排序的很好的修正。而且在希爾排序很少出現最壞狀況。
希爾排序通過對數組 以一定間隔相隔的位置 進行插入排序，以達到讓數據快速出現在它應該出現的位置的周圍，使數組逐步接近基本有序。隨著間隔的減少，數組越來越接近基本有序，最后間隔為1時，變成標準的插入排序。
數據的間隔有多種算法，一般要求間隔序列之間互質，此處使用Kunth序列：h = h * 3 + 1
希爾排序的時間效率很難從理論上證明，實驗表明大約是O(n^(3/2)) ~ O(n^(7/6))之間。
代碼如下：
class Shell {
public static void main(String[] args) {
int[] a = {9,8,7,6,5,4,3,2,1};
sort(a);
println(a);
}
private static void println(int[] a) {
for(int i: a) System.out.print(i + " ");
System.out.println();
}
private static void sort(int[] a) {
int h = 1;
while(h <= a.length/3) h = h * 3 + 1; //產成Kunth序列
while(h > 0) {
for(int i = h; i < a.length; i++) { //對每個數據進行間隔為h的插入排序
int pos = i;
int temp = a[i];
while(pos >= h && a[pos - h] > temp) {
a[pos] = a[pos-h];
pos -= h;
}
a[pos] = temp;
}
h = (h - 1) / 3; //減小間隔值
}
}
}