1.希尔排序的思想：

排序实际上都是为了消除逆序数对，使得数组越来越有序，不能只处理相邻的逆序数对。
所以就按照步长进行分组，然后不断缩小步长直到1，当步长缩小至1时，实际上是在做插入排序。
插入排序：相邻元素交换，若有逆序数对则交换位置，然后将交换过的元素与前面的元素进行比较再交换，最后前面的部分形成一个有序数组。

2.实现 shell 排序

  1. public void shellSort(Int[] arr){
  2.     int length = data.length / 2;
  3.     while(length > 0){
  4.         // 当步长为 length 时， 从步长开始，以便可以取到前面的数
  5.         for(int i = length; i < data.length; i++){
  6.             int temp = arr[i];
  7.             for(int j = i; (j - length) >= 0 &&  arr[j] < arr[j-length]; j-= length){
  8.                 arr[j] = arr[j - length];
  9.             }
  10.             arr[j] = temp;
  11.         }
  12.         length /= 2;
  13.     }    
  14. }

3.时间复杂度分析：

image.png

4.使用步长序列进行：h以一个式子变化

  1. h = 3 * h + 1;

对于不同的数据体量，根据不同的步长变化，性能也会变化。