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

doodlewind 發(fā)布于2019-08-21 11:28 / 1895人閱讀

摘要：需求實(shí)現(xiàn)一個(gè)函數(shù)對(duì)鏈表進(jìn)行升序排列插入排序。關(guān)于插入排序插入排序的介紹可以看，大體邏輯為建立一個(gè)新的空鏈表。遍歷完成，返回新鏈表。代碼如下總結(jié)因?yàn)橛猩蟼€(gè)的函數(shù)的幫助，這個(gè)插入排序?qū)崿F(xiàn)起來(lái)非常簡(jiǎn)單。

TL;DR

2016 年末最后一篇，對(duì)鏈表進(jìn)行插入排序。系列目錄見(jiàn) 前言和目錄。

需求

實(shí)現(xiàn)一個(gè) insertSort() 函數(shù)對(duì)鏈表進(jìn)行升序排列（插入排序）。實(shí)現(xiàn)過(guò)程中可以使用上一個(gè) kata 中的 sortedInsert() 函數(shù)。insertSort() 函數(shù)接受鏈表頭為參數(shù)并返回排序后的鏈表頭。

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

如果傳入的鏈表為 null 或者只有一個(gè)節(jié)點(diǎn)，就原樣返回。

關(guān)于插入排序

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

建立一個(gè)新的空鏈表。

依次遍歷待排序的鏈表節(jié)點(diǎn)，挨個(gè)插入新鏈表的合適位置，始終保持新鏈表是已排序的。

遍歷完成，返回新鏈表。

觀察這段邏輯不難發(fā)現(xiàn)，第二個(gè)步驟其實(shí)就是上個(gè) kata 中 sortedInsert 做的事情 -- 把節(jié)點(diǎn)插入一段已排序的鏈表的合適位置。在此之上稍微包裝一下就可以實(shí)現(xiàn) insertSort 。

遞歸版本

首先我們記住兩個(gè)函數(shù)的表達(dá)的意思：

insertSort 返回鏈表的排序版本。

sortedInsert 把節(jié)點(diǎn)插入一個(gè)已排序鏈表的合適位置，并返回修改后的鏈表（也是已排序的）。

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

整理后的代碼如下：

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

循環(huán)版本

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

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

總結(jié)

因?yàn)橛猩蟼€(gè) kata 的函數(shù)的幫助，這個(gè)插入排序?qū)崿F(xiàn)起來(lái)非常簡(jiǎn)單。遞歸版本再次體現(xiàn)了聲明式編程的優(yōu)勢(shì)。有時(shí)候能表達(dá)某種數(shù)據(jù)的不只是變量，也可以是函數(shù)。只要我們發(fā)現(xiàn)表達(dá)合適邏輯的函數(shù)，實(shí)現(xiàn)過(guò)程就會(huì)非常簡(jiǎn)單。

算法相關(guān)的代碼和測(cè)試我都放在 GitHub 上，如果對(duì)你有幫助請(qǐng)幫我點(diǎn)個(gè)贊！

參考資料

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