希尔排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func ShellSort(array []int64) {
h := 1
for h < len(array)/3 {
h = h*3 + 1
}
// 设置整个数组的插入排序间隔,每次排序会使数组大致有序
// 以减少最终排序的交换次数,间隔最后为1时会进行一次插入排序
for gap := h; gap > 0; gap = (gap-1)/3 {
// 这里就是插入排序的代码,只是会使用间隔
for j := gap; j < len(array); j++ {
for i := j; i >= gap && array[i] < array[i-gap]; i -= gap {
array[i], array[i-gap] = array[i-gap], array[i]
}
}
}
}

希尔排序算法平均时间复杂度O(n1.3),最好时间复杂度为O(n),最差时间复杂度为O(n2)
空间复杂度O(1),稳定性为不稳定
属于插入排序的改进版,极大提升性能