归并排序(Merge Sort)

2020-07-19  本文已影响0人  Bel李玉

归并排序是最高效的排序算法之一。该排序算法的时间复杂度是O(log n),归并排序是由分割和合并组成的。将一个比较大的问题分割成若干容易解决的小问题,然后进行合并,得到一个最终的结果。归并排序的口诀就是先分割,后合并。

举个例子,假定你手中有如下一摞卡牌:


mergeSort1.png

排序算法的排序过程大致是这样的:
1,首先,将这一摞牌分成两半,这样就得到了两摞无序的卡牌。


mergeSort2.png
1,现在继续对每摞卡牌进行分割,直到不能在分割为止,到最后在每摞卡牌中,就只存在一张卡牌。
mergeSort3.png

1,最后,以和分割相反的顺序,将每一摞卡牌合并。在每一次合并的过程中,将数据按照规则进行排序。由于每一小摞的卡牌都已经有序,在合并的时候会比较容易些。


mergeSort4.png

实现

分割

首先,先将数组分成两半:

public func mergeSort<Element>(_ array: [Element])
    -> [Element] where Element: Comparable {
  let middle = array.count / 2
  let left = Array(array[..<middle])
  let right = Array(array[middle...])
  // ... more to come
}

将数组分割一次远远不够,需要递归调用分割函数,直到不能在分割为止。这样的话,每一个子部分都只包含一个元素。按照这种思路,我们将 mergeSort 更新至如下所示:

public func mergeSort<Element>(_ array: [Element])
    -> [Element] where Element: Comparable {
  // 1
  guard array.count > 1 else {
    return array
  }
  let middle = array.count / 2
  // 2
  let left = mergeSort(Array(array[..<middle]))
  let right = mergeSort(Array(array[middle...]))
  // ... more to come
}

这里有两个变动点:
1,对函数进行了递归调用,在数组中有且只有一个元素时,停止递归调用。
2,对原数组的左右子数组都调用 mergeSort

如上代码在能通过编译之前,仍然还有很多事情去做。现在已经完成了数组分割部分,是时候去关注于合并了。

合并

合并左右子数组是该算法的最后一步。为了更算法更明了一些,单独创建一个 merge 方法。

merge 方法的职责仅仅是 将两个将两个有序的数组合并成一个有序的数组。在 mergeSort 函数中,增加以下方法:

private func merge<Element>(_ left: [Element], _ right: [Element])
    -> [Element] where Element: Comparable {
  // 1
  var leftIndex = 0
  var rightIndex = 0
  // 2
  var result: [Element] = []
  // 3
  while leftIndex < left.count && rightIndex < right.count {
    let leftElement = left[leftIndex]
    let rightElement = right[rightIndex]
    // 4
    if leftElement < rightElement {
      result.append(leftElement)
      leftIndex += 1
    } else if leftElement > rightElement {
      result.append(rightElement)
      rightIndex += 1
    } else {
      result.append(leftElement)
      leftIndex += 1
      result.append(rightElement)
      rightIndex += 1
    }
  }
  // 5
  if leftIndex < left.count {
    result.append(contentsOf: left[leftIndex...])
  }
  if rightIndex < right.count {
    result.append(contentsOf: right[rightIndex...])
  }
  return result
}

最后附上本文的相关代码DataAndAlgorim

参考链接《Data Structures & Algorithms in Swift》

上一篇 下一篇

猜你喜欢

热点阅读