go-希尔排序算法

package main

import "fmt"

func main() {
	var arr = []int{9, 7, 6, 8, 4, 1, 5, 2, 3}
	fmt.Printf("arr: %v\n", arr)
	var gap = 1
	for {
		if gap >= (len(arr))/3 {
			break
		}
		gap = gap*3 + 1

	}
	fmt.Printf("gap: %v\n", gap)
	for gap := gap; gap > 0; gap = (gap - 1) / 3 {
		for i := gap; i < len(arr); i++ {
			for j := i; j > gap-1 && arr[j] < arr[j-gap]; j -= gap {
				swap(arr, j, j-gap)
			}

		}
		fmt.Printf("arr: %v\n", arr)
	}
	fmt.Printf("arr: %v\n", arr)
}
func ShellSort(nums []int) []int {
	var gap = 1
	for {
		if gap >= (len(nums)-1)/3 {
			break
		}
		gap = gap*3 + 1

	}
	fmt.Printf("gap: %v\n", gap)
	for step := gap; step > 0; step = (step - 1) / 3 {
		for i := step; i < len(nums); i += step {
			for j := i - step; j >= 0 && nums[j+step] < nums[j]; j -= step {
				nums[j], nums[j+step] = nums[j+step], nums[j]
			}
		}
	}
	return nums
}
func swap(arr []int, a, b int) {
	var temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp
}

arr: [9 7 6 8 4 1 5 2 3]
gap: 4
arr: [3 1 5 2 4 7 6 8 9]
arr: [1 2 3 4 5 6 7 8 9]
arr: [1 2 3 4 5 6 7 8 9]