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

2018-9-10

归并排序

算法讲解

归并排序使用了算法思想里的分治思想（divide conquer）。顾名思义，就是将一个大问题，分成类似的小问题来逐个攻破。在归并排序的算法实现上，首先逐步将要排序的数组等分成最小的组成部分（通常是1各元素），然后再反过来逐步合并。

用一张图来体会一下归并算法的实现过程：

上图面的虚线箭头代表拆分的过程；实线代表合并的过程。仔细看可以发现，拆分和归并的操作都是重复进行的，在这里面我们可以使用递归来操作。

首先看一下归并的操作：

归并的操作就是把两个数组（在这里这两个数组的元素个数通常是一致的）合并成一个完全有序数组。

归并操作的实现步骤是：

新建一个空数组，该数组用于存放合并后的有序数组。
两个传入的数组从index 0 开始两两比较，较小的元素放在新建的空数组中，index + 1; 较大的元素不作操作，index 不变，然后继续两两比较。知道index移到末尾为止。
个别情况当两个数组长度不一致的情况下需要将数组里剩余的元素放在新建的数组中。

代码实现

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

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
}
复制代码

因为该函数是归并排序函数内部调用的函数，所以在函数名称的前面添加了下划线。仅仅是为了区分，并不是必须的。

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

新建空数组，初始化两个传入数组的index为0
两两比较两个数组index上的值，较小的放在新建数组里面并且index+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)内部添加log来验证上面的说法：

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
复制代码

可以看到归并排序的算法是优与选择排序的。

现在我们知道归并排序使用了分治思想而且使用了递归，能够高效地将数组排序。

THE END