See Chrome Devtools!

希尔排序

本质就是一个步长从 n / 2 开始指数级缩短的插入排序。

• 稳定性

  不稳定（跳着插的）

• 复杂度

  • 时间复杂度

    O(n) ~ O(n(log n)^2)

    • 最好情况

      数组有序

    • 最差情况

• 原理

  基于以下两条原理：

  1. 插入排序在针对几乎已经排好的数据时进行操作时，效率是线性的。

  2. 插入排序本身低效，如果数据跨度太大效率就会很低。

     从 1/2 数组长度开始，按这个距离，将以这个距离间隔的数字用插入排序排好。

     因为插入排序在数组有序时只会遍历一次，不会瞎搞，所以只要基本有序就会很快，只有一次 O(n) 的复杂度。

     距离不断缩小（一般是每次 / 2），一直到最后一次整理距离为 1 的数组长度，这样插入排序导致的数组漂移就不会影响太多元素。

• 优化方法

  其实就是跟比较次数有关，如果跑得轮数太少，就会退化为普通插入排序。

  1. 基础版

     步长 n / 2^i（也就是不断 / 2），最差复杂度 n^2。

  2. 2^i - 1

     最差复杂度 n^2。

  3. 2^i3^伊普西龙

     可以让复杂度到达 n(log n)

  4. 一个复杂的算式

     我看不懂