Java算法之实现希尔排序实例源码。什么是希尔排序步？希尔排序步长的选择很重要，不同的选择方式性能差异很大。实验时候，生成一个长度为 0×400000（该数字为16进制）随机的整形数组，存放于硬盘上的文本文件内。每次排序均将此数组读入内存后，再排序，再将排序结果写入硬盘文件。只对排序操作计时，读文件和写文件不计时。步长选择方式为最基本的1,2,4,8,16,32,64…size/2。在测试中，排序耗时7150毫秒。

private static void shellSort1(int[] a) {
int size = a.length;
for(int gap = size/2; gap>=1; gap /= 2) {
for(int i=gap; i<size; i++) {
int k;
int temp = a[i];
for(k = i-gap; k>=0 && a[k] > temp; k -= gap) {
a[k+gap] = a[k];
}
a[k+gap] = temp;
}
}
}

步长选择方式更改为特殊公式计算出的序列1,5,19,41,109,209,505,929,2161,3905…

在我的测试中，排序耗时930毫秒

private static void shellSort2(int[] a) {
int[] gaps = generateShellGaps(a.length / 2);
for(int j=gaps.length-1; j>=0; j–) {
for(int i=gaps[j]; i<a.length; i++) {
int k;
int temp = a[i];
for(k = i-gaps[j]; k>=0 && a[k] > temp; k -= gaps[j]) {
a[k+gaps[j]] = a[k];
}
a[k+gaps[j]] = temp;
}
}
}

private static int[] generateShellGaps(int max) {
List<Integer> a = new ArrayList<>();
List<Integer> b = new ArrayList<>();
int x = 1;
for(int i=1; x<max; i++) {
a.add(x);
x = (int) ((Math.pow(4, i) – Math.pow(2, i)) * 9 + 1);
}
x = 5;
for(int i=1; x<max; i++) {
b.add(x);
x = (int) ((Math.pow(2, i+2) – 3) * Math.pow(2, i+2) + 1);
}
int i=0, j=0, k=0;
int[] result = new int[a.size()+b.size()];
while(i<a.size() && j<b.size()) {
if(a.get(i) < b.get(j)) {
result[k] = a.get(i);
i++;
}else {
result[k] = b.get(j);
j++;
}
k++;
}
while(i<a.size()) {
result[k] = a.get(i);
i++;
k++;
}
while(j<b.size()) {
result[k] = b.get(j);
j++;
k++;
}
return result;
}

调用系统自带的快速排序Arrays.sort(array)，耗时190毫秒，速度真是超级快。
希尔排序还可以用多线程实现，详见这篇文章：http://blog.csdn.net/andycpp/article/details/8592317