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