数组-归并排序

采用归并排序方式对数组进行排序

归并排序百科:归并排序(Merge Sort),是建立子啊归并操作上的一种有效、稳定的排序算法,该算法是采用分治法(Divide and Conque)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并.

摘一个示例做个说明.
示例 1：
输入: [0,5,9,3,12,7]
输出: [0,3,5,7,9,12]

算法原理:

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针超出序列尾.将另一序列剩下的所有元素直接复制到合并序列尾
5. 算法演示 归并排序演示.gif

算法分析:

归并排序的比较次数小于快速排序的比较次数，移动次数一般多于快速排序的移动次数。

1. 时间复杂度
   最好: O(nlog₂n)
   平均: O(nlog₂n)
   最差: O(nlog₂n)
   综上,归并排序总的平均时间复杂度为O(nlog₂n).
2. 空间复杂度
   O(n)
3. 算法稳定性
   归并排序是一种稳定排序算法.

代码实现-Swift版本:

func mergeSort(_ num: [Int]) -> [Int] {
    // 跳出递归操作
    guard num.count > 1 else {
        return num
    }
    let middleIndex = num.count / 2
    // 不断拆分左数组
    let leftArray = mergeSort(Array(num[0 ..< middleIndex]))
    // 不断拆分右数组
    let rightArray = mergeSort(Array(num[middleIndex ..< num.count]))
    // 合并排序后的数组
    return merge(leftArray,rightArray)
}
// 数组合并
func merge(_ leftNum: [Int],_ rightNum: [Int]) -> [Int]{
    
    var leftIndex = 0
    var rightIndex = 0
    var result = [Int]()
    
    while leftIndex < leftNum.count && rightIndex < rightNum.count {
        if leftNum[leftIndex] < rightNum[rightIndex] {
            result.append(leftNum[leftIndex])
            leftIndex += 1
        }else if leftNum[leftIndex] > rightNum[rightIndex] {
            result.append(rightNum[rightIndex])
            rightIndex += 1
        }else{
            result.append(leftNum[leftIndex])
            leftIndex += 1
            result.append(rightNum[rightIndex])
            rightIndex += 1
        }
    }
    
    while leftIndex < leftNum.count {
        result.append(leftNum[leftIndex])
        leftIndex += 1
    }
    
    while rightIndex < rightNum.count {
        result.append(rightNum[rightIndex])
        rightIndex += 1
    }
    
    return result
}

测试用例:

var nums = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

参考:

• 归并排序百科
• 一像素

考察要点:

• 数组
• 排序