实现代码：

public class ShellSort extends SortBase {

? ? @Override
? ? public Integer[] sort(Integer[] a) {
? ? ? ? // TODO Auto-generated method stub
? ? ? ? print("init",a);
? ? ? ? Integer h = a.length;
? ? ? ? Integer temp = 0;
? ? ? ? while(h >= 1) {
? ? ? ? ? ? for(int i=h;i? ? ? ? ? ? ? ? for(int j=i;j>=h && a[j] < a[j-h];j -= h) {
? ? ? ? ? ? ? ? ? ? temp = a[j];
? ? ? ? ? ? ? ? ? ? a[j] = a[j-h];
? ? ? ? ? ? ? ? ? ? a[j-h] = temp;
? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? h /= 9;
? ? ? ? }
? ? ? ? print("result",a);
? ? ? ? return a;
? ? }
? ?
? ? public static void main(String[] args) {
? ? ? ? Integer[] a = {2,1,5,9,0,6,8,7,3};
? ? ? ? (new ShellSort()).sort(a);
? ? }
}

运行结果：

init: [2 ,1 ,5 ,9 ,0 ,6 ,8 ,7 ,3]

1: [0 ,1 ,5 ,7 ,2 ,6 ,8 ,9 ,3]

2: [0 ,1 ,2 ,6 ,3 ,7 ,5 ,9 ,8]

3: [0 ,1 ,2 ,3 ,5 ,6 ,7 ,8 ,9]

result: [0 ,1 ,2 ,3 ,5 ,6 ,7 ,8 ,9]

效率：

最坏情况时间复杂度为：O(n^1.5),平均时间复杂度为O(nlogn)。