一、先上维基的图：希尔排序wiki
图一、插入排序的例子
| 分类 | 排序算法 |
|---|---|
| 数据结构 | 数组 |
| 最差时间复杂度 | 根据步长序列的不同而不同。已知最好的： |
| 最优时间复杂度 | O(n) |
| 平均时间复杂度 | 根据步长序列的不同而不同。 |
| 最差空间复杂度 | O(n) |
13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10然后我们对每列进行排序：
10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45将上述四行数字，依序接在一起时我们得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了，然后再以3为步长进行排序：
10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45排序之后变为：
10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94此时为[ 10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94 ]
static <E extends Comparable<? super E>> void shellSort(List<E> a) {
int h = 1;
while (h < a.size()/3) {
h = h*3 + 1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
}
for (; h >= 1; h /= 3) {
for (k = 0; k < h; k++) {
for (int i = h + k; i < a.size(); i+=h) {
for (int j = i; j >= h && a.get(j).compareTo(a.get(j-h)) < 0; j-=h) {
Collections.swap(a, j, j-h);
}
}
}
}
}
public class ShellInsertion {
public static int count = 0;
public static void main(String[] args) {
int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
print(data);
shellSort(data);
print(data);
}
public static void shellSort(int[] data) {
// 计算出最大的h值
int h = 1;
while (h <= data.length / 3) {
h = h * 3 + 1;
}
while (h > 0) {
for (int i = h; i < data.length; i += h) {
if (data[i] < data[i - h]) {
int tmp = data[i];
int j = i - h;
while (j >= 0 && data[j] > tmp) {
data[j + h] = data[j];
j -= h;
}
data[j + h] = tmp;
print(data);
}
}
// 计算出下一个h值
h = (h - 1) / 3;
}
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "\t");
}
System.out.println();
}
} 原文：http://blog.csdn.net/waycaiqi/article/details/44538273