希尔排序
1959 年一个叫Donald L. Shell (March 1, 1924 – November 2, 2015)的美国人在Communications of the ACM 国际计算机学会月刊发布了一个排序算法，从此名为希尔排序的算法诞生了。
注：ACM = Association for Computing Machinery，国际计算机学会，世界性的计算机从业员专业组织，创立于1947年，是世界上第一个科学性及教育性计算机学会。
希尔排序是直接插入排序的改进版本。因为直接插入排序对那些几乎已经排好序的数列来说，排序效率极高，达到了O(n)的线性复杂度，但是每次只能将数据移动一位。希尔排序创造性的可以将数据移动n位，然后将n一直缩小，缩到与直接插入排序一样为1，请看下列分析。
希尔排序属于插入类排序算法。
一、算法介绍
有一个N个数的数列：
- 先取一个小于
N的整数d1，将位置是d1整数倍的数们分成一组，对这些数进行直接插入排序。接着取一个小于
d1的整数d2，将位置是d2整数倍的数们分成一组，对这些数进行直接插入排序。接着取一个小于
d2的整数d3，将位置是d3整数倍的数们分成一组，对这些数进行直接插入排序。...
直到取到的整数
d=1，接着使用直接插入排序。这是一种分组插入方法，最后一次迭代就相当于是直接插入排序，其他迭代相当于每次移动n个距离的直接插入排序，这些整数是两个数之间的距离，我们称它们为增量。
我们取数列长度的一半为增量，以后每次减半，直到增量为1。
举个简单例子，希尔排序一个 12 个元素的数列：[5 9 1 6 8 14 6 49 25 4 6 3]，增量d的取值依次为：6，3，1：
x 表示不需要排序的数
取 d = 6 对 [5 x x x x x 6 x x x x x] 进行直接插入排序，没有变化。
取 d = 3 对 [5 x x 6 x x 6 x x 4 x x] 进行直接插入排序，排完序后：[4 x x 5 x x 6 x x 6 x x]。
取 d = 1 对 [4 9 1 5 8 14 6 49 25 6 6 3] 进行直接插入排序，因为 d=1 完全就是直接插入排序了。
越有序的数列，直接插入排序的效率越高，希尔排序通过分组使用直接插入排序，因为步长比1大，在一开始可以很快将无序的数列变得不那么无序，比较和交换的次数也减少，直到最后使用步长为1的直接插入排序，数列已经是相对有序了，所以时间复杂度会稍好一点。
在最好情况下，也就是数列是有序时，希尔排序需要进行logn次增量的直接插入排序，因为每次直接插入排序最佳时间复杂度都为：O(n)，因此希尔排序的最佳时间复杂度为：O(nlogn)。
在最坏情况下，每一次迭代都是最坏的，假设增量序列为：d8 d7 d6 ... d3 d2 1，那么每一轮直接插入排序的元素数量为：n/d8 n/d7 n/d6 .... n/d3 n/d2 n，那么时间复杂度按照直接插入的最坏复杂度来计算为：
假设增量序列为 ⌊N/2⌋ ，每次增量取值为比上一次的一半小的最大整数。
O( (n/d8)^2 + (n/d7)^2 + (n/d6)^2 + ... + (n/d2)^2 + n^2)
= O(1/d8^2 + 1/d7^2 + 1/d6^2 + ... + 1/d2^2 + 1) * O(n^2)
= O(等比为1/2的数列和) * O(n^2)
= O(等比求和公式) * O(n^2)
= O( (1-(1/2)^n)/(1-1/2) ) * O(n^2)
= O( (1-(1/2)^n)*2 ) * O(n^2)
= O( 2-2*(1/2)^n ) * O(n^2)
= O( < 2 ) * O(n^2)
所以，希尔排序最坏时间复杂度为O(n^2)。
不同的分组增量序列，有不同的时间复杂度，但是没有人能够证明哪个序列是最好的。Hibbard增量序列：1，3，7，···，2n−1是被证明可广泛应用的分组序列，时间复杂度为：Θ(n^1.5)。
希尔排序的时间复杂度大约在这个范围：O(n^1.3)~O(n^2)，具体还无法用数学来严格证明它。
希尔排序不是稳定的，因为每一轮分组，都使用了直接插入排序，但分组会跨越n个位置，导致两个相同的数，发现不了对方而产生了顺序变化。
二、算法实现
package main
import "fmt"
// 增量序列折半的希尔排序
func ShellSort(list []int) {
// 数组长度
n := len(list)
// 每次减半，直到步长为 1
for step := n / 2; step >= 1; step /= 2 {
// 开始插入排序，每一轮的步长为 step
for i := step; i < n; i += step {
for j := i - step; j >= 0; j -= step {
// 满足插入那么交换元素
if list[j+step] < list[j] {
list[j], list[j+step] = list[j+step], list[j]
continue
}
break
}
}
}
}
func main() {
list := []int{5}
ShellSort(list)
fmt.Println(list)
list1 := []int{5, 9}
ShellSort(list1)
fmt.Println(list1)
list2 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3}
ShellSort(list2)
fmt.Println(list2)
list3 := []int{5, 9, 1, 6, 8, 14, 6, 49, 25, 4, 6, 3, 2, 4, 23, 467, 85, 23, 567, 335, 677, 33, 56, 2, 5, 33, 6, 8, 3}
ShellSort(list3)
fmt.Println(list3)
}
输出：
[5]
[5 9]
[1 3 4 5 6 6 6 8 9 14 25 49]
[1 2 2 3 3 4 4 5 5 6 6 6 6 8 8 9 14 23 23 25 33 33 49 56 85 335 467 567 677]
按照之前分析的几种排序算法，一般建议待排序数组为小规模情况下使用直接插入排序，在规模中等的情况下可以使用希尔排序，但在大规模还是要使用快速排序，归并排序或堆排序。
系列文章入口
我是陈星星，欢迎阅读我亲自写的 数据结构和算法(Golang实现)，文章首发于 阅读更友好的GitBook。
数据结构和算法(Golang实现)(1)简单入门Golang-前言
数据结构和算法(Golang实现)(2)简单入门Golang-包、变量和函数
数据结构和算法(Golang实现)(3)简单入门Golang-流程控制语句
数据结构和算法(Golang实现)(4)简单入门Golang-结构体和方法
数据结构和算法(Golang实现)(5)简单入门Golang-接口
数据结构和算法(Golang实现)(6)简单入门Golang-并发、协程和信道
数据结构和算法(Golang实现)(7)简单入门Golang-标准库
数据结构和算法(Golang实现)(8.1)基础知识-前言
数据结构和算法(Golang实现)(8.2)基础知识-分治法和递归
数据结构和算法(Golang实现)(9)基础知识-算法复杂度及渐进符号
数据结构和算法(Golang实现)(10)基础知识-算法复杂度主方法
数据结构和算法(Golang实现)(11)常见数据结构-前言
数据结构和算法(Golang实现)(12)常见数据结构-链表
数据结构和算法(Golang实现)(13)常见数据结构-可变长数组
数据结构和算法(Golang实现)(14)常见数据结构-栈和队列
数据结构和算法(Golang实现)(15)常见数据结构-列表
数据结构和算法(Golang实现)(16)常见数据结构-字典
数据结构和算法(Golang实现)(17)常见数据结构-树
数据结构和算法(Golang实现)(18)排序算法-前言
数据结构和算法(Golang实现)(19)排序算法-冒泡排序
数据结构和算法(Golang实现)(20)排序算法-选择排序
数据结构和算法(Golang实现)(21)排序算法-插入排序
数据结构和算法(Golang实现)(22)排序算法-希尔排序
数据结构和算法(Golang实现)(23)排序算法-归并排序
数据结构和算法(Golang实现)(24)排序算法-优先队列及堆排序
数据结构和算法(Golang实现)(25)排序算法-快速排序
数据结构和算法(Golang实现)(26)查找算法-哈希表
数据结构和算法(Golang实现)(27)查找算法-二叉查找树
数据结构和算法(Golang实现)(28)查找算法-AVL树
数据结构和算法(Golang实现)(29)查找算法-2-3树和左倾红黑树
数据结构和算法(Golang实现)(30)查找算法-2-3-4树和普通红黑树
