希爾排序
-自然語言描述：
先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分組。所有距離為d1的倍數(shù)的記錄放在同一個組中投慈。先在各組內(nèi)進行直接插入排序；然后策吠，取第二個增量d2<d1重復(fù)上述的分組和排序逛裤，直至所取的增量 d t = 1(dt < dt-1…<d2<d1)，即所有記錄放在同一組中進行直接插入排序為止猴抹。
希爾排序通過將比較的全部元素分為幾個區(qū)域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步锁荔。然后算法再取越來越小的步長進行排序蟀给，算法的最后一步就是普通的插入排序，但是到了這步阳堕，需排序的數(shù)據(jù)幾乎是已排好的了（此時插入排序較快）跋理。
-Java語言實現(xiàn)：
public static void sort(Comparable[] a){
int N = a.length;
int h = 1;
while (h < N/3) h = 3*h + 1;
while (h >= 1){
for(int i = h; i < N; i++){
for(int j = i; j>=h&&(a[j] <a[j-1]);j -=h){
Comparable temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
h = h/3;
}
}
-驗證代碼：
public class Shell {
public static void sort(Comparable[] a){
//升序
int N = a.length;
int h = 1;
while (h < N/3) h = 3*h + 1;
while (h >=1 ){
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 = h/3;
}
}
private static boolean less(Comparable v, Comparable w){ return v.compareTo(w) < 0; }
private static void exch(Comparable[] a, int i, int j){
Comparable t = a[i]; a[i] = a[j]; a[j] = t; }
private static void show(Comparable[] a){ // 在單行中打印數(shù)組
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
public static boolean isSorted(Comparable[] a){
int length = a.length;
for (int i = 1;i < length ;i++ ) {
if (less(a[i],a[i -1])) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String[] a = In.readStrings();
sort(a);
assert isSorted(a);
show(a);
}
}
