希尔排序

• 原理
  希尔排序又叫作缩小增量排序，其本质还是插入排序，只不过是将待排序列按某种规则分成几个子序列，分别对这几个子序列进行直接插入排序。这个规则的体现就是增量的选取，如果增量为1，就是直接插入排序。例如，先以增量5来分割序列，即将下标为0、5、10、15…的关键字分成一组，将下标为1、6、11、16…的关键字分成另一组等，然后分别对这些组进行直接插入排序，这就是一趟希尔排序。将上面排好序的整个序列，再以增量2分割，即将下标为0、2、4、6、8…的关键字分成一组，将下标为1、3、5、7、9…的关键字分成另一组等，然后分别对这些组进行直接插入排序，这又完成了一趟希尔排序。最后以增量1分割整个序列，其实就是对整个序列进行一趟直接插入排序，从而完成整个希尔排序。没有理解的可以看 视频讲解🖱️

---

• 增量的选取
  第一个增量一般是数组长度的一半，第二个增量是第一个增量的一半，以此类推 … 直到为 1

---

• 重要考点
  请回答希尔排序增量选取时需要注意的地方。答:
  1）增量序列的最后一个值一定取 1
  2）增量序列中的值应尽量没有除 1 之外的公因子

---

• 复杂度
  1）增量除以2并向下取整，其中 n 为序列长度，此时时间复杂度：O(n²)
  2）增量为 2^k+1 小于待排序列长度，k为大于等于1的整数，增量序列末尾的1是额外添加的，此时时间复杂度：O(n^1.5)
  空间复杂度：O(1)

---

• 实践
  原始序列:49 38 65 97 76 13 27 49 55 04
  1）以增量 5 分割序列,得到 13   27   49   55   04   49   38   65   97   76
  2）以增量 3 分割序列,得到 13   04   49   38   27   49   55   65   97   76
  3）以增量 1 分割序列,得到 04   13   27   38   49   49   55   65   76   97
  或
  1）以增量 5 分割序列,得到 13   27   49   55   04   49   38   65   97   76
  2）以增量 2 分割序列,得到 04   27   13   49   38   55   49   65   97   76
  3）以增量 1 分割序列,得到 04   13   27   38   49   49   55   65   76   97

---

说明:对于希尔排序，考研中的重点是上边所讲的执行流程，考题经常给出一个待排序列，让考生写出每一趟排序的执行情况。而对于希尔排序的算法代码，考研要求得不多。