希尔排序
最后更新于：2022-04-02 04:11:18
[TOC]
## 希尔排序
希尔排序是直接插入排序的改进版本。因为直接插入排序对那些几乎已经排好序的数列来说，排序效率极高，达到了`O(n)`的线性复杂度，但是每次只能将数据移动一位。希尔排序创造性的可以将数据移动`n`位，然后将`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)`
## 快速排序
```
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)
}
```
';