算法原理

代码实现

 1 public static  void sort(int[] array){
 2         //数据间隔h 8>4>2>1
 3         int h = array.length / 2;
 4         while(h >= 1){
 5             for (int start = 0; start < h; start++) {
 6                 //对 start, start+h ,start+2h, start+nh 插排
 7                 //前后元素是-h和+h
 8                 for (int i = start + h; i < array.length; i += h) {
 9                     int tmp = array[i];
10                     int j;
11                     for (j = i; j - h >= 0 && tmp < array[j - h]; j -= h) {
12                         array[j] = array[j - h];
13                     }
14                     array[j] = tmp;
15                 }
16             }
17             h /= 2;
18         }
19         System.out.println("Arrays.toString(array) = " + Arrays.toString(array));
20     }

复杂度

希尔排序理论上时间复杂度是O(n^2)，但实际上执行效率能跟O(nlogn)级别的算法媲美，不过当数据量增加时，还是会跟O(nlogn)产生差距。

希尔排序性能高的原因是：希尔排序每一轮排完，会让数据逐渐有序。