golang写希尔排序

希尔排序（Shell Sort）是插入排序的一种优化版本，它通过将数组分为若干个子序列进行插入排序，随着排序的进行，子序列的大小逐渐减小，最后达到直接插入排序。Golang编写希尔排序的主要步骤如下：

1. **选择增量序列**：希尔排序的关键是选择合适的增量序列，常见的有直接插入排序的增量序列（如1, 2, 4, ..., n/2）。

2. **分割数组**：对于给定的增量，将数组分为n/i个子序列，i是当前增量。

3. **内部排序**：对每个子序列进行插入排序。由于子序列较小，可以直接使用插入排序。

4. **逐步缩小增量**：重复步骤2和3，每次减小增量直到增量为1，这时就完成了整个排序过程。

5. **实现代码**：

package main

import (
	"fmt"
)

func shellSort(arr []int) {
	n := len(arr)
	// 常见的增量序列：{7, 5, 3, 1}
	for gap := n / 2; gap > 0; gap /= 2 {
		for i := gap; i < n; i++ {
			// 将元素arr[i]暂时存到arr暂存区
			temp := arr[i]
			j := i

			// 对子序列进行插入排序
			for j >= gap && arr[j-gap] > temp {
				arr[j] = arr[j-gap]
				j -= gap
			}
			arr[j] = temp // 插入元素
		}
	}
}

func main() {
	arr := []int{9, 8, 7, 6, 5, 4, 3, 2, 1}
	shellSort(arr)
	fmt.Println("Sorted array after Shell Sort:")
	for _, val := range arr {
		fmt.Print(val, " ")
	}