1. 原理
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
（1）希尔排序是对直接插入排序的优化。
（2）当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
2. 代码实现
//希尔排序 public static void shellSort(int[] array){ int gap = array.length; while(gap > 1){ shell(array,gap); gap /= 2;//增量是多少都可以，随便小伙伴们写 } shell(array,1); } //有增量的直接插入排序 //不是一组希尔排序全部排完，是间隔性的，可能是第一组先插一个，第二组再插一个，第一组再插…… private static void shell(int[] array,int gap){ for(int i = gap;i < array.length;i++){ int tmp = array[i]; int j = i - gap; for(;j >= 0;j -= gap){ if(array[j] > array[j+gap]){ array[j + gap] = array[j]; } else{ break; } } array[j + gap] = tmp; } } public static void main(String[] args) { int[] arr = {3,1,2,4,5}; Sort.shellSort(arr); for (int x : arr) { System.out.print(x + " "); } }
3. 性能分析
| 时间复杂度 | 空间复杂度 | ||
| 最好 | 平均 | 最坏 | |
| O(N) | O(N^1.3) | O(N^2) | O(1) |
| 数据有序 | 难以构造出来 | ||
public static void main(String[] args) { int[] arr2 = new int[10000]; Test.createArray2(arr2); long s2 = System.currentTimeMillis(); Sort.insertSort(arr2); long e2 = System.currentTimeMillis(); System.out.println("直接插入排序的数组逆序的情况："+(e2 - s2)); int[] arr1 = new int[10000]; Test.createArray2(arr1); long s1 = System.currentTimeMillis(); Sort.shellSort(arr2); long e1 = System.currentTimeMillis(); System.out.println("希尔排序的数组逆序的情况："+(e1 - s1)); }
稳定性：不稳定。
由于增量不同，可能导致本来在后面的元素跑到前面去！
