JavaScript實作歸并排序演算法詳解

說明

歸并排序（Merge Sort）演算法，也叫合并排序，是創建在歸并操作上的一種有效的排序演算法，演算法是采用分治法（Divide and Conquer）的一個非常典型的應用，且各層分治遞回可以同時進行，歸并排序思路簡單，速度僅次于快速排序，為穩定排序演算法，一般用于對總體無序，但是各子項相對有序的數列，

歸并排序和選擇排序一樣，歸并排序的性能不受輸入資料的影響，但表現比選擇排序好的多，因為始終都是O(n log n）的時間復雜度，代價是需要額外的記憶體空間，

歸并排序是用分治思想，分治模式在每一層遞回上有三個步驟：

分解（Divide）：將n個元素分成個含n/2個元素的子序列， 解決（Conquer）：用合并排序法對兩個子序列遞回的排序， 合并（Combine）：合并兩個已排序的子序列已得到排序結果，

實作程序

1. 將所有陣列項無限細分，得到1個個獨立的單元，也就是不斷分解，
2. 將相近的兩兩進行比較，按照已排序陣列合并，形成（n/2）個序列，每個序列包含2個數字，
3. 將上述兩個序列遞回合并，按照已排序陣列合并，形成（n/4）個序列，每個序列包含4個數字，
4. 重復步驟2，直到所有元素合并排序完畢，

示意圖

性能分析

平均時間復雜度：O(nlogn) 最佳時間復雜度：O(n) 最差時間復雜度：O(nlogn) 空間復雜度：O(n) 排序方式：In-place 穩定性：穩定

JS第1種寫法，標準雙指標移動比較

/**
 * 歸并排序 ，采用分而治之(divide - conquer)的步驟
 * 1. 分解（Divide），把待排序元素的序列分解為兩個子序列，以中間2分, 每個子序列包括一半成員，
 * 2. 解決（Conquer），對每個子序列分別呼叫歸并操作, 進行遞回或非遞回回圈操作，完成內部排序，
 * 3. 合并（Combine），合并兩個排好序的子序列，生成排序結果， 歸并排序的最壞時間復雜度和平均時間復雜度均為O(nlogn)
 */
(function () {
  // 將兩個有序陣列合并為一個新的有序陣列
  function merge (arr, left, mid, right) {
    // 先建立一個長度等于原陣列的臨時陣列
    const temp = []
    // 左側指標
    let i = left
    // 右側指標
    let j = mid + 1
    // 臨時陣列指標
    let k = 0
    // 當左指標小于中間，且右指標不大于最右側時
    while (i <= mid && j <= right) {
      // 如果左側小于右側，將數移到臨時陣列中左側
      if (arr[i] <= arr[j]) {
        temp[k++] = arr[i++]
        // 否則移動到臨時陣列右側
      } else {
        temp[k++] = arr[j++]
      }
    }

    // 如果左邊陣列還有資料，就把左側剩余都放入到原陣列后面
    while (i <= mid) {
      temp[k++] = arr[i++]
    }
    // 如果右側陣列還有資料，把剩下的資料放入到原陣列后面
    while (j <= right) {
      temp[k++] = arr[j++]
    }

    // 將排序后的元素全部移動到原陣列中
    let x = 0
    while (left <= right) {
      arr[left++] = temp[x++]
    }
    console.log('arr:', arr)
  }

  function mergeSort (arr, left, right) {
    // 得到中間值
    const mid = Math.floor((left + right) / 2)
    // 如果左側小于右側則執行合并排序
    if (left < right) {
      // 遞回合并左側
      mergeSort(arr, left, mid)
      // 遞回合并右側
      mergeSort(arr, mid + 1, right)
      // 合并左右結果
      merge(arr, left, mid, right)
    }
    return arr
  }

  // test
  const arr = [7, 11, 9, 10, 12, 13, 8, -2, 0, 8]
  console.time('sort')
  console.log('origin:', arr)
  console.log('\r\nsorted:', mergeSort(arr, 0, arr.length - 1))
  console.timeEnd('sort')
})();

// JS第2種寫法，雙指標移動結合陣列特性
(function () {
  function mergeSort (arr) {
    const len = arr.length
    if (len < 2) {
      return arr
    }
    // 取得當前陣列的中間位置
    const mid = Math.floor(len / 2)
    const left = arr.slice(0, mid)
    const right = arr.slice(mid)
    console.log('mergeSort arr:', arr, left, right)
    // 遞回呼叫，不斷重復直到當前陣列拆分剩1項
    return merge(mergeSort(left), mergeSort(right))
  }

  // 將兩個有序陣列進行合并為一個新的有序陣列
  function merge (left, right) {
    // 建立一個空陣列，用來存放排序結果
    const result = []
    // 左右陣列的長度都不為空時，則將兩個陣列的第一個進行比較
    // 如左側小于右，則移除左側的內容到結果資料，反之移動右側成員
    while (left.length && right.length) {
      if (left[0] <= right[0]) {
        result.push(left.shift())
      } else {
        result.push(right.shift())
      }
    }
    // 最后把剩余的左或者右側成員全部添加到結果陣列
    while (left.length) {
      result.push(left.shift())
    }

    while (right.length) {
      result.push(right.shift())
    }
    // 這樣一趟下來后，兩個陣列就合并為一個新的排序陣列
    return result
  }
})()

鏈接

歸并排序演算法原始碼：https://github.com/microwind/algorithms/tree/master/sorts/mergesort

其他排序演算法原始碼：https://github.com/microwind/algorithms

標籤：其他

上一篇：極限科技受邀參加 2023 可信資料庫發展大會并入選 “中國資料庫產業圖譜”

下一篇：返回列表