希尔排序

时间复杂度：O(n log n)

• 最好：O(n log^2 n)
• 最坏：O(n log^2 n)

空间复杂度：O(1)

• 只需要一个额外空间用于数据交换

原理
希尔排序（Shell Sort）是一个不稳定排序，它的基本思想是：
先取定一个小于序列元素个数的整数作为增量，把序列的全部元素分成增量个组，所有相互之间距离为增量整数倍的元素放在同一个组中，在各组内进行直接插入排序。

实现

1. 将一个数据序列按照增量进行分组。
2. 将各个分组的数据进行直接插入排序。
3. 更新增量，同时增量大于零在进行分组并排序。

// 希尔排序，降序不稳定排序
func ShellSort(slice []int) []int {
    if len(slice) < 2 {
        return slice
    }
    for gap := len(slice) >> 1; gap > 0; gap >>= 1 {
        for i := gap; i < len(slice); i++ {
            for j := i; j >= gap && slice[j] > slice[j-gap]; j -= gap {
                slice[j], slice[j-gap] = slice[j-gap], slice[j]
            }
        }
    }
    return slice
}