Algorithm of Shellsort

main.go

package main

import "fmt"

func main() {
	var nums []int = []int{3, 2, 1, 2, 5, 9, 8, 6, 7}
	shellsort(nums)
	fmt.Println(nums)
}

func shellsort(nums []int) {
	for gap := len(nums) / 2; gap >= 1; gap = gap / 2 {
		for i := gap; i < len(nums); i++ {
			var j int = i
			var tmp int = nums[j]

			for j-gap >= 0 && tmp < nums[j-gap] {
				nums[j] = nums[j-gap]
				j = j - gap
			}

			nums[j] = tmp
		}
	}
}

参考文档：
https://www.runoob.com/w3cnote/shell-sort.html
https://www.cnblogs.com/chengxiao/p/6104371.html

重点：希尔排序主要控制 增量序列(gap) 来提高性能，但是如果增量序列最后为 1 时则时间复杂度与插入排序基本相同 O(N^2)

---

个人对这个算法比较迷惑，网上给出的大量示例基本都会对最后增量为 1 进行处理，意味着如果不处理最后增量 1 则该算法无法保证最终准确性？