排序算法-归并排序

归并排序（升序为例）

• 思路：
  • 1. 将当前序列平均分割成2q个子序列，直到不能再分割（即序列中只剩下1个元素）
  • 2. 再不断的将2个子序列合并成一个有序序列，直到最终合成1个序列

class MergeSort {
    
    var array = [5, 7, 2, 8, 9, 4, 7, 3, 2]
    var leftArray: [Int]
    init() {
        leftArray = Array(repeating: 0, count: array.count >> 1)
    }
    func sort() {
        sort(begin: 0, end: array.count)
    }
    // [begin, end) 区间内
    private func sort(begin: Int, end: Int) {
        if end - begin < 2 { return }
        let mid = (end + begin) >> 1
        sort(begin: begin, end: mid)
        sort(begin: mid, end: end)
        
        merge(begin: begin, mid: mid, end: end)
    }
    /**
     因为merge的两个数组在同一个数组中，且是相临的
     为了方便merge操作，将其中1组序列备份出来，如[begin, mid)
     */
    private func merge(begin: Int, mid: Int, end: Int) {
        // leftIndex: 左边序列的索引开始， leftEnd：左边索引结束（基于分割的左边序列）
        var leftIndex = 0, leftEnd = mid - begin
        // rightIndex: 右边序列的索引开始， rightEnd：右边索引结束
        var rightIndex = mid, rightEnd = end
        // array 的索引
        var arrayIndex = begin
        for i in leftIndex ..< leftEnd  { // 拷贝左边数组到 leftArray
            leftArray[i] = array[begin + i]
        }
        while leftIndex < leftEnd { // 因为是将左边数组拷贝出来，如果左边的先merge完了，右边都是较大的，本身就在右边，无需再移动
            if rightIndex < rightEnd, array[rightIndex] < leftArray[leftIndex] {
                array[arrayIndex] = array[rightIndex] // 拷贝右边数组到 array
                arrayIndex += 1
                rightIndex += 1
            } else {
                array[arrayIndex] = leftArray[leftIndex] // 拷贝左边数组到 array
                arrayIndex += 1
                leftIndex += 1
            }
        }
    }
}

* 最好、最坏、平均时间复杂度：O(nlogn)，因为每次分割都是平分

* 空间复杂度： O(n)

* 稳定性：稳定排序