Swift算法俱樂部

本文是對(duì) Swift Algorithm Club 翻譯的一篇文章。
Swift Algorithm Club是 raywenderlich.com網(wǎng)站出品的用Swift實(shí)現(xiàn)算法和數(shù)據(jù)結(jié)構(gòu)的開源項(xiàng)目镜廉，目前在GitHub上有18000+??娇唯，我初略統(tǒng)計(jì)了一下塔插，大概有一百左右個(gè)的算法和數(shù)據(jù)結(jié)構(gòu)想许，基本上常見的都包含了，是iOSer學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)不錯(cuò)的資源流纹。
??andyRon/swift-algorithm-club-cn是我對(duì)Swift Algorithm Club糜烹，邊學(xué)習(xí)邊翻譯的項(xiàng)目。由于能力有限漱凝，如發(fā)現(xiàn)錯(cuò)誤或翻譯不妥疮蹦，請(qǐng)指正，歡迎pull request碉哑。也歡迎有興趣、有時(shí)間的小伙伴一起參與翻譯和學(xué)習(xí)??亮蒋。當(dāng)然也歡迎加??扣典，??????????慎玖。
本文的翻譯原文和代碼可以查看??swift-algorithm-club-cn/Merge Sort

這個(gè)主題已經(jīng)有輔導(dǎo)文章

目標(biāo)：將數(shù)組從低到高（或從高到低）排序

歸并排序是1945年由John von Neumann發(fā)明的贮尖，是一種有效的算法，最佳趁怔、最差和平均時(shí)間復(fù)雜度都是O(n log n)湿硝。

歸并排序算法使用分而治之方法，即將一個(gè)大問題分解為較小的問題并解決它們润努。 歸并排序算法可分為 先拆分 和 后合并关斜。

假設(shè)您需要按正確的順序?qū)﹂L度為 n 的數(shù)組進(jìn)行排序。 歸并排序算法的工作原理如下：

• 將數(shù)字放在未排序的堆中铺浇。
• 將堆分成兩部分痢畜。 那么現(xiàn)在就有兩個(gè)未排序的數(shù)字堆。
• 繼續(xù)分裂兩個(gè)未排序的數(shù)字堆鳍侣，直到你不能分裂為止丁稀。 最后，你將擁有 n 個(gè)堆倚聚，每堆中有一個(gè)數(shù)字线衫。
• 通過順序配對(duì)，開始 合并 堆惑折。 在每次合并期間授账，將內(nèi)容按排序順序排列。 這很容易惨驶，因?yàn)槊總€(gè)單獨(dú)的堆已經(jīng)排序（譯注：單個(gè)數(shù)字沒有所謂的順序矗积，就是排好序的）。

例子

拆分

假設(shè)給你一個(gè)長度為n的未排序數(shù)組：[2,1,5,4,9]敞咧。 目標(biāo)是不斷拆分堆棘捣，直到你不能拆分為止。

首先，將數(shù)組分成兩半：[2,1]和[5,4,9]乍恐。 你能繼續(xù)拆分嗎评疗？ 是的你可以！

專注于左邊堆茵烈。 將[2,1]拆分為[2]和[1]百匆。 你能繼續(xù)拆分嗎？ 不能了呜投。檢查右邊的堆加匈。

將[5,4,9]拆分為[5]和[4,9]。 不出所料仑荐，[5]不能再拆分了雕拼，但是[4,9]可以分成[4]和[9]。

拆分最終結(jié)果為：[2]``[1]``[5]``[4]``[9]粘招。 請(qǐng)注意啥寇，每個(gè)堆只包含一個(gè)元素。

合并

您已經(jīng)拆分了數(shù)組洒扎，您現(xiàn)在應(yīng)該 合并并排序 拆分后的堆辑甜。 請(qǐng)記住，這個(gè)想法是解決許多小問題而不是一個(gè)大問題袍冷。 對(duì)于每次合并迭代磷醋，您必須關(guān)注將一堆與另一堆合并。

對(duì)于堆 [2] [1] [5] [4] [9]胡诗，第一次合并的結(jié)果是[1,2]和[4,5] 和[9]子檀。 由于[9]的位置落單，所以在合并過程中沒有堆與之合并了乃戈。

下一次將合并[1,2]和[4,5]褂痰。 結(jié)果[1,2,4,5]，再次由于[9]的位置落單不需要合并症虑。

只剩下兩堆[1,2,4,5]和[9]缩歪，合并后完成排序的數(shù)組為[1,2,4,5,9]。

自上而下的實(shí)施(遞歸法)

歸并排序的Swift實(shí)現(xiàn)：

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
}

代碼的逐步說明：

1. 如果數(shù)組為空或包含單個(gè)元素谍憔，則無法將其拆分為更小的部分匪蝙，返回?cái)?shù)組就行。

2. 找到中間索引习贫。

3. 使用上一步中的中間索引逛球，遞歸地分割數(shù)組的左側(cè)。

4. 此外苫昌，遞歸地分割數(shù)組的右側(cè)颤绕。

5. 最后，將所有值合并在一起，確保它始終排序奥务。

這兒是合并的算法：

func merge(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
}

這種方法可能看起來很可怕物独，但它非常簡單：

1. 在合并時(shí)，您需要兩個(gè)索引來跟蹤兩個(gè)數(shù)組的進(jìn)度氯葬。

2. 這是合并后的數(shù)組挡篓。 它現(xiàn)在是空的，但是你將在下面的步驟中通過添加其他數(shù)組中的元素構(gòu)建它帚称。

3. 這個(gè)while循環(huán)將比較左側(cè)和右側(cè)的元素官研，并將它們添加到orderedPile，同時(shí)確保結(jié)果保持有序闯睹。

4. 如果前一個(gè)while循環(huán)完成戏羽，則意味著leftPile或rightPile中的一個(gè)的內(nèi)容已經(jīng)完全合并到orderedPile中。此時(shí)瞻坝，您不再需要進(jìn)行比較蛛壳。只需依次添加剩下一個(gè)數(shù)組的其余內(nèi)容到orderedPile杏瞻。

merge()函數(shù)如何工作的例子所刀。假設(shè)我們有以兩個(gè)個(gè)堆：leftPile = [1,7,8]和rightPile = [3,6,9]。 請(qǐng)注意捞挥，這兩個(gè)堆都已單獨(dú)排序 -- 合并排序總是如此的浮创。 下面的步驟就將它們合并為一個(gè)更大的排好序的堆：

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

左側(cè)索引（此處表示為l）指向左側(cè)堆的第一個(gè)項(xiàng)目1。 右則索引r指向3砌函。 因此斩披，我們添加到orderedPile的第一項(xiàng)是1。 我們還將左側(cè)索引l移動(dòng)到下一個(gè)項(xiàng)讹俊。

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

現(xiàn)在l指向7但是r仍然處于3垦沉。 我們將最小的項(xiàng)3添加到有序堆中。 現(xiàn)在的情況是：

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

重復(fù)上面的過程仍劈。 在每一步中厕倍，我們從leftPile或rightPile中選擇最小的項(xiàng)，并將該項(xiàng)添加到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

現(xiàn)在贩疙，左堆中沒有更多物品了讹弯。 我們只需從右邊的堆中添加剩余的項(xiàng)目，我們就完成了这溅。 合并的堆是[1,3,6,7,8,9]组民。

請(qǐng)注意，此算法非常簡單：它從左向右移動(dòng)通過兩個(gè)堆悲靴，并在每個(gè)步驟選擇最小的項(xiàng)目臭胜。 這是有效的，因?yàn)槲覀儽ＷC每個(gè)堆都已經(jīng)排序。

譯注： 關(guān)于自上而下的執(zhí)行(遞歸法)的歸并排序庇楞，我找了一個(gè)比較形象的動(dòng)圖榜配，來源

遞歸的歸并排序

自下而上的實(shí)施(迭代)

到目前為止你看到的合并排序算法的實(shí)現(xiàn)被稱為“自上而下”的方法，因?yàn)樗紫葘?shù)組拆分成更小的堆然后合并它們吕晌。排序數(shù)組（而不是鏈表）時(shí)蛋褥，實(shí)際上可以跳過拆分步驟并立即開始合并各個(gè)數(shù)組元素。 這被稱為“自下而上”的方法睛驳。

下面是Swift中一個(gè)完整的自下而上的實(shí)現(xiàn)：

func mergeSortBottomUp<T>(_ a: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {
  let n = a.count

  var z = [a, a]      // 1
  var d = 0

  var width = 1
  while width < n {   // 2

    var i = 0
    while i < n {     // 3

      var j = i
      var l = i
      var r = i + width

      let lmax = min(l + width, n)
      let rmax = min(r + width, n)

      while l < lmax && r < rmax {                // 4
        if isOrderedBefore(z[d][l], z[d][r]) {
          z[1 - d][j] = z[d][l]
          l += 1
        } else {
          z[1 - d][j] = z[d][r]
          r += 1
        }
        j += 1
      }
      while l < lmax {
        z[1 - d][j] = z[d][l]
        j += 1
        l += 1
      }
      while r < rmax {
        z[1 - d][j] = z[d][r]
        j += 1
        r += 1
      }

      i += width*2
    }

    width *= 2
    d = 1 - d      // 5
  }
  return z[d]
}

它看起來比自上而下的版本更令人生畏烙心，但請(qǐng)注意主體包含與merge()相同的三個(gè)while循環(huán)。

值得注意的要點(diǎn)：

1. 歸并排序算法需要一個(gè)臨時(shí)工作數(shù)組乏沸，因?yàn)槟悴荒芎喜⒆笥叶巡⑼瑫r(shí)覆蓋它們的內(nèi)容淫茵。 因?yàn)闉槊總€(gè)合并分配一個(gè)新數(shù)組是浪費(fèi)，我們使用兩個(gè)工作數(shù)組蹬跃，我們將使用d的值在它們之間切換匙瘪，它是0或1。數(shù)組z[d]用于讀蝶缀，z[1 - d]用于寫丹喻。 這稱為 雙緩沖。

2. 從概念上講翁都，自下而上版本的工作方式與自上而下版本相同碍论。首先，它合并每個(gè)元素的小堆柄慰，然后它合并每個(gè)堆兩個(gè)元素鳍悠，然后每個(gè)堆成四個(gè)元素，依此類推坐搔。堆的大小由width給出藏研。 最初，width是1但是在每次循環(huán)迭代結(jié)束時(shí)概行，我們將它乘以2蠢挡，所以這個(gè)外循環(huán)確定要合并的堆的大小，并且要合并的子數(shù)組在每一步中變得更大占锯。

3. 內(nèi)循環(huán)穿過堆并將每對(duì)堆合并成一個(gè)較大的堆袒哥。 結(jié)果寫在z[1 - d]給出的數(shù)組中。

4. 這與自上而下版本的邏輯相同消略。 主要區(qū)別在于我們使用雙緩沖堡称，因此從z[d]讀取值并寫入z [1 - d]。它還使用isOrderedBefore函數(shù)來比較元素而不僅僅是<艺演，因此這種合并排序算法是通用的却紧，您可以使用它來對(duì)任何類型的對(duì)象進(jìn)行排序桐臊。

5. 此時(shí)，數(shù)組z[d]的大小width的堆已經(jīng)合并為數(shù)組z[1-d]中更大的大小width * 2晓殊。在這里断凶，我們交換活動(dòng)數(shù)組，以便在下一步中我們將從我們剛剛創(chuàng)建的新堆中讀取巫俺。

這個(gè)函數(shù)是通用的认烁，所以你可以使用它來對(duì)你想要的任何類型對(duì)象進(jìn)行排序，只要你提供一個(gè)正確的isOrderedBefore閉包來比較元素介汹。

怎么使用它的示例：

let array = [2, 1, 5, 4, 9]
mergeSortBottomUp(array, <)   // [1, 2, 4, 5, 9]

譯注：關(guān)于迭代的歸并排序却嗡，我找到一個(gè)圖來表示，來源

迭代的歸并排序

性能

歸并排序算法的速度取決于它需要排序的數(shù)組的大小嘹承。 數(shù)組越大窗价，它需要做的工作就越多。

初始數(shù)組是否已經(jīng)排序不會(huì)影響歸并排序算法的速度叹卷，因?yàn)闊o論元素的初始順序如何撼港，您都將進(jìn)行相同數(shù)量的拆分和比較。

因此骤竹，最佳帝牡，最差和平均情況的時(shí)間復(fù)雜度將始終為 O(n log n)。

歸并排序算法的一個(gè)缺點(diǎn)是它需要一個(gè)臨時(shí)的“工作”數(shù)組瘤载，其大小與被排序的數(shù)組相同否灾。 它不是原地排序卖擅，不像例如quicksort鸣奔。

大多數(shù)實(shí)現(xiàn)歸并排序算法是穩(wěn)定的排序。這意味著具有相同排序鍵的數(shù)組元素在排序后將保持相對(duì)于彼此的相同順序惩阶。這對(duì)于數(shù)字或字符串等簡單值并不重要挎狸，但在排序更復(fù)雜的對(duì)象時(shí)，如果不是穩(wěn)定的排序可能會(huì)出現(xiàn)問題断楷。

譯注：當(dāng)元素相同時(shí)锨匆，排序后依然保持排序之前的相對(duì)順序，那么這個(gè)排序算法就是穩(wěn)定的冬筒。穩(wěn)定的排序有：插入排序恐锣、計(jì)數(shù)排序、歸并排序舞痰、基數(shù)排序等等土榴，詳見穩(wěn)定的排序。

擴(kuò)展閱讀

歸并排序的維基百科

歸并排序的中文維基百科

作者：Kelvin Lau. Additions 响牛， Matthijs Hollemans
翻譯：Andy Ron
校對(duì)：Andy Ron