希尔排序的大体步骤

demo 具体代码

func sort(items: Array<Int>) -> Array<Int> {
    
    var list = items
    var step: Int = list.count / 2
    while step > 0 {
        print("步长为\(step)的插入排序开始:")
        for i in 0..<list.count {
            var j = i + step
            while j >= step && j < list.count {
                if list[j] < list[j - step]  {
                    let temp = list[j]
                    list[j] = list[j-step]
                    list[j-step] = temp
                    j = j - step  // 结束while循环
                } else {
                    break
                }
            }
        }
        print("步长为\(step)的插入排序结束")
        print("本轮排序结果为:\(list)\n")
        step = step / 2     //缩小步长
    }
    return list
}

示例

希尔排序 [2, 8, 9, 3, 5]
步长为2的插入排序开始
步长为2的插入排序结束
本轮排序结果为[2, 3, 5, 8, 9]

步长为1的插入排序开始
步长为1的插入排序结束
本轮排序结果为[2, 3, 5, 8, 9]

希尔排序:时间复杂度—-O(n^(3/2))

反过来理解:步长为1是相邻两个数依次两两比较,步长为2是隔一个数依次进行的两两比较