希尔排序

排序

说明

先按大间隔做插入排序再缩小间隔；性能依赖间隔序列。

分析

先让相距 gap 的元素进行插入排序，可较快地移动离正确位置很远的值。gap 缩到 1 时再完成普通插入排序。

图解推演

补充 [8,5,3,1]，gap=2 时分别排序下标 (0,2) 与 (1,3)，得到 [3,1,8,5]；gap=1 再做插入排序得到 [1,3,5,8]。大步移动减少远距离逆序，但不同 gap 序列有不同上界，不能统称为 O(n log n)。

查看图表代码

适用前提与边界

它就地工作且代码不复杂，但最坏性能依赖所选间隔序列，通常不如标准库排序具有明确保证。

示例输入与调用

a := []int{3, 1, 2}
	ShellSort(a)
	fmt.Println(a)

运行输出

[1 2 3]

完整 Go 示例

package main

import "fmt"

func ShellSort(a []int) {
	for gap := len(a) / 2; gap > 0; gap /= 2 {
		for i := gap; i < len(a); i++ {
			x := a[i]
			j := i
			for j >= gap && a[j-gap] > x {
				a[j] = a[j-gap]
				j -= gap
			}
			a[j] = x
		}
	}
}

func main() {
	a := []int{3, 1, 2}
	ShellSort(a)
	fmt.Println(a)
}