• 要求
• 算法描述
• 算法实现
• 参考资料

要求

• 能够用自己语言描述希尔排序算法

  算法描述

1. 首先选取一个间隙序列，如 (n/2，n/4 … 1)，n 为数组长度
2. 每一轮将间隙相等的元素视为一组，对组内元素进行插入排序，目的有二① 少量元素插入排序速度很快② 让组内值较大的元素更快地移动到后方
3. 当间隙逐渐减少，直至为 1 时，即可完成排序

   算法实现

   private static void shell(int[] a) {
   int n = a.length;
   for (int gap = n / 2; gap > 0; gap /= 2) {
       // i 代表待插入元素的索引
       for (int i = gap; i < n; i++) {
           int t = a[i]; // 代表待插入的元素值
           int j = i;
           while (j >= gap) {
               // 每次与上一个间隙为 gap 的元素进行插入排序
               if (t < a[j - gap]) { // j-gap 是上一个元素索引，如果 > t，后移
                   a[j] = a[j - gap];
                   j -= gap;
               } else { // 如果 j-1 已经 <= t, 则 j 就是插入位置
                   break;
               }
           }
           a[j] = t;
           System.out.println(Arrays.toString(a) + " gap:" + gap);
       }
   }
   }

   参考资料

• https://en.wikipedia.org/wiki/Shellsort

插入排序的变形