如何按字母顺序对 JavaScript 中的链表进行排序
How to Alphabetically Sort a Linked List in JavaScript
我有几本类做一个书的链表。我很难按字母顺序对每本书进行排序，然后 return 全部阅读。我还没有在 SO 上找到任何与在 JavaScript 中按字母顺序排序链表相关的内容，所以希望这个 post 示例对其他人也有用。 sortList() 函数应该按书名的字母顺序对书籍进行排序，然后 return 所有这些书都可以 console.log。
class Book {
constructor(element) {
this.element = element;
this.next = null;
}
}
class Books {
constructor() {
this.head = null;
this.size = 0;
}
add(element) { //adds a book
var node = new Book(element);
var current;
if (this.head == null) this.head = node;
else {
current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.size++;
}
insertAt(element, index) { //adds a book at the specified index
if (index < 0 || index > this.size)
return console.log("Please enter a valid index.");
else {
var node = new Book(element);
var curr, prev;
curr = this.head;
if (index == 0) {
node.next = this.head;
this.head = node;
} else {
curr = this.head;
var it = 0;
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
node.next = curr;
prev.next = node;
}
this.size++;
}
}
sortList() { //sorts the head alphabetically
var sortedList = new Books();
let current = this.head;
var array = new Set();
while (current != null) {
array.add(current);
current = current.link;
}
array.sort();
for (let i = array.length - 1; i >= 0; i--) {
sortedList.insertAt(new Book(array[i]), 0);
}
return sortedList;
}
}
var bookList = new Books();
bookList.add("abook1");
bookList.add("bbook2");
bookList.add("cbook3");
bookList.add("dbook4");
bookList.add("ebook5");
bookList.add("fbook6");
bookList.add("gbook7");
bookList.add("hbook8");
console.log(bookList.sortList()); //prints out the sorted bookList
您可以通过检查节点和下一个节点来更改喜欢列表中的值。如有必要，交换值并从头开始再次比较。
此方法采用比较函数，该函数使用 three-way comparison 和 return 值小于零、零或大于零，具体取决于顺序。
const
compareString = (a, b) => a.localeCompare(b);
class Book {
constructor(element) {
this.element = element;
this.next = null;
}
}
class Books {
constructor() {
this.head = null;
this.size = 0;
}
add(element) { //adds a book
var node = new Book(element);
var current;
if (this.head == null) this.head = node;
else {
current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.size++;
}
sortList() {
let current = this.head;
while (current.next) {
if (compareString(current.element, current.next.element) > 0) { // swap
[current.element, current.next.element] = [current.next.element, current.element];
current = this.head;
continue;
}
current = current.next;
}
return this;
}
}
var bookList = new Books();
bookList.add("ac");
bookList.add("ab");
bookList.add("cc");
bookList.add("bb");
bookList.add("aa");
bookList.add("dd");
bookList.add("ba");
bookList.add("bc");
console.log(bookList.sortList()); //prints out the sorted bookList
作为替代解决方案，这里有一个合并排序算法，其时间复杂度为 O(nlogn)：
class Book {
constructor(element) {
this.element = element;
this.next = null;
}
}
class Books {
constructor() {
this.head = null;
this.size = 0;
}
add(element) { //adds a book
var node = new Book(element);
var current;
if (this.head == null) this.head = node;
else {
current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.size++;
}
*values() { // Utility function to facilitate printing
let current = this.head;
while (current) {
yield current.element;
current = current.next;
}
}
sortList() { // Sorts the list alphabetically, using merge sort
if (!this.head || !this.head.next) return; // Nothing to sort
// Find last node of first half
let node = this.head;
for (let fast = node.next; fast?.next; fast = fast.next.next) {
node = node.next;
}
// Split list into two halves
let that = new Books();
that.head = node.next;
node.next = null;
// Recursively sort the two shorter lists
this.sortList();
that.sortList();
// Merge the two sorted lists
if (this.head.element > that.head.element) [this.head, that.head] = [that.head, this.head];
let prev = this.head;
let thatNode = that.head;
while (prev.next && thatNode) {
if (prev.next.element > thatNode.element) [thatNode, prev.next] = [prev.next, thatNode];
prev = prev.next;
}
if (thatNode) prev.next = thatNode;
// The sort happened in-place, so we don't return the list
}
}
let bookList = new Books();
for (let ch of "himvlxpbcyndwjkefuzgqorsat") {
bookList.add(ch);
}
console.log("input:");
console.log(...bookList.values());
bookList.sortList();
console.log("sorted:");
console.log(...bookList.values());
比较运行次。
这里是算法之间的比较，使用 500 个元素的列表，最初按相反顺序排序：“499”、“498”、“497”、...、“001”、“000”。
const
compareString = (a, b) => a.localeCompare(b);
class Book {
constructor(element) {
this.element = element;
this.next = null;
}
}
class Books {
constructor() {
this.head = null;
this.size = 0;
}
add(element) { //adds a book
var node = new Book(element);
var current;
if (this.head == null) this.head = node;
else {
current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.size++;
}
sortList_NinaScholz() { // Version of 20.10.2021
let current = this.head;
while (current.next) {
if (compareString(current.element, current.next.element) > 0) { // swap
[current.element, current.next.element] = [current.next.element, current.element];
current = this.head;
continue;
}
current = current.next;
}
return this;
}
sortList_trincot() {
if (!this.head?.next) return; // Nothing to sort
// Find last node of first half
let node = this.head;
for (let fast = node.next; fast?.next; fast = fast.next.next) {
node = node.next;
}
// Split list into two halves
let that = new Books();
that.head = node.next;
node.next = null;
// Recursively sort the two shorter lists
this.sortList_trincot();
that.sortList_trincot();
// Merge the two sorted lists
if (this.head.element > that.head.element) [this.head, that.head] = [that.head, this.head];
let prev = this.head;
let thatNode = that.head;
while (prev.next && thatNode) {
if (prev.next.element > thatNode.element) [thatNode, prev.next] = [prev.next, thatNode];
prev = prev.next;
}
if (thatNode) prev.next = thatNode;
// The sort happened in-place, so we don't return the list
}
}
console.log("running sort...");
setTimeout(function () {
for (let method of ["trincot", "NinaScholz"]) {
let bookList = new Books();
for (let v of [...Array(500).keys()].reverse())
bookList.add(v.toString().padStart(3, "0"));
let start = performance.now();
bookList["sortList_" + method]();
console.log(method, performance.now() - start, "milliseconds");
// verify that list is really sorted
for (let book = bookList.head, i=0; book; book = book.next, i++) {
if (+book.element != i) throw "not well sorted";
}
}
}, 100);
我有几本类做一个书的链表。我很难按字母顺序对每本书进行排序，然后 return 全部阅读。我还没有在 SO 上找到任何与在 JavaScript 中按字母顺序排序链表相关的内容，所以希望这个 post 示例对其他人也有用。 sortList() 函数应该按书名的字母顺序对书籍进行排序，然后 return 所有这些书都可以 console.log。
class Book {
constructor(element) {
this.element = element;
this.next = null;
}
}
class Books {
constructor() {
this.head = null;
this.size = 0;
}
add(element) { //adds a book
var node = new Book(element);
var current;
if (this.head == null) this.head = node;
else {
current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.size++;
}
insertAt(element, index) { //adds a book at the specified index
if (index < 0 || index > this.size)
return console.log("Please enter a valid index.");
else {
var node = new Book(element);
var curr, prev;
curr = this.head;
if (index == 0) {
node.next = this.head;
this.head = node;
} else {
curr = this.head;
var it = 0;
while (it < index) {
it++;
prev = curr;
curr = curr.next;
}
node.next = curr;
prev.next = node;
}
this.size++;
}
}
sortList() { //sorts the head alphabetically
var sortedList = new Books();
let current = this.head;
var array = new Set();
while (current != null) {
array.add(current);
current = current.link;
}
array.sort();
for (let i = array.length - 1; i >= 0; i--) {
sortedList.insertAt(new Book(array[i]), 0);
}
return sortedList;
}
}
var bookList = new Books();
bookList.add("abook1");
bookList.add("bbook2");
bookList.add("cbook3");
bookList.add("dbook4");
bookList.add("ebook5");
bookList.add("fbook6");
bookList.add("gbook7");
bookList.add("hbook8");
console.log(bookList.sortList()); //prints out the sorted bookList
您可以通过检查节点和下一个节点来更改喜欢列表中的值。如有必要，交换值并从头开始再次比较。
此方法采用比较函数，该函数使用 three-way comparison 和 return 值小于零、零或大于零，具体取决于顺序。
const
compareString = (a, b) => a.localeCompare(b);
class Book {
constructor(element) {
this.element = element;
this.next = null;
}
}
class Books {
constructor() {
this.head = null;
this.size = 0;
}
add(element) { //adds a book
var node = new Book(element);
var current;
if (this.head == null) this.head = node;
else {
current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.size++;
}
sortList() {
let current = this.head;
while (current.next) {
if (compareString(current.element, current.next.element) > 0) { // swap
[current.element, current.next.element] = [current.next.element, current.element];
current = this.head;
continue;
}
current = current.next;
}
return this;
}
}
var bookList = new Books();
bookList.add("ac");
bookList.add("ab");
bookList.add("cc");
bookList.add("bb");
bookList.add("aa");
bookList.add("dd");
bookList.add("ba");
bookList.add("bc");
console.log(bookList.sortList()); //prints out the sorted bookList
作为替代解决方案，这里有一个合并排序算法，其时间复杂度为 O(nlogn)：
class Book {
constructor(element) {
this.element = element;
this.next = null;
}
}
class Books {
constructor() {
this.head = null;
this.size = 0;
}
add(element) { //adds a book
var node = new Book(element);
var current;
if (this.head == null) this.head = node;
else {
current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.size++;
}
*values() { // Utility function to facilitate printing
let current = this.head;
while (current) {
yield current.element;
current = current.next;
}
}
sortList() { // Sorts the list alphabetically, using merge sort
if (!this.head || !this.head.next) return; // Nothing to sort
// Find last node of first half
let node = this.head;
for (let fast = node.next; fast?.next; fast = fast.next.next) {
node = node.next;
}
// Split list into two halves
let that = new Books();
that.head = node.next;
node.next = null;
// Recursively sort the two shorter lists
this.sortList();
that.sortList();
// Merge the two sorted lists
if (this.head.element > that.head.element) [this.head, that.head] = [that.head, this.head];
let prev = this.head;
let thatNode = that.head;
while (prev.next && thatNode) {
if (prev.next.element > thatNode.element) [thatNode, prev.next] = [prev.next, thatNode];
prev = prev.next;
}
if (thatNode) prev.next = thatNode;
// The sort happened in-place, so we don't return the list
}
}
let bookList = new Books();
for (let ch of "himvlxpbcyndwjkefuzgqorsat") {
bookList.add(ch);
}
console.log("input:");
console.log(...bookList.values());
bookList.sortList();
console.log("sorted:");
console.log(...bookList.values());
比较运行次。
这里是算法之间的比较，使用 500 个元素的列表，最初按相反顺序排序：“499”、“498”、“497”、...、“001”、“000”。
const
compareString = (a, b) => a.localeCompare(b);
class Book {
constructor(element) {
this.element = element;
this.next = null;
}
}
class Books {
constructor() {
this.head = null;
this.size = 0;
}
add(element) { //adds a book
var node = new Book(element);
var current;
if (this.head == null) this.head = node;
else {
current = this.head;
while (current.next) {
current = current.next;
}
current.next = node;
}
this.size++;
}
sortList_NinaScholz() { // Version of 20.10.2021
let current = this.head;
while (current.next) {
if (compareString(current.element, current.next.element) > 0) { // swap
[current.element, current.next.element] = [current.next.element, current.element];
current = this.head;
continue;
}
current = current.next;
}
return this;
}
sortList_trincot() {
if (!this.head?.next) return; // Nothing to sort
// Find last node of first half
let node = this.head;
for (let fast = node.next; fast?.next; fast = fast.next.next) {
node = node.next;
}
// Split list into two halves
let that = new Books();
that.head = node.next;
node.next = null;
// Recursively sort the two shorter lists
this.sortList_trincot();
that.sortList_trincot();
// Merge the two sorted lists
if (this.head.element > that.head.element) [this.head, that.head] = [that.head, this.head];
let prev = this.head;
let thatNode = that.head;
while (prev.next && thatNode) {
if (prev.next.element > thatNode.element) [thatNode, prev.next] = [prev.next, thatNode];
prev = prev.next;
}
if (thatNode) prev.next = thatNode;
// The sort happened in-place, so we don't return the list
}
}
console.log("running sort...");
setTimeout(function () {
for (let method of ["trincot", "NinaScholz"]) {
let bookList = new Books();
for (let v of [...Array(500).keys()].reverse())
bookList.add(v.toString().padStart(3, "0"));
let start = performance.now();
bookList["sortList_" + method]();
console.log(method, performance.now() - start, "milliseconds");
// verify that list is really sorted
for (let book = bookList.head, i=0; book; book = book.next, i++) {
if (+book.element != i) throw "not well sorted";
}
}
}, 100);