排序之希尔排序

希尔排序，也可以叫“缩小增量排序”，可以看作插入排序的概括。

基本思想：先将序列按增量分割成若干序列，然后分别进行插入排序。然后降低增量再进行排序。最后增量降低为1时，对全体记录进行插入排序。

希尔排序是一种不稳定的排序方法。
希尔排序的时间复杂度最坏的情况为 O(n²)，优化可以提高。
希尔排序的空间复杂度为 O(1)。

增量序列(Gap sequences)

增量序列有很多。增量序列都是已经排序好的序列。有一些比较常见的增量序列，设N为数组的长度：

增量序列(k >= 1)	具体增量	最坏的时间复杂度	作者与时间
⌊ N / 2^k ⌋	⌊ N / 2 ⌋, ⌊N / 4⌋, …, 1	O(n²)	Shell 1959
2^k - 1	1, 3, 7, 15, 31, 63, …	O(n^3/2)	Hibbard 1963
2^p3^q的连续数字	1, 2, 3, 4, 6, 8, 9, 12, …	O(N log²N)	Pratt 1971

希尔排序的伪代码：

// 设置增量gap, 并逐步减少增量
gap ← ⌊length(Arr)/2⌋
WHILE gap > 0
  i ← gap
  // 从第gap个元素，逐个对其所在组进行直接插入排序操作
  WHILE i < length(Arr)
    minIndex ← i
    WHILE minIndex >= gap and arr[minIndex] < arr[minIndex - gap]
      // 交换最小值的位置
      swap arr[minIndex] and arr[min - gap]
      minIndex ← minInde - gap
    END WHILE
    i ← i+1
  END WHILE
  gap ← ⌊gap/2⌋
END WHILE