2.1.6希尔排序

实现原理

使数组中任意间隔为h的元素都是有序的。然后缩减h再次进行排序，最后缩减到1

效率分析

数学上无法确定希尔排序需要的平均比较次数，最坏情况下是N，达不到平方的级别。希尔排序的代码量很少，且不需要额外的内存空间。在嵌入式平台上比较常用。

代码实现

func sort(a []int) {
  N := len(a)
  h := 1
  for h < N / 3 {
    h = 3 * h + 1
  }
  for h >= 1 {
    for i := h; i < N; i++ {
      // a[i], a[i-h], a[i-2*h]... 做插入排序
      for j := i; j >= h && less(a[j], a[j - h]); j -= h {
        exch(a, j, j - h)
      }
    }
    h = h / 3
  }
}