阅读 13

排序算法笔记之希尔排序

###希尔排序

  • 希尔排序的执行流程
    1. 把序列看作一个矩阵,分成m列,逐列排序

      • m从某个整数逐渐减为1
      • 当m为1时,整个序列为有序序列
    2. 矩阵的烈属取决于步长序列

      • 不同的步长序列执行效率不同
      • 希尔本人给的步长序列是n/2^k
      • 目前已知的最好的序列是[1,5,19,41,109....]
    3. 因为每轮矩阵排序后,逆序对的数量在不断减少,以此增加排序效率

希尔本人给出的步长序列:

/// 定义希尔排序的步长序列(希尔本人给出的步长序列:n/2^k)
    /// - Returns: 返回步长序列
    private func shellStepSequence() -> [Int]{
        var stepSequence = [Int]()
        var count = array.count >> 1
        while count > 0{
            stepSequence.append(count)
            count = count >> 1
        }
        return stepSequence
    }
复制代码

目前为止最好的步长序列:

/// 定义希尔排序的步长序列(目前为止最好的步长序列:1,5,19,41,109...)
    /// - Returns: 返回步长序列
    private func sedgewickStepSequence() -> [Int]{
        var stepSequence = [Int]()
        var k = 0, step = 0
        while true {
            if k % 2 == 0 {
                let p = Int(pow(2.0, Double(k>>1)))
                step = 1 + 9 * (p * p - p)
            }else{
                let p1 = Int(pow(2.0, Double((k - 1) >> 1)))
                let p2 = Int(pow(2.0, Double((k + 1) >> 1)))
                step = 1 + 8 * p1 * p2 - 6 * p2
            }
            if step >= array.count {
                break
            }
            stepSequence.insert(step, at: 0)
            k += 1
        }
        return stepSequence
    }
复制代码
  • 希尔排序的图示:

希尔排序.png - 假设元素在第col列,row行,步长是step - 那么这个元素在数组中的索引是col+rowstep - 如图9,在第2列第0行,索引就是2+05 = 2 - 如图4,在第2列第1行,索引就是2+1*5 = 7

希尔排序的实现:

    /// 希尔排序
    /// - Parameter step: 步长
    private func shellSort(step:Int){
        for col in 0..<step {
            // 每列第一个元素
            var begin = col + step
            while begin < array.count {
                var cur = begin
                // 当前元素与矩阵前一个元素比较
                while cur > col && array[cur] < array[cur - step] {
                    let temp = array[cur]
                    array[cur] = array[cur - step]
                    array[cur - step] = temp
                    cur -= step
                }
                begin += step
            }
            
        }
    }
复制代码
  • 希尔排序的优化

    • 构建堆来选择最大值
    • 即堆排序
  • 希尔排序的稳定性

    • 选择排序属于不稳定的排序
  • 希尔排序的时间复杂度和空间复杂度

    • 时间复杂度 取决于步长序列
    • 空间复杂度
      • O(1)
      • 属于原地算法

源码及单元测试:https://github.com/yukifeng/suanfaStudy