思想:使数组中间隔为h的元素是有序的 基于插入排序
public class Shell {
public static void sort(Comparable[] a) {
// 将a[]按升序排列
int N = a.length;
int h = 1;
while (h < N / 3) {
h = 3 * h + 1; // 1,4,13,40,121,364,1093,……
}
while (h >= 1) {
for (int i = h; i < N; i++) {
// a[j]<h-子数组中的前一个数就往前移
for (int j = i; j >= h && less(a[j], a[j - h]); j = 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) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Integer[] a = {1, 3, 7, 7, 0, 5, 7, 1, 0, 5, 9};
sort(a);
show(a);
}
}