1、什么是希尔排序：
插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。这是官方对希尔排序的定义。
从概念中，无法知道到底希尔排序是怎么样原理。我接下来用例子来说明。
例如有一个n=25个数字的数列。
list :=[]int {10,3,4,19,2,22,54,222,555,32,67,29,1,90,23,77,24,28,100,70,31,26,25,84,99}
我们对该数列进行
第一次分组。分组排序原则是step=n/2=12。这时这个要排序数列为：[0],[12],[24]对应的三个单元的数列{10,1,99}，先对这个三个数进行排序。步长为12的倍数下标数列。排序结果[0]=1,[12]=10,[24]=99
第二次分组。再对第一次的step进行除以2.step=step/2=6,这时这个要排序数列为：[0],[6],[12],[18],[24]对应的5个单元的数列{1,54,10,100,99},该数列经过第一次排序后跟原数列发生变化了。先对这个5个数进行排序。步长为6的倍数下标数列。排序结果:[0]=1,[6]=10,[12]=54,[18]=99,[24]=100
第三次分组。再对第二次的step进行step=step/2=3,这时要排序数列为:[0],[3],[6],[9],[12],[15],[18],[21],[24].对应数列为{1,19,10,32,54,77,99,26,100}，接下来对这个数列进行排序，步长为3的整数倍无序数列。排序结果：[0]=1,[3]=10,[6]=19,[9]=26,[12]=32,[15]=54,[18]=77,[21]=99,[24]=100
第四分组。再对第三次的step进行step=step/2=3/2=1.这个时候就对整个数列进行适当位置互换。
希尔排序：案例代码
package main
import "fmt"
// 增量序列折半的希尔排序
func ShellSort(list []int) {
// 数组长度
n := len(list)
loop := 0
// 每次减半，直到步长为 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 {
loop++
// 满足插入那么交换元素
if list[j+step] < list[j] {
list[j], list[j+step] = list[j+step], list[j]
continue
}
break
}
}
}
//fmt.Println(temp0)
fmt.Printf("循环次数：%d", loop)
fmt.Println()
}
func main() {
list := []int{10, 3, 4, 19, 2, 22, 54, 222, 555, 32, 67, 29, 1, 90, 23, 77, 24, 28, 100, 70, 31, 26, 25, 84, 99}
ShellSort(list)
fmt.Println(list)
}
假如对上面的数列用冒泡算法来执行。
冒泡排序：代码：
package main
import (
"fmt"
)
func main() {
var nums = []int{10, 3, 4, 19, 2, 22, 54, 222, 555, 32, 67, 29, 1, 90, 23, 77, 24, 28, 100, 70, 31, 26, 25, 84, 99}
BubbleSort(nums)
fmt.Println(nums)
}
func BubbleSort(list []int) {
listLen := len(list)
loop := 0
for i := listLen - 1; i > 1; i-- {
didSwap := false
for j := 0; j < i; j++ {
if list[j] >= list[j+1] {
list[j], list[j+1] = list[j+1], list[j]
didSwap = true
}
loop++
}
if !didSwap {
fmt.Println("循环次数：", loop) //打印循环次数
return
}
}
}
从上面两个例子看出来。冒泡排序需要循环比较245次，而希尔排序只需要123次。效率几乎提升一倍。