用 JavaScript 实现链表操作 - 06 Insert Sort

doodlewind 发布于2019-08-21 11:28 / 1761人阅读

摘要：需求实现一个函数对链表进行升序排列插入排序。关于插入排序插入排序的介绍可以看，大体逻辑为建立一个新的空链表。遍历完成，返回新链表。代码如下总结因为有上个的函数的帮助，这个插入排序实现起来非常简单。

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语言实现链表

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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