swift算法 - 归并算法

归并算法是一种相对高效的算法，它的最好、最坏、和平均时间复杂度都是O(n log n)。
归并算法的核心思想是分治思想：将一个大问题拆分为多个小问题，并通过解决众多小问题来最终解决大问题。我们可以将归并算法拆分为先拆后合并。

算法步骤

1、给定一个待排序的数组
2、将数组对半拆分为两个数组得到两个待排序的小数组
3、继续拆分小数组知道不能在拆分，最终我们得到n个只有一个元素的数组
4、开始合并小数组：将相邻的两个数组元素按照顺序（从大到小或者从小到达）合并为一个新数组。
5、继续合并，直到最后得到一个排序的数组

举例说明

拆分

假设我们有个带排序的数组为[2, 1, 5, 4, 9].现在我们的目标是将该数组拆分到不能再拆
1、将数组拆分为2个数组：[2, 1] 和 [5, 4, 9]
2、继续拆分数组为[2], [1], [5], [4, 9]
3、继续拆分数组为[2], [1], [5], [4], [9]
这时数组不能再拆了，拆分就结束了

合并

现在我们对数组进行排序的同时进行合并
1、将[2], [1]合并为[1, 2]，将[5], [4]合并为[4, 5]
2、将[1, 2]和[4, 5] 合并为[1, 2, 4, 5]
3、最后将[1, 2, 4, 5]和[9]合并为[1, 2, 4, 5, 9].
现在我们就得到最终的排序结果了

代码

采用递归方法对数组进行拆分

func mergeSort(array: [Int]) -> [Int] {
  guard array.count > 1 else { return array }    // 1

  let middleIndex = array.count / 2              // 2

  let leftArray = mergeSort(Array(array[0..<middleIndex]))             // 3

  let rightArray = mergeSort(Array(array[middleIndex..<array.count]))  // 4

  return merge(leftPile: leftArray, rightPile: rightArray)             // 5
}

func merge(leftPile leftPile: [Int], rightPile: [Int]) -> [Int] {
  // 1
  var leftIndex = 0
  var rightIndex = 0

  // 2 
  var orderedPile = [Int]()

  // 3
  while leftIndex < leftPile.count && rightIndex < rightPile.count {
    if leftPile[leftIndex] < rightPile[rightIndex] {
      orderedPile.append(leftPile[leftIndex])
      leftIndex += 1
    } else if leftPile[leftIndex] > rightPile[rightIndex] {
      orderedPile.append(rightPile[rightIndex])
      rightIndex += 1
    } else {
      orderedPile.append(leftPile[leftIndex])
      leftIndex += 1
      orderedPile.append(rightPile[rightIndex])
      rightIndex += 1
    }
  }

  // 4
  while leftIndex < leftPile.count {
    orderedPile.append(leftPile[leftIndex])
    leftIndex += 1
  }

  while rightIndex < rightPile.count {
    orderedPile.append(rightPile[rightIndex])
    rightIndex += 1
  }

  return orderedPile
}

我们来看下排序的过程，假设有如下两个数组

leftPile       rightPile       orderedPile
[ 1, 7, 8 ]    [ 3, 6, 9 ]     [ ]
  l              r

先将左边第一个元素与右边第一个元素对比，1 < 3，将1移入orderedPile，同时将左边索引l向右移动

leftPile       rightPile       orderedPile
[ 1, 7, 8 ]    [ 3, 6, 9 ]     [ 1 ]
  -->l

重复上述步骤发现3 < 7，将3移入orderedPile，同时将右边所以向右移动

leftPile       rightPile       orderedPile
[ 1, 7, 8 ]    [ 3, 6, 9 ]     [ 1, 3 ]
     l           -->r

重复上述步骤将所有元素都移动到orderedPile

leftPile       rightPile       orderedPile
[ 1, 7, 8 ]    [ 3, 6, 9 ]     [ 1, 3, 6 ]
     l              -->r

leftPile       rightPile       orderedPile
[ 1, 7, 8 ]    [ 3, 6, 9 ]     [ 1, 3, 6, 7 ]
     -->l              r

leftPile       rightPile       orderedPile
[ 1, 7, 8 ]    [ 3, 6, 9 ]     [ 1, 3, 6, 7, 8 ]
        -->l           r

现在我们就得到最终的排序结果[ 1, 3, 6, 7, 8, 9 ].

注意：以上的比较大小的算法很简单，但是是建立在左右两个数组都是已经是排序后的基础上的。