[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) } ```