希尔排序

def shell_sort(alist):
    # 希尔排序：核心是插入排序
    n = len(alist)
    # 折半：取整数解，防止小数:n=9,step=4
    step = n // 2
    i = 1
    
    # 步长变化到0之前即1，插入算法执行的次数 
    while step > 0:
        # 插入算法：与普通插入算法的区别就是步长step
        for j in range(step, n):
            # j = gap, gap+1, ..., n-1
            i = j
            while i > 0:
                if alist[i] < alist[i-step]:
                    # 比较的两个数下标相差为步长step
                    alist[i], alist[i-step] = alist[i-step], alist[i]
                    i -= step
                else:
                    break
        # 一个for循环结束则缩短步长step
        step //= 2
        
    return alist

package main

import "fmt"

// shell排序
func shellSort(numberArray []int) []int{   // 定义函数、参数和返回值
	n := len(numberArray)
	step := n / 2   // 设定步长step

	for step > 0{   //   进行排序的条件：步长大于0
		for j := step; j < n; j++{  // 控制外层循环：从中间的step位置开始，往后进行比较
			// j = [step, step+1, ..., n-1]
			i := j
			for i > 0{
				if numberArray[i] > numberArray[i-step]{   // 进行比较和交换的两个数之的索引相差为step
					numberArray[i], numberArray[i-step] = numberArray[i-step], numberArray[i]
					i -= step   // 每交换一次，下标左移step；直接插入排序中是左移一个位置
				}else {
					break
				}
			}
		}
		step = step / 2   // 执行一次，步长要缩短一半
	}
	return numberArray
}


func main(){
	shellArray := []int{1,8,9,7,3,5,2,6,4}
	fmt.Println("Before:", shellArray)
	shellSort(shellArray)
	fmt.Println("After:", shellArray)
}