希尔排序

希尔排序是对插入排序的改进，引入了一个增量，按照增量将数组分成多个组，每个组分别进行插入排序，直到增量为1，进行最后一次插入排序。

代码

struct Shell {
    
    // 希尔排序是对插入排序的改进
    static func sort(array: inout [Int]) {
        var h:Int = 1   // 增量
        while h < (array.count / 2 ) {
            h = 2 * h + 1
        }
        while h >= 1 {
            for i in (h..<array.count) {
                for j in stride(from: i, through: h, by: -h) {
                    let a = array[j - h]
                    let b = array[j]
                    let result = compare(a: a , b: b)
                    if result == true {
                        exchange(array: &array, aIndex: j-h, bIndex: j)
                    } else {
                        break
                    }
                }
            }
            h = h / 2
        }
        
    }
    
    /// 比较大小
    static func compare(a: Int, b: Int) -> Bool {
        if a > b {
            return true
        } else {
            return false
        }
    }
    
    /// 交换位置
    static func exchange( array: inout [Int], aIndex: Int, bIndex: Int) {
        let temp = array[aIndex]
        array[aIndex] = array[bIndex]
        array[bIndex] = temp
    }
    
}

比较希尔排序和插入排序会发现，当数据上万条后，希尔排序花费的时间要少很多。