归并排序算法讲解及快速代码实现

归并排序

算法讲解

归并排序使用了分而治之的思想）（分而治之的思想。顾名思义，就是将一个大的将问题分解成类似的小问题，逐一解决。在实现归并排序算法时，首先将数组逐渐划分为最小的组成部分（通常是1个元素），然后反向逐步合并。

用图像来了解融合算法的实现过程：

上图中的虚线箭头代表分裂过程；实线代表合并过程，仔细观察可以看到‘分裂和合并的操作不断重复’ ，这里我们可以使用递归来操作（这里两个数组中的元素通常是相同的）变成一个全序数组。

实现合并操作的步骤是：

• 创建一个新的空数组，用于存储合并后的有序数组。
• 两个传入数组从索引 0 开始两两比较。较小的元素放入新创建的空数组中，索引 + 1；较大的元素不进行操作，索引保持不变，然后继续两两比较。直到索引移动到末尾。
• 某些情况下，如果两个数组的长度不一致，则必须将数组中剩余的元素放入新数组中。

代码实现

我们看一下归并排序算法的代码实现：

func _merge(leftPile: [Int], rightPile: [Int]) -> [Int] {
    
    var leftIndex = 0   //left pile index, start from 0
    var rightIndex = 0  //right pile index, start from 0
    
    var sortedPile = [Int]() //sorted pile, empty in the first place
    
    while leftIndex < leftPile.count && rightIndex < rightPile.count {
        
        //append the smaller value into sortedPile
        if leftPile[leftIndex] < rightPile[rightIndex] {
            
            sortedPile.append(leftPile[leftIndex])
            leftIndex += 1
            
        } else if leftPile[leftIndex] > rightPile[rightIndex] {
            
            sortedPile.append(rightPile[rightIndex])
            rightIndex += 1
            
        } else {
            
            //same value, append both of them and move the corresponding index
            sortedPile.append(leftPile[leftIndex])
            leftIndex += 1
            sortedPile.append(rightPile[rightIndex])
            rightIndex += 1
        }
    }
    
    
    //left pile is not empty
    while leftIndex < leftPile.count {
        sortedPile.append(leftPile[leftIndex])
        leftIndex += 1
    }
    
    //right pile is not empty
    while rightIndex < rightPile.count {
        sortedPile.append(rightPile[rightIndex])
        rightIndex += 1
    }
    

    return sortedPile
}
复制代码

因为该函数是归并排序函数中调用的函数，所以函数名前加下划线。只是为了区分，没有必要。

从上面的代码我们可以看到合并的实现逻辑：

• 创建一个新的空数组，并将传入的两个数组的索引初始化为0
• 比较两者索引处的值数组和 Pairs，并放入较小的一个 创建一个新数组并向其添加索引+1。
• 最后检查是否还有元素，如果有则添加到新数组中。

现在我们了解了合并算法，让我们看看分裂算法。分裂算法使用递归：

func mergeSort(_ array: [Int]) -> [Int] {
    
    guard array.count > 1 else { return array }
    
    let middleIndex = array.count / 2
    let leftArray = mergeSort(Array(array[0..<middleIndex]))             // recursively split left part of original array
    let rightArray = mergeSort(Array(array[middleIndex..<array.count]))  // recursively split right part of original array

    return _merge(leftPile: leftArray, rightPile: rightArray)             // merge left part and right part
}
复制代码

我们可以看到mergeSort调用自身，其递归终止条件为！(Array.count >1)如果数组元素个数达到则返回= 1，触发调用堆栈的弹出。

从这个递归函数的实现中我们可以看出，它的作用就是根据中心存储对输入数组进行连续划分。在递归终止条件之后，如果数组元素> 1，则拆分将继续。只有当递归完成并且堆栈开始弹出时，以下合并函数才会开始实际执行。即分裂完成后才开始融合，这与上面作者介绍的融合算法的实现过程是一致的。

上面这段话一定要反复理解。

为了更形象地体现归并排序的实现过程，可以在归并函数中添加日志（_merge）来验证上面的说法：

func _merge(leftPile: [Int], rightPile: [Int]) -> [Int] {
    
    print("\nmerge left pile:\(leftPile)  |  right pile:\(rightPile)")
    
    ...
    
    print("sorted pile：\(sortedPile)")
    return sortedPile
}
复制代码

并且为了上面的方便对比图，初始数组可以取图中的[3,5,9,2,7,4,8,0]。运行一下看看效果：

original array:
[3, 5, 9, 2, 7, 4, 8, 0]

merge sort...

merge left pile:[3]  |  right pile:[5]
sorted pile：[3, 5]

merge left pile:[9]  |  right pile:[2]
sorted pile：[2, 9]

merge left pile:[3, 5]  |  right pile:[2, 9]
sorted pile：[2, 3, 5, 9]

merge left pile:[7]  |  right pile:[4]
sorted pile：[4, 7]

merge left pile:[8]  |  right pile:[0]
sorted pile：[0, 8]

merge left pile:[4, 7]  |  right pile:[0, 8]
sorted pile：[0, 4, 7, 8]

merge left pile:[2, 3, 5, 9]  |  right pile:[0, 4, 7, 8]
sorted pile：[0, 2, 3, 4, 5, 7, 8, 9]
复制代码

我们可以看到，拆分合并操作是先处理原数组的左边部分，然后再处理原数组的右边部分。这是为什么？

让我们看看函数一开始是如何被调用的：

我们首先调用该函数：

func mergeSort(_ array: [Int]) -> [Int] {
    
    guard array.count > 1 else { return array }
    
    let middleIndex = array.count / 2
    let leftArray = mergeSort(Array(array[0..<middleIndex]))             //1 
    let rightArray = mergeSort(Array(array[middleIndex..<array.count]))  //2

    return _merge(leftPile: leftArray, rightPile: rightArray)            //3
}
复制代码

递归从 //1 行开始。此时数组为原数组，元素个数为8，并且当调用mergeSort时，原数组被分成两半，为4。且4>1，不满足递归终止条件，且递归继续，直到满足终止条件（[3]），然后递归重新开始。假设此时数组的左半部分最初被分割，因此左半部分的分割逐渐合并，最终得到[2,3,5,9]。

同样，我们回到原来分割数组的右半部分（上面代码片段中的//2），按照左边测试的方式进行分割合并，得到右边的合并结果部分：[0,4,7,8。

此时递归调用栈中只有一个MergeSort函数。 mergeSort会执行最终的合并（上面代码段中的//3），并调用函数_merge得到最终结果：[0, 2, 3, 4, 5, 7, 8 ，9]。

关于融合排序的性能：因为它使用了分治和递归，并且使用了不同的内存空间，所以它的性能比上面介绍的所有排序都要高，但前提是初始元素量不小。

我们可以比较选择排序和归并排序：初始数组是一个长度为500、最大值为500的随机数组：

selection sort...
selection sort time duration : 12.7s

merge sort...
merge sort time duration : 5.21s
复制代码

可以看到归并排序算法优于选择排序。

现在我们知道归并排序使用除法和思想，并使用递归来高效地对数组进行排序。