用 JavaScript 實現鏈表操作 - 15 Merge Sort

X_AirDu 發布于2019-08-20 14:23 / 2124人閱讀

摘要：需求實現函數進行歸并排序。解法歸并排序的運行方式是，遞歸的把一個大鏈表切分成兩個小鏈表。切分到最后就全是單節點鏈表了，而單節點鏈表可以被認為是已經排好序的。這時候再兩兩合并，最終會得到一個完整的已排序鏈表。用把排好序的兩個鏈表合并起來。

TL;DR

對鏈表進行歸并排序，系列目錄見前言和目錄。

需求

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

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

解法

歸并排序的運行方式是，遞歸的把一個大鏈表切分成兩個小鏈表。切分到最后就全是單節點鏈表了，而單節點鏈表可以被認為是已經排好序的。這時候再兩兩合并，最終會得到一個完整的已排序鏈表。

因為切分和合并兩個最重要的功能都已經實現，需要思考的就只是如何遞歸整個過程了。我們分析一下可以把整個過程分成：

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

對 first 和 second 排序。

用 sortedMerge() 把排好序的兩個鏈表合并起來。

其中第 2 步就是遞歸的點，因為排序這個事情恰好是 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 的代碼實現
GitHub 的測試

云服務器 GPU云服務器 merge_sort merge-sort 用javascript操作xml 多鏈表c語言實現

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/81590.html

用 JavaScript 實現鏈表操作 - 前言和目錄

摘要：我打算寫一個鏈表操作的系列，來自的系列，實現語言是。通過自己實現一個鏈表和常用操作，可以加深理解這類數據結構的優缺點。鏈表經常用來訓練指針操作，雖然這只對適用，但等高級語言中控制引用的思路其實也差不多。 TL;DR 我打算寫一個鏈表操作的系列，來自 Codewars 的 Linked List 系列 kata ，實現語言是 JavaScript 。這篇是開篇，簡單描述了一下我寫這個的目...

BetaRabbit 2019-08-20 12:25 評論0 收藏0
JavaScript數據結構和算法

摘要：棧被稱為一種后入先出的數據結構。散列使用的數據結構叫做散列表。這些操作需要求助于其他數據結構，比如下面介紹的二叉查找樹。前言在過去的幾年中，得益于Node.js的興起，JavaScript越來越廣泛地用于服務器端編程。鑒于JavaScript語言已經走出了瀏覽器，程序員發現他們需要更多傳統語言（比如C++和Java）提供的工具。這些工具包括傳統的數據結構（如鏈表，棧，隊列，圖等），...

EastWoodYang 2019-08-21 16:23 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
用 JavaScript 實現鏈表操作 - 13 Shuffle Merge

摘要：需求實現函數把兩個鏈表合并成一個。新鏈表的節點是交叉從兩個鏈表中取的。通過行的調換指針，我們可以保證下一次循環就是對另一個鏈表進行操作了。這樣一直遍歷到兩個鏈表末尾，返回結束。參考資料的代碼實現的測試 TL;DR 把兩個鏈表洗牌合并成一個，系列目錄見前言和目錄。需求實現函數 shuffleMerge() 把兩個鏈表合并成一個。新鏈表的節點是交叉從兩個鏈表中取的。這叫洗牌合并。舉...

shiguibiao 2019-08-20 14:21 評論0 收藏0
148. Sort List

摘要：題目分析一看到問題，而且時間復雜度要求又是，很自然地就會想到數組時，如下這道題要求是，所以在上面的基礎上還要進行一些額外操作找到的中點，使用快慢指針法。需要注意的是，找到中點后要把鏈表分成兩段，即兩個鏈表。這部分代碼應該近似于這道題的答案。 Sort a linked list in O(n log n) time using constant space complexity. 題...

anquan 2019-08-14 17:56 評論0 收藏0