用 JavaScript 實現鏈表操作 - 06 Insert Sort

doodlewind 發布于2019-08-21 11:28 / 1901人閱讀

摘要：需求實現一個函數對鏈表進行升序排列插入排序。關于插入排序插入排序的介紹可以看，大體邏輯為建立一個新的空鏈表。遍歷完成，返回新鏈表。代碼如下總結因為有上個的函數的幫助，這個插入排序實現起來非常簡單。

TL;DR

2016 年末最后一篇，對鏈表進行插入排序。系列目錄見前言和目錄。

需求

實現一個 insertSort() 函數對鏈表進行升序排列（插入排序）。實現過程中可以使用上一個 kata 中的 sortedInsert() 函數。insertSort() 函數接受鏈表頭為參數并返回排序后的鏈表頭。

var list = 4 -> 3 -> 1 -> 2 -> null
insertSort(list) === 1 -> 2 -> 3 -> 4 -> null

如果傳入的鏈表為 null 或者只有一個節點，就原樣返回。

關于插入排序

插入排序的介紹可以看 Wikipedia ，大體邏輯為：

建立一個新的空鏈表。

依次遍歷待排序的鏈表節點，挨個插入新鏈表的合適位置，始終保持新鏈表是已排序的。

遍歷完成，返回新鏈表。

觀察這段邏輯不難發現，第二個步驟其實就是上個 kata 中 sortedInsert 做的事情 -- 把節點插入一段已排序的鏈表的合適位置。在此之上稍微包裝一下就可以實現 insertSort 。

遞歸版本

首先我們記住兩個函數的表達的意思：

insertSort 返回鏈表的排序版本。

sortedInsert 把節點插入一個已排序鏈表的合適位置，并返回修改后的鏈表（也是已排序的）。

然后我們用遞歸的思路描述 insertSort 邏輯，應該是先把原鏈表的第一個節點插入某個已排序的鏈表的合適位置，這段邏輯可以用 sortedInsert(someList, head.data) 表達。而這個 “某個已排序的鏈表” ，我們需要它包含除了 head 之外其他的所以節點，這個鏈表可以用 insertSort(head.next) 來表達。

整理后的代碼如下：

function insertSort(head) {
  if (!head) return null
  return sortedInsert(insertSort(head.next), head.data)
}

循環版本

循環版本是最接近算法描述的版本，所以不多贅述。代碼如下：

function insertSort(head) {
  for (var sortedList = null, node = head; node; node = node.next) {
    sortedList = sortedInsert(sortedList, node.data)
  }
  return sortedList
}

總結

因為有上個 kata 的函數的幫助，這個插入排序實現起來非常簡單。遞歸版本再次體現了聲明式編程的優勢。有時候能表達某種數據的不只是變量，也可以是函數。只要我們發現表達合適邏輯的函數，實現過程就會非常簡單。

算法相關的代碼和測試我都放在 GitHub 上，如果對你有幫助請幫我點個贊！

參考資料

Codewars Kata
GitHub 的代碼實現
GitHub 的測試

云服務器 GPU云服務器用javascript操作xml 多鏈表c語言實現 java實現鏈表插入遍歷c語言實現鏈表

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

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

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

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

BetaRabbit 2019-08-20 12:25 評論0 收藏0
Javascript的數據結構與算法(一)

摘要：對數組中的每一項運行給定函數，返回改函數會返回的項組成的數組。將所有的數組元素鏈接成一個字符串。數組合并方法可以向一個數組傳遞數組對象或是元素。通過棧實現對正整數的二進制轉換。源碼地址的數據結構與算法一源碼 1數組 1.1方法列表數組的常用方法如下: concat: 鏈接兩個或者更多數據，并返回結果。 every: 對數組中的每一項運行給定的函數，如果該函數對每一項都返回true...

VioletJack 2019-08-21 11:23 評論0 收藏0
Python_數據結構與算法

摘要：什么是數據結構數據的組織結構方式一組數據如何存儲，基本數據類型，，的封裝算法與數據結構的區別數據結構只是靜態的描述了數據元素之間的關系。高效的程序需要在數據結構的基礎上設計和選擇算法。數據結構和算法基礎什么是數據結構和算法：兵法，計算的方法。算法是獨立存在的一種解決問題的方法和思想。算法的特征：輸入：算法具有0個或多個輸入輸出：算法至少有1個或多個輸出有窮性：算法在有限的...

Kylin_Mountain 2019-07-30 16:02 評論0 收藏0
[ JavaScript ] 數據結構與算法 —— 鏈表

摘要：每個元素由一個存儲元素本身的節點和一個指向下一個元素的引用也稱指針或鏈接組成。相對于傳統的數組，鏈表的一個好處在于，添加或移除元素的時候不需要移動其他元素。然而，鏈表需要使用指針，因此實現鏈表時需要額外注意。本篇主要有三部分什么是鏈表鏈表的實現鏈表的變種源碼地址：https://github.com/yhtx1997/S... 另外，今天2019年2月18日上午發現 20...

wfc_666 2019-08-23 15:19 評論0 收藏0
用 JavaScript 實現鏈表操作 - 15 Merge Sort

摘要：需求實現函數進行歸并排序。解法歸并排序的運行方式是，遞歸的把一個大鏈表切分成兩個小鏈表。切分到最后就全是單節點鏈表了，而單節點鏈表可以被認為是已經排好序的。這時候再兩兩合并，最終會得到一個完整的已排序鏈表。用把排好序的兩個鏈表合并起來。 TL;DR 對鏈表進行歸并排序，系列目錄見前言和目錄。需求實現函數 mergeSort() 進行歸并排序。注意這種排序法需要使用遞歸。在 fr...

X_AirDu 2019-08-20 14:23 評論0 收藏0