算法：希尔排序

算法演进

首次按数组的长度除以2为分组步长，若步长大于1，则再次分组，以首次得到的步长再除以2为步长，以此类推分组，直至步长为1。

以[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]为例。

第一步

分组步长：10/2=5 ，以5为步长递增分组得到：[8,3] [9,5] [1,4] [7,6] [2,0]，分组后从第5位元素开始按步长为5递减进行排序交换得到[3 5 1 6 0 8 9 4 7 2]。

第二步

分组步长：5/2=2 ，以2为步长递增分组得到：[3,1,0,9,7] [5,6,8,4,2]，分组后从第2位元素开始按步长为2递减进行排序交换得到[0 2 1 4 3 5 7 6 9 8]。

第三步

分组步长：2/2=1 ，以1为步长递增分组得到：[0 2 1 4 3 5 7 6 9 8]，分组后从第1位元素开始按步长为1递减进行排序交换得到[0 1 2 3 4 5 6 7 8 9]。

// 交换法
func ShellSortExchangeEvolution() {
    arr := []int{8, 9, 1, 7, 2, 3, 5, 4, 6, 0}
    log.Println(arr)
    //step := 5 // len(arr)/2
    for i := 5; i < len(arr); i++ {
        log.Println("step=5, iiiiiiiiii=", i, arr)
        for j := i - 5; j >= 0; j -= 5 {
            if arr[j] > arr[j+5] {
                temp := arr[j]
                arr[j] = arr[j+5]
                arr[j+5] = temp
            }
            log.Println("step=5, j=", j, arr)
        }
    }

    log.Println(arr)

    for i := 2; i < len(arr); i++ {
        /*if arr[i-2] > arr[i] {
            temp := arr[i-2]
            arr[i-2] = arr[i]
            arr[i] = temp
        }*/
        log.Println("step=2, iiiiiiiiii=", i, arr)
        for j := i - 2; j >= 0; j -= 2 {
            if arr[j] > arr[j+2] {
                temp := arr[j]
                arr[j] = arr[j+2]
                arr[j+2] = temp
            }
            log.Println("step=2, j=", j, arr)
        }
    }

    log.Println(arr)

    for i := 1; i < len(arr); i++ {

        log.Println("step=1, iiiiiiiiii=", i, arr)
        for j := i - 1; j >= 0; j -= 1 {
            if arr[j] > arr[j+1] {
                temp := arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = temp
            }
            log.Println("step=1, j=", j, arr)
        }
    }

    log.Println(arr)
}

希尔排序交换法代码

func Exchange() {
    arr := []int{8, 9, 1, 7, 2, 3, 5, 4, 6, 0}

    for step := len(arr) / 2; step > 0; step /= 2 {
        for i := step; i < len(arr); i++ {
            for j := i - step; j >= 0; j -= step {
                if arr[j] > arr[j+step] {
                    temp := arr[j]
                    arr[j] = arr[j+step]
                    arr[j+step] = temp
                }
            }
        }
        log.Println(arr)
    }
}

希尔排序移位法代码

func main() {
    arr := []int{8, 9, 1, 7, 2, 3, 5, 4, 6, 0}

    for step := len(arr) / 2; step > 0; step /= 2 {
        for i := step; i < len(arr); i++ {
            j := i
            insertVal := arr[i]
            if arr[j] < arr[j-step] {
                for j-step >= 0 && insertVal < arr[j-step] {
                    arr[j] = arr[j-step]
                    j -= step
                }
                arr[j] = insertVal
            }
        }
        log.Println(arr)
    }
}