網(wǎng)站:
JavaEye 作者:
shenyu 鏈接：
http://shenyu.javaeye.com/blog/189563 發(fā)表時間: 2008年05月05日
聲明：本文系JavaEye網(wǎng)站發(fā)布的原創(chuàng)博客文章，未經(jīng)作者書面許可，嚴禁任何網(wǎng)站轉載本文，否則必將追究法律責任！
插入排序 對基本有序的數(shù)組效果非常好，但是對于通常情況則表現(xiàn)一般。假設最小的數(shù)字在最右邊，升序排序時，這個數(shù)則要經(jīng)過n次交換比較換到最左邊。希爾排序則是對插入排序的很好的修正。而且在希爾排序很少出現(xiàn)最壞狀況。
希爾排序通過對數(shù)組 以一定間隔相隔的位置 進行插入排序，以達到讓數(shù)據(jù)快速出現(xiàn)在它應該出現(xiàn)的位置的周圍，使數(shù)組逐步接近基本有序。隨著間隔的減少，數(shù)組越來越接近基本有序，最后間隔為1時，變成標準的插入排序。
數(shù)據(jù)的間隔有多種算法，一般要求間隔序列之間互質(zhì)，此處使用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; //產(chǎn)成Kunth序列
while(h > 0) {
for(int i = h; i < a.length; i++) { //對每個數(shù)據(jù)進行間隔為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; //減小間隔值
}
}
}