算法基础--递归入门の归并排序

本文只是自己的笔记，并不具备过多的指导意义。

为了理解很多都使用了递归，而不是自己通过while进行压栈处理。
代码的初衷是便于理解，网上大神优化过的代码很多，也不建议在项目中copy本文代码。

目录

• 归并排序
  • 如何合并两个有序数组
  • 使两端分别有序
  • 最外侧还有一个入口方法
  • 图解排序过程
• 递归时间复杂度的估算
  • master公式

---

归并排序

众所周知，分治策略中使用递归来求解问题分为三步走，分别为分解、解决和合并。

所以归并排序中心思想是通过二分的方式，将一个段数组拆分成左右两端，然后进行合并

• 如何合并两个有序数组

通过将最小值依次外排的方式，进行合并

1. 两个指针p1，p2指向两个数组的首位置，每次将较小的值外排进辅助数组并且右移指针。
2. 当一个指针越界后，将另一个剩余的元素放入辅助数组。
3. 最后的辅助数组将是一个有序数组。

/// 对一个数组的两个有序分段进行整合排序
///
/// - Parameters:
///   - arr: 数组
///   - left: 左侧起点
///   - mid: 中心点，左侧末尾
///   - right: 右侧末尾
func merge(arr: inout [Int] ,left: Int ,mid: Int ,right:Int) {
    
    var help : [Int] = [Int](repeating: 0, count: right-left+1) //辅助数组
    var p1 = left//左侧指针
    var p2 = mid+1 //右侧指针
    var i = 0 //容器指针位置
    
    while p1<=mid && p2<=right {
        if arr[p1] <= arr[p2] {//左侧指针位置小于等于右侧指针位置
            help[i] = arr[p1] //将左侧指针位置放入辅助数组
            p1 = p1+1 //左侧指针右移
        }else {//右侧指针大于左侧指针位置
            help[i] = arr[p2] //将右侧指针位置放入辅助数组
            p2 = p2+1 //左侧指针右移
        }
        i = i+1  //容器指针右移
    }
    
    //到这里，p1,p2之中已经有一个指针越界了
    //没有越界的那个，重复上面的操作写入辅助数组
    while p1<=mid {
        help[i] = arr[p1]
        p1 = p1+1
        i = i+1
    }
    while p2<=right {
        help[i] = arr[p2]
        p2 = p2+1
        i = i+1
    }
    //写入完毕，用辅助数组替换进原数组
    i = 0
    for index in left...right { //left,left+1...right-1,right
        arr[index] = help[i]
        i = i+1
    }
}

之所以先说这个，是因为这个方法是核心方法，并且写完滞后直接将可以测试。
测试通过之后，再去测试下面的递归方法可以更加准确的确定问题所在。

• 使两端分别有序

通过递归的方式，将长数组最终分解成有序的数组进行排序处理。

比如[4,2,6,1,9,7]

/// 在一个数组的某一段上进行排序
///
/// - Parameters:
///   - arr: 数组
///   - left: 左侧
///   - right: 右侧
func mergeProcess(arr: inout [Int] ,left: Int ,right:Int) {
    
    if left==right { //左右相等，说明这次要调整的只有一个数
        return
    }
    
    let mid = (left+right)/2 //取得中心点位置
    mergeProcess(arr: &arr, left: left, right: mid)//对左半边进行排序
    mergeProcess(arr: &arr, left: mid+1, right: right)//对右半边进行排序
    //此时左右两侧都已经排序完成
    merge(arr: &arr, left: left, mid: mid, right: right)//对左右两侧进行合并排序
}

• 最外侧还有一个入口方法

/// 归并排序
///
/// - Parameter arr: 数组
func mergeSort(arr: inout [Int]) {
    if arr.count<2 {
        return
    }
    mergeProcess(arr: &arr, left: 0, right: arr.count-1)
}

时间复杂度O(N * logN)，额外空间复杂度O(N)。

• 图解排序过程

网上还看到一个动图，结合上面的应该更容易理解了。

这个过程中，不管数组多长，最后都将被划分成2个单位长度的数组进行排序。
然后向上依次合并并且排序。

这也很好的体现出了分治或者递归的思想所在，将大样本划分成小样本并依次解决。

---

递归时间复杂度的估算

只说一种普遍的通用情况

• master公式

T(N) = A*T(N/B) + O(N^D)

当量本量为N的情况下，整个样本被划分成B样本量，共执行A次。
出去调用递归过程之外，剩下的部分的时间复杂度O(N^D)

1) log(b,a) > d -> 复杂度为O(N^log(b,a)) 
2) log(b,a) = d -> 复杂度为O(N^d * logN) 
3) log(b,a) < d -> 复杂度为O(N^d)

以归并排序为例:

func mergeProcess(arr: inout [Int] ,left: Int ,right:Int) {
    
    if left==right { //左右相等，说明这次要调整的只有一个数
        return
    }
    
    let mid = (left+right)/2 //取得中心点位置
    mergeProcess(arr: &arr, left: left, right: mid)//T(N/2)
    mergeProcess(arr: &arr, left: mid+1, right: right)//T(N/2)
  
    merge(arr: &arr, left: left, mid: mid, right: right)//O(N)
}

有T(N) = T(N/2) + T(N/2) + O(N) = 2T(N/2) + O(N)
中A = 2,B=2,D=1

带入master公式log(b,a) = 1,与d值相等。

于是归并排序的时间复杂度为O(N * logN)。

---

参考资料

【图解数据结构】 一组动画演示归并排序
左神牛课网算法课