用 JavaScript 實(shí)現(xiàn)鏈表操作 - 15 Merge Sort

X_AirDu 發(fā)布于2019-08-20 14:23 / 2120人閱讀

摘要：需求實(shí)現(xiàn)函數(shù)進(jìn)行歸并排序。解法歸并排序的運(yùn)行方式是，遞歸的把一個(gè)大鏈表切分成兩個(gè)小鏈表。切分到最后就全是單節(jié)點(diǎn)鏈表了，而單節(jié)點(diǎn)鏈表可以被認(rèn)為是已經(jīng)排好序的。這時(shí)候再兩兩合并，最終會(huì)得到一個(gè)完整的已排序鏈表。用把排好序的兩個(gè)鏈表合并起來(lái)。

TL;DR

對(duì)鏈表進(jìn)行歸并排序，系列目錄見前言和目錄。

需求

實(shí)現(xiàn)函數(shù) mergeSort() 進(jìn)行歸并排序。注意這種排序法需要使用遞歸。在 frontBackSplit() 和 sortedMerge() 兩個(gè)函數(shù)的幫助下，你可以很輕松的寫一個(gè)遞歸的排序。基本算法是，把一個(gè)鏈表切分成兩個(gè)更小的鏈表，遞歸地對(duì)它們進(jìn)行排序，最終把兩個(gè)排好序的小鏈表合成完整的鏈表。

var list = 4 -> 2 -> 1 -> 3 -> 8 -> 9 -> null
mergeSort(list) === 1 -> 2 -> 3 -> 4 -> 8 -> 9 -> null

解法

歸并排序的運(yùn)行方式是，遞歸的把一個(gè)大鏈表切分成兩個(gè)小鏈表。切分到最后就全是單節(jié)點(diǎn)鏈表了，而單節(jié)點(diǎn)鏈表可以被認(rèn)為是已經(jīng)排好序的。這時(shí)候再兩兩合并，最終會(huì)得到一個(gè)完整的已排序鏈表。

因?yàn)榍蟹趾秃喜蓚€(gè)最重要的功能都已經(jīng)實(shí)現(xiàn)，需要思考的就只是如何遞歸整個(gè)過(guò)程了。我們分析一下可以把整個(gè)過(guò)程分成：

用 frontBackSplit() 把鏈表切分成兩個(gè)，分別叫 first 和 second 。

對(duì) first 和 second 排序。

用 sortedMerge() 把排好序的兩個(gè)鏈表合并起來(lái)。

其中第 2 步就是遞歸的點(diǎn)，因?yàn)榕判蜻@個(gè)事情恰好是 mergeSort 本身可以做的。

代碼如下：

const { Node } = require("./00-utils")
const { frontBackSplit } = require("./12-front-back-split")
const { sortedMerge } = require("./14-sorted-merge")

function mergeSort(list) {
  if (!list || !list.next) return list

  const first = new Node()
  const second = new Node()
  frontBackSplit(list, first, second)

  return sortedMerge(mergeSort(first), mergeSort(second))
}

參考資料

Codewars Kata
GitHub 的代碼實(shí)現(xiàn)
GitHub 的測(cè)試