-
介绍
希尔排序的原理跟插入排序差不多，但是希尔排序可以减少数据搬移的次数。排序的原则是将数据区分成特定间隔的几个小区块，以插入排序法完成区块内的数据后再渐渐减少间隔的距离。 -
演示
代码如下：
private static void shellSort() {
int data[] = {6, 4, 8, 1, 3, 7, 2, 9, 5};
int i, j, k = 1, tmp, jmp = data.length / 2;
while (jmp != 0) {
for (i = jmp; i < data.length; i++) {
tmp = data[i];
j = i - jmp;
while (j >= 0 && tmp < data[j]) {
data[j + jmp] = data[j];
j = j - jmp;
}
data[jmp + j] = tmp;
}
jmp = jmp / 2;
}
}
排序结果：
希尔排序结果.png
- 分析
- 在任何情况下的时间复杂度均为P(n³/n²);（3/2的这个幂打不上）；
- 是稳定排序；
- 只需要一个额外空间，所以空间复杂度是最佳的；
- 此排序法适用于数据大部分都已排序完成的情况。
