golang 写个希尔排序

追风骚年 · · 491 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

希尔排序非常的牛，听说是第一个打破时间复杂度我 n² 的算法，通过一个区间不断缩小，由远及近，最终达到有序状态，也可以称为加强版的分组插入排序。

算法描述

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的
长度。

先回顾一下插入排序

func insertionSort(arr []int) {
    for i := 1; i < len(arr); i++ {
        for j := i; j > 0 && arr[j] < arr[j-1]; j-- {
            arr[j], arr[j-1] = arr[j-1], arr[j]
        }
    }
}

希尔排序的精髓在于增量的选择，教科书上一般都是不断除以 2，最后达到1，这样做的问题是，奇数位和偶数位的数字始终不能比较。增量选择也是这个排序的魅力所在，看多很多资料给到的是 3x+1为一个合适的分组状态，所以我们先选择 3x+1 ，更多分组可以参照参考文档。

func shellSort(arr []int) {
    h := 1
    for h < len(arr)/3 { 
        h = 3*h + 1
    }

    for h >= 1 {
        for i := h; i < len(arr); i++ {
            for j := i; j >= h && arr[j] < arr[j-h]; j -= h {
                arr[j], arr[j-h] = arr[j-h], arr[j]
            }
        }
        h /= 3
    }
}

希尔排序相对于插入排序来说，外层套了一个递减变量，
希尔排序的时间复杂度为 o(n^k) (k=1.3~2.0)，具体 1.3 怎么算出来的，很玄学没找到地方列出推导过程，2 是因为如果整体逆序的情况下的最差情况。