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