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