阅读 16

排序算法之插入排序

###插入排序

  • 插入排序的执行流程
    • 将序列分成有序(头部)和无序(尾部)两部分
    • 从头开始以此扫描每个元素,找到该元素在头部有序序列中合适的位置插入
for begin in 1..<array.count {
            var current = begin
            while current > 0 && array[current] < array[current - 1] {
                let temp = array[current]
                array[current] = array[current - 1]
                array[current - 1] = temp
                current -= 1
            }
        }
复制代码
  • 插入排序的优化
    • 将交换目标元素和其余元素的操作改为挪动部分有序元素,后一次插入操作将目标元素插入到合适位置
for begin in 1..<array.count {
            var current = begin
            let element = array[current]
            while current > 0 && element < array[current - 1]{
                array[current] = array[current - 1]
                current -= 1
            }
            array[current] = element
        }
复制代码
  • 使用二分查找寻找目标元素应插入的位置
    /// 将source位置的元素插入到dest的位置
    /// - Parameters:
    ///   - source: <#source description#>
    ///   - dest: <#dest description#>
    private func insert(source:Int,dest:Int){
        let element = array[source]
        var i = source
        while i > dest {
            array[i] = array[i - 1]
            i -= 1
        }
        array[dest] = element
    }
    
    /// 二分查找元素应插入的位置  范围是[0,target)
    /// - Parameters:
    ///   - array: 数组
    ///   - target: 目标元素索引
    /// - Returns: 元素插入的下标
    private func search(target:Int) -> Int{
        guard array.count > 0 else {
            return 0
        }
        var begin = 0
        var end = target
        
        while begin < end {
            let mid = (begin + end) >> 1
            if array[target] < array[mid]{
                end = mid
            }else {
                begin = mid + 1
            }
        }
        return begin
    }

复制代码
  • 插入排序的稳定性

    • 属于稳定的排序算法
  • 插入排序的时间复杂度和空间复杂度

    • 时间复杂度
      • 需要遍历两轮,时间复杂度为O(n^2)
      • 使用二分查找后减少了比较次数,但时间复杂度仍未O(n^2)
    • 空间复杂度
      • O(1)

      • 属于原地算法

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