Algorithm - 希尔排序

说明

希尔排序是基于插入排序的优化算法

图解说明 https://www.cnblogs.com/chengxiao/p/6104371.html

Code

package main

import (
	"fmt"
)

func main() {
	arr := []int{1, 6, 8, 3, 23, 454, 15, 334, 8, 6, 35}

	shellSort(arr[:])
	fmt.Println(arr)
}

func shellSort(arr []int) {
	N := len(arr)
	gap := N / 2
	for gap >= 1 {
		for i := gap; i < N; i++ {
			for j := i; j > gap && less(arr[j], arr[j-gap]); j -= gap {
				fmt.Println(arr[j], arr[j-gap])
				exch(arr, j, j-gap)
			}
		}
		fmt.Println(gap)
		gap = gap / 2
	}

}

func less(a, b int) bool {
	return a < b
}

func exch(arr []int, i, min int) {
	arr[i], arr[min] = arr[min], arr[i]
}