阅读 13

排序算法笔记之归并排序

###归并排序

  • 归并排序的执行流程
    1. 循环执行:将当前序列平均分割成2个子序列,直至序列中只包含一个元素
    2. 循环执行:将2个子序列合并成一个有序序列,直到最终合并成一个序列
    归并排序图示:

归并.png

将序列平均分割成2个子序列:

    /// 分割数组 范围 [begin,end)
    /// - Parameters:
    ///   - begin: <#begin description#>
    ///   - end: <#end description#>
    private func divide(begin:Int,end:Int){
        guard end - begin > 1 else {
            return
        }
        let mid = (begin + end) >> 1
        divide(begin: begin, end: mid)
        divide(begin: mid, end: end)
        merge(begin: begin, mid: mid, end: end)
    }
    
复制代码

将2个子序列合并成一个有序序列:

/// 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
    /// - Parameters:
    ///   - begin: <#begin description#>
    ///   - mid: <#mid description#>
    ///   - end: <#end description#>
    private func merge(begin:Int,mid:Int,end:Int){
        /// 分割后左边数组的拷贝
        // 2,3,5   (2 | 3,4)
        var leftArray:[E] = []
        /// 指向左数组当前需要判断大小的指针的索引
        var li = 0
        /// 指向右数组当前需要判断大小的指针的索引
        var ri = mid
        /// 左数组结束的索引
        let le = mid - begin
        /// 右数组结束的索引
        let re = end
        /// 指向当前数组需要覆盖的索引
        var ai = begin
        
        /// 将左边数组拷贝
        for i in li..<le {
            leftArray.append(self.array[begin + i])
        }
        /**
            合并要注意的几种情况:1.左边先结束,无需做任何操作,即为有序数组
                              2.右边先结束,将左边未转移的有序数组按顺序替换原数组元素
            比较ri和li指向的元素大小,当右侧大ai += 1 ,ri += 1 左侧大ai += 1,li += 1
            ri < re : 判断右边数组已经结束,全部使用左边有序数组替换
         */
        while li < le {
            if ri < re && self.array[ri] < leftArray[li] {
                self.array[ai] = self.array[ri]
                ai += 1
                ri += 1
            }else{
                self.array[ai] = leftArray[li]
                ai += 1
                li += 1
            }
        }
    }
复制代码
  • 归并排序的稳定性
    • 属于稳定排序
  • 归并排序的时间复杂度和空间复杂度
    • 时间复杂度
      • O(nlogn)
    • 空间复杂度
      • O(n/2 + logn) == O(n)

      • n/2用于临时存放左侧数组,logn因为递归调用

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