排序算法之希尔

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。
希尔排序是非稳定排序算法。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，算法便终止。

Swift代码

func shellSort(numbers: inout [Int]) {
    var gap = numbers.count / 2
    while gap > 0 {
        for i in gap ..< numbers.count {
            //index 从0到gap
            var index = i - gap
            while index >= 0 {
                //numbers[index]为gap前部分内容，numbers[index+gap]为gap后部分内容
                //互相比对，前部分数大于后部分数，则交换
                if numbers[index] > numbers[index+gap] {
                    (numbers[index], numbers[index+gap]) = (numbers[index+gap], numbers[index])
                }
                index -= gap
            }
        }
        gap = gap / 2
    }
}

var array = [3,2,5,1,7,9,8]
shellSort(numbers: &array)
//打印结果[1, 2, 3, 5, 7, 8, 9]