排序链接数组
Sorting a linked array
上下文：
我有一个 LinkedList class，它包含并自动以正确的顺序插入节点。注意这是一个链表数据结构（保存nodes/elements的数组代表RAM，指针-head，tail，以及next和prev 表示 RAM 中的地址（但在本例中，它们是保存节点的数组的索引）。
例如
myLinkedList.insert(2);
myLinkedList.insert(1);
myLinkedList.output(); // => [{value:2, next:null, prev:1}, {value:1,next:0,prev:null]}, head = 1, tail = 0
所以现在当我调用我的 printInOrder 函数时，它会输出 1，然后是 2，然后停止。
注意：当我插入一个新节点时，它被推到数组的末尾，但是它的相邻节点的指针发生了变化（所以next 和 prev) 以便从 head 到 tail 的类似火车的路径包括特定顺序的所有节点（默认为升序）。所以插入的节点总是在最后，只有它的指针表示它的位置。
我的问题：
这是我的问题：（见问题末尾的代码）
假设我创建了一个链表，它默认排序（升序），并且我有值 2、1 和 3。所以当我遍历列表时，我将收到 1,2， 3.现在，我想重新排序链表。这意味着，每个节点的索引 不会改变 ，但节点的指针会改变。毕竟，指针是创造秩序的东西。那么我将如何使用一些排序算法，比如合并或冒泡，在不实际改变它们的顺序的情况下对我的节点进行排序，只是它们的 next 和 prev 指针（以及全局 head 和 tail).
我的代码
这是目前为止重新排序函数的代码，它目前使用冒泡排序但不起作用：
class LinkedList {
constructor(sortingFunction) {
this.head;
this.tail;
this.list = [];
this.sortingFunction = sortingFunction ? ? ((a, b) => {
return a < b
});
}
sort(sortingFunction) {
if (!sortingFunction) {
return false;
}
this.head = null;
this.tail = null;
const arr = this.list.map(x => x);
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (!arr[j + 1] ? .value) {
console.log("no");
continue;
}
if (sortingFunction(arr[j].value, arr[j + 1].value)) {
let tmp_next = arr[j].next;
let tmp_prev = arr[j].previous;
arr[j].next = arr[j + 1].next;
arr[j].previous = arr[j + 1].previous;
arr[j + 1].next = tmp_next;
arr[j + 1].previous = tmp_prev;
}
}
}
this.list = arr;
}
}
这里是我的 LinkedList class 的完整代码，这将允许您重现我的问题 - 即节点根本无法自行排序。他们的指针改变了，但不是他们应该的方式，我不明白为什么。
class LinkedList {
constructor(sortingFunction) {
this.head;
this.tail;
this.list = [];
this.sortingFunction = sortingFunction ?? ((a,b) => {return a < b});
}
some(func) {
let currentNode = this.list[this.head];
let index = this.head;
while(!func(currentNode)) {
index = currentNode.next;
currentNode = this.list[index];
if(index == undefined || index == null) { return -1; }
}
return index;
}
forEachInOrder(func) {
let current = this.head;
while(current != undefined) {
const node = this.list[current];
func(node);
current = node.next;
}
}
* iterator() {
let current = this.head;
while(current != undefined) {
const node = this.list[current];
yield node;
current = node.next;
}
}
insert(value) {
if(!this.list.length) {
this.head = 0;
this.tail = 0;
this.list.push({value, next:null,previous:null});
return 0;
}
let nodeToInsert = {value, next:null,previous:null};
let indexToInsert = this.head;
let nthnode = this.list[this.head];
while(nthnode && this.sortingFunction(nthnode.value, value)) {
indexToInsert = nthnode.next;
nthnode = this.list[indexToInsert];
}
if(indexToInsert === null) {
// new tail (biggest)
nodeToInsert.previous = this.tail;
this.list[this.tail].next = this.list.length;
this.tail = this.list.length;
} else if(indexToInsert === this.head) {
// new head (smallest)
nodeToInsert.next = this.head;
this.list[this.head].previous = this.list.length;
this.head = this.list.length;
} else {
nodeToInsert.next = indexToInsert;
if(this.list[this.list[indexToInsert].previous]?.next != undefined) {
this.list[this.list[indexToInsert].previous].next = this.list.length;
}
nodeToInsert.previous = this.list[indexToInsert].previous;
this.list[indexToInsert].previous = this.list.length;
}
this.list.push(nodeToInsert);
return 1;
}
reverse() {
let _temp;
for(let i = 0; i < this.list.length; i++) {
_temp = this.list[i].next;
this.list[i].next = this.list[i].previous;
this.list[i].previous = _temp;
}
_temp = this.head;
this.head = this.tail;
this.tail = _temp;
}
sort(sortingFunction) {
if(!sortingFunction) {return false;}
this.head = null;
this.tail = null;
const arr = this.list.map(x=>x);
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if(!arr[j+1]?.value) {continue;}
if (sortingFunction(arr[j].value, arr[j+1].value)) {
let tmp_next = arr[j].next;
let tmp_prev = arr[j].previous;
arr[j].next = arr[j+1].next;
arr[j].previous = arr[j+1].previous;
arr[j+1].next = tmp_next;
arr[j+1].previous = tmp_prev;
}
}
}
this.list = arr;
}
print() {
console.log(this.list);
console.log("Head:",this.head,"\nTail:",this.tail, "\nDefault is ascending order.");
}
printInOrder() {
let current = this.list[this.head];
while(current) {
console.log(current.value);
current = this.list[current.next];
}
}
}
const list = new LinkedList();
list.insert(100);
list.insert(30);
list.insert(50);
list.insert(400);
list.insert(10);
list.insert(200);
list.insert(-90);
console.log("When each node is sorted when it is inserted:")
list.print();
list.sort((a, b) => {
return a > b;
});
console.log("Now, when re-sorted:");
list.print();
这是一个利用 Array#sort()
的快速而肮脏的解决方案
const list = [
{ value: { num: 1, str: 'a' }, next: 3, prev: 2 },
{ value: { num: 2, str: 'e' }, next: 2, prev: null },
{ value: { num: 3, str: 'v' }, next: 0, prev: 1 },
{ value: { num: 4, str: 'g' }, next: null, prev: 0 }];
let head = 1, tail = 3;
function sort(sortingFunction) {
const sorted = list
.map((node, idx) => ({ node, idx }))
.sort(({ node: { value: a } }, { node: { value: b } }) => sortingFunction(a, b));
for (const [i, { node, idx }] of sorted.entries()) {
if (!i) {
node.prev = null;
head = idx;
} else node.prev = sorted[i - 1].idx;
if (i === sorted.length - 1) {
node.next = null;
tail = idx;
} else node.next = sorted[i + 1].idx;
}
}
const log_list = () => { let node = list[head]; while (node !== undefined) { console.log(node.value); node = list[node.next]; } };
// initial order logging
console.log('initial - ', 'head: ', head, ' tail: ', tail);
log_list();
console.log('list order: ', ...list.map((o) => o.value.num));
// sort descending
sort((a, b) => b.num - a.num);
// after sort logging
console.log('\nsorted descending - ', 'head: ', head, ' tail: ', tail);
log_list();
console.log('list order: ', ...list.map((o) => o.value.num));
// sort alphabetic
sort((a, b) => a.str.localeCompare(b.str));
// after sort logging
console.log('\nsorted alphabetic - ', 'head: ', head, ' tail: ', tail);
log_list();
console.log('list order: ', ...list.map((o) => o.value.num));
.as-console-wrapper { max-height: 100% !important; top: 0; }
以上为您提供了 javascript 引擎 (timsort in V8) 提供的优化排序的优势，但如果您想实现自己的排序，您也可以在列表内排序，而不是对包含它的数组进行排序。
您要求按值在数组中按顺序保持节点的顺序使这变得更加困难，因为交换时您需要记住将相邻节点更新为要比较的节点以保持列表连续。
这是一个快速的冒泡排序，它从头到尾遍历列表，直到没有交换发生。它接受一个回调，该回调应该 return >0 以在 a.
之前对 b 进行排序
const list = [
{ value: { num: 1, str: 'a' }, next: 3, prev: 2 },
{ value: { num: 2, str: 'e' }, next: 2, prev: null },
{ value: { num: 3, str: 'v' }, next: 0, prev: 1 },
{ value: { num: 4, str: 'g' }, next: null, prev: 0 }];
let head = 1, tail = 3;
function sort(sortingFunction) {
let flag = true, node = list[head];
while (flag) {
flag = false;
while (node.next !== null) {
if (sortingFunction(node.value, list[node.next].value) > 0) {
const prev_node = list[node.prev];
const _node = list[node.next];
const next_node = list[_node.next];
const temp = node.prev;
if (prev_node) prev_node.next = node.next;
node.prev = node.next;
node.next = _node.next;
if (next_node) next_node.prev = _node.prev;
_node.next = _node.prev;
_node.prev = temp;
if (_node.prev === null) head = node.prev;
if (node.next === null) tail = _node.next;
flag = true;
} else {
node = list[node.next];
}
}
node = list[head];
}
}
const log_list = () => { let node = list[head]; while (node !== undefined) { console.log(node.value); node = list[node.next]; } };
// // initial order logging
console.log('initial - ', 'head: ', head, ' tail: ', tail);
log_list();
console.log('list order: ', ...list.map((o) => o.value.num));
// sort numeric
sort((a, b) => b.num - a.num);
// after sort logging
console.log('\nsorted descending - ', 'head: ', head, ' tail: ', tail);
log_list();
console.log('list order: ', ...list.map((o) => o.value.num));
// sort str
sort((a, b) => a.str.localeCompare(b.str));
// after sort logging
console.log('\nsorted alphabetic - ', 'head: ', head, ' tail: ', tail);
log_list();
console.log('list order: ', ...list.map((o) => o.value.num));
.as-console-wrapper { max-height: 100% !important; top: 0; }
您的 sort 函数中存在一些问题：
内部循环查看按索引连续的对，但它应该比较按链接[=76]连续的对=]，因为这是您应该决定是否需要交换的地方。
您的代码交换涉及 4 个链接分配，但实际上涉及 6 个链接：
this.head 和 this.tail 设置为 null 但再也没有设置为适当的值。
你的代码有一个很好的 iterator() 方法，我想在你的冒泡排序中重用它，但为了避免它会使用最近交换更改的 next 引用，我建议对该生成器进行微小的更改，以便它不受此影响：
* iterator() {
let current = this.head;
while(current != undefined) {
const node = this.list[current];
current = node.next; // <--- move this here!
yield node; // ...so the consumer can safely alter node.next
}
}
现在您的 sort 方法可以变成：
sort(sortingFunction) {
if (!sortingFunction) return;
for (let i = 0; i < this.list.length; i++) {
let prevNode = null;
// Iterate in the current order, so by following the links:
for (let currNode of this.iterator()) { // Requires the change in the generator
if (prevNode && sortingFunction(currNode.value, prevNode.value)) {
// Get the indexes of the current pair of nodes:
let currIndex = prevNode.next;
let prevIndex = currNode.previous;
// Update links from outer neighbors to these two nodes
if (currNode.next != null) this.list[currNode.next].previous = prevIndex;
else this.tail = prevIndex;
if (prevNode.previous != null) this.list[prevNode.previous].next = currIndex;
else this.head = currIndex;
// Update links from these two nodes to outer neighbors:
currNode.previous = prevNode.previous;
prevNode.next = currNode.next;
// Update links between the two nodes themselves:
prevNode.previous = currIndex;
currNode.next = prevIndex;
} else {
prevNode = currNode;
}
}
}
}
这是我忍不住在 forEachInOrder 和 some 中使用您的生成器函数的整个脚本：
class LinkedList {
constructor(sortingFunction) {
this.head;
this.tail;
this.list = [];
this.sortingFunction = sortingFunction ?? ((a,b) => {return a < b});
}
some(func) { // I adapted this to use the iterator
for (const node of this.iterator()) {
if (func(node)) {
return node.previous == null ? this.head : this.list[node.previous].next;
}
}
return -1;
}
forEachInOrder(func) { // I adapted this to use the iterator
for (const node of this.iterator()) func(node);
}
* iterator() {
let current = this.head;
while(current != undefined) {
const node = this.list[current];
current = node.next; // <--- move this here!
yield node;
}
}
insert(value) {
if(!this.list.length) {
this.head = 0;
this.tail = 0;
this.list.push({value, next:null,previous:null});
return 0;
}
let nodeToInsert = {value, next:null,previous:null};
let indexToInsert = this.head;
let nthnode = this.list[this.head];
while(nthnode && this.sortingFunction(nthnode.value, value)) {
indexToInsert = nthnode.next;
nthnode = this.list[indexToInsert];
}
if(indexToInsert === null) {
// new tail (biggest)
nodeToInsert.previous = this.tail;
this.list[this.tail].next = this.list.length;
this.tail = this.list.length;
} else if(indexToInsert === this.head) {
// new head (smallest)
nodeToInsert.next = this.head;
this.list[this.head].previous = this.list.length;
this.head = this.list.length;
} else {
nodeToInsert.next = indexToInsert;
if(this.list[this.list[indexToInsert].previous]?.next != undefined) {
this.list[this.list[indexToInsert].previous].next = this.list.length;
}
nodeToInsert.previous = this.list[indexToInsert].previous;
this.list[indexToInsert].previous = this.list.length;
}
this.list.push(nodeToInsert);
return 1;
}
reverse() { // I adapted this to use the (modified) iterator
for (const node of this.iterator()) {
[node.next, node.previous] = [node.previous, node.next];
}
[this.head, this.tail] = [this.tail, this.head];
}
sort(sortingFunction) {
if (!sortingFunction) {return false;}
for (let i = 0; i < this.list.length; i++) {
let prevNode = null;
// Iterate in the current order, so by following the links:
for (let currNode of this.iterator()) { // Requires the change in the generator
if (prevNode && sortingFunction(currNode.value, prevNode.value)) {
// Get the indexes of the current pair of nodes:
let currIndex = prevNode.next;
let prevIndex = currNode.previous;
// Update links from outer neighbors to these two nodes
if (currNode.next != null) this.list[currNode.next].previous = prevIndex;
else this.tail = prevIndex;
if (prevNode.previous != null) this.list[prevNode.previous].next = currIndex;
else this.head = currIndex;
// Update links from these two nodes to outer neighbors:
currNode.previous = prevNode.previous;
prevNode.next = currNode.next;
// Update links between the two nodes themselves:
prevNode.previous = currIndex;
currNode.next = prevIndex;
} else {
prevNode = currNode;
}
}
}
}
print() { // I adapted this a bit to get more condense output and add a call to printInOrder
console.log(JSON.stringify(this.list));
console.log("Head:",this.head,"\nTail:",this.tail, "\nDefault is ascending order.");
this.printInOrder();
}
printInOrder() { // I adapted this to use your nice iterator()
console.log(...Array.from(this.iterator(), node => node.value));
}
}
const list = new LinkedList();
list.insert(100);
list.insert(30);
list.insert(50);
list.insert(400);
list.insert(10);
list.insert(200);
list.insert(-90);
console.log("When each node is sorted when it is inserted:")
list.print();
list.sort((a, b) => {
return a > b;
});
console.log("Now, when re-sorted:");
list.print();
再注意一点：您的 sortingFunction return 是一个布尔值（指示两个给定参数的顺序是否正确），这与可以传递给本机的比较器函数不同Array#sort 方法：需要 return 一个数字，它允许通过 returning a negative[=76= 来指示参数的顺序是否正确] 值，等于 0 和反转 positive 值。您可能希望在实施中遵循相同的“合同”。
使用更高效的排序算法
您可以进行 O(nlogn) 归并排序，而不是 O(n²) 冒泡排序。
我在这里添加了一个mergeSort方法，以及一个创建分区的辅助方法：splice。它从链接列表中提取一个部分（删除它）并将其 return 作为一个新实例。为了使这种拼接工作良好，它像共享内存池一样使用 相同的 列表，但有自己的 head 和 tail。这意味着列表的长度不再是链表大小的指示，因此一些引用 length 的代码必须更改，例如冒泡排序例程中的外部循环：
class LinkedList {
constructor(sortingFunction) {
this.head = null; // Initialise with null explicitly
this.tail = null;
this.list = [];
this.sortingFunction = sortingFunction ?? ((a,b) => {return a < b});
}
some(func) { // I adapted this to use the iterator
for (const node of this.iterator()) {
if (func(node)) {
return node.previous == null ? this.head : this.list[node.previous].next;
}
}
return -1;
}
forEachInOrder(func) { // I adapted this to use the iterator
for (const node of this.iterator()) func(node);
}
* iterator() {
let current = this.head;
while(current != undefined) {
const node = this.list[current];
current = node.next; // <--- move this here!
yield node;
}
}
insert(value) {
if (this.head == null) { // Avoid using list.length
this.head = this.list.length; // While here it is appropriate to use list.length!
this.tail = this.list.length;
this.list.push({value, next:null,previous:null});
return 0;
}
let nodeToInsert = {value, next:null,previous:null};
let indexToInsert = this.head;
let nthnode = this.list[this.head];
while(nthnode && this.sortingFunction(nthnode.value, value)) {
indexToInsert = nthnode.next;
nthnode = this.list[indexToInsert];
}
if(indexToInsert === null) {
// new tail (biggest)
nodeToInsert.previous = this.tail;
this.list[this.tail].next = this.list.length;
this.tail = this.list.length;
} else if(indexToInsert === this.head) {
// new head (smallest)
nodeToInsert.next = this.head;
this.list[this.head].previous = this.list.length;
this.head = this.list.length;
} else {
nodeToInsert.next = indexToInsert;
this.list[this.list[indexToInsert].previous].next = this.list.length;
nodeToInsert.previous = this.list[indexToInsert].previous;
this.list[indexToInsert].previous = this.list.length;
}
this.list.push(nodeToInsert);
return 1;
}
reverse() {
for (const node of this.iterator()) {
[node.next, node.previous] = [node.previous, node.next];
}
[this.head, this.tail] = [this.tail, this.head];
}
sort(sortingFunction) {
if (!sortingFunction) return false;
let dirty = true;
while (dirty) { // Removed dependency on length
dirty = false;
let prevNode = null;
// Iterate in the current order, so by following the links:
for (const currNode of this.iterator()) { // Requires the change in the generator
if (prevNode && sortingFunction(currNode.value, prevNode.value)) {
// Get the indexes of the current pair of nodes:
let currIndex = prevNode.next;
let prevIndex = currNode.previous;
// Update links from outer neighbors to these two nodes
if (currNode.next != null) this.list[currNode.next].previous = prevIndex;
else this.tail = prevIndex;
if (prevNode.previous != null) this.list[prevNode.previous].next = currIndex;
else this.head = currIndex;
// Update links from these two nodes to outer neighbors:
currNode.previous = prevNode.previous;
prevNode.next = currNode.next;
// Update links between the two nodes themselves:
prevNode.previous = currIndex;
currNode.next = prevIndex;
dirty = true;
} else {
prevNode = currNode;
}
}
}
}
// Added this method which can also be of use for algorithms that use partitioning
splice(head, tail) {
// Remove this slice from the current linked list
if (tail != this.tail) this.list[this.list[tail].next].previous = this.list[head].previous;
else this.tail = this.list[head].previous;
if (head != this.head) this.list[this.list[head].previous].next = this.list[tail].next;
else this.head = this.list[tail].next;
this.list[tail].next = null;
this.list[head].previous = null;
// Wrap the removed slice into a new linked list instance, but one that shares the memory list
let slice = new LinkedList(this.sortingFunction);
slice.list = this.list;
slice.head = head;
slice.tail = tail;
return slice;
}
mergeSort(sortingFunction) {
if (!sortingFunction || this.head == null || this.head == this.tail) return; // base case
// Find last node of first half
let fastIter = this.iterator();
fastIter.next();
let half;
for (half of this.iterator()) {
if (fastIter.next().done || fastIter.next().done) break;
}
// Split list into two halves
let right = this.splice(half.next, this.tail);
let left = this; // ...what remains after the splice.
// Recursively sort the two shorter lists
left.mergeSort(sortingFunction);
right.mergeSort(sortingFunction);
// Make sure the "left" sublist is the one with a head value that comes before the other head value
if (sortingFunction(this.list[right.head].value, this.list[left.head].value)) [left, right] = [right, left];
// Merge the two sorted lists
let tailIndex = left.head;
let otherIndex = right.head;
for (let currIndex = this.list[tailIndex].next; currIndex != null || otherIndex != null; currIndex = this.list[tailIndex].next) {
if (currIndex == null || otherIndex != null && sortingFunction(this.list[otherIndex].value, this.list[currIndex].value)) {
this.list[tailIndex].next = otherIndex;
this.list[otherIndex].previous = tailIndex;
tailIndex = otherIndex;
otherIndex = currIndex;
} else {
tailIndex = currIndex;
}
}
this.head = left.head;
this.tail = tailIndex;
}
print() { // I adapted this a bit to get more condense output and add a call to printInOrder
console.log(JSON.stringify(this.list));
console.log("Head:",this.head,"\nTail:",this.tail, "\nDefault is ascending order.");
this.printInOrder();
}
printInOrder() { // I adapted this to use your nice iterator()
console.log(...Array.from(this.iterator(), node => node.value));
}
}
const linked = new LinkedList();
linked.insert(100);
linked.insert(30);
linked.insert(50);
linked.insert(400);
linked.insert(10);
linked.insert(200);
linked.insert(-90);
console.log("When each node is sorted when it is inserted:")
linked.print();
linked.mergeSort((a, b) => {
return a > b;
});
console.log("Now, when re-sorted:");
linked.print();
上下文：
我有一个 LinkedList class，它包含并自动以正确的顺序插入节点。注意这是一个链表数据结构（保存nodes/elements的数组代表RAM，指针-head，tail，以及next和prev 表示 RAM 中的地址（但在本例中，它们是保存节点的数组的索引）。
例如
myLinkedList.insert(2);
myLinkedList.insert(1);
myLinkedList.output(); // => [{value:2, next:null, prev:1}, {value:1,next:0,prev:null]}, head = 1, tail = 0
所以现在当我调用我的 printInOrder 函数时，它会输出 1，然后是 2，然后停止。
注意：当我插入一个新节点时，它被推到数组的末尾，但是它的相邻节点的指针发生了变化（所以next 和 prev) 以便从 head 到 tail 的类似火车的路径包括特定顺序的所有节点（默认为升序）。所以插入的节点总是在最后，只有它的指针表示它的位置。
我的问题：
这是我的问题：（见问题末尾的代码）
假设我创建了一个链表，它默认排序（升序），并且我有值 2、1 和 3。所以当我遍历列表时，我将收到 1,2， 3.现在，我想重新排序链表。这意味着，每个节点的索引 不会改变 ，但节点的指针会改变。毕竟，指针是创造秩序的东西。那么我将如何使用一些排序算法，比如合并或冒泡，在不实际改变它们的顺序的情况下对我的节点进行排序，只是它们的 next 和 prev 指针（以及全局 head 和 tail).
我的代码
这是目前为止重新排序函数的代码，它目前使用冒泡排序但不起作用：
class LinkedList {
constructor(sortingFunction) {
this.head;
this.tail;
this.list = [];
this.sortingFunction = sortingFunction ? ? ((a, b) => {
return a < b
});
}
sort(sortingFunction) {
if (!sortingFunction) {
return false;
}
this.head = null;
this.tail = null;
const arr = this.list.map(x => x);
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (!arr[j + 1] ? .value) {
console.log("no");
continue;
}
if (sortingFunction(arr[j].value, arr[j + 1].value)) {
let tmp_next = arr[j].next;
let tmp_prev = arr[j].previous;
arr[j].next = arr[j + 1].next;
arr[j].previous = arr[j + 1].previous;
arr[j + 1].next = tmp_next;
arr[j + 1].previous = tmp_prev;
}
}
}
this.list = arr;
}
}
这里是我的 LinkedList class 的完整代码，这将允许您重现我的问题 - 即节点根本无法自行排序。他们的指针改变了，但不是他们应该的方式，我不明白为什么。
class LinkedList {
constructor(sortingFunction) {
this.head;
this.tail;
this.list = [];
this.sortingFunction = sortingFunction ?? ((a,b) => {return a < b});
}
some(func) {
let currentNode = this.list[this.head];
let index = this.head;
while(!func(currentNode)) {
index = currentNode.next;
currentNode = this.list[index];
if(index == undefined || index == null) { return -1; }
}
return index;
}
forEachInOrder(func) {
let current = this.head;
while(current != undefined) {
const node = this.list[current];
func(node);
current = node.next;
}
}
* iterator() {
let current = this.head;
while(current != undefined) {
const node = this.list[current];
yield node;
current = node.next;
}
}
insert(value) {
if(!this.list.length) {
this.head = 0;
this.tail = 0;
this.list.push({value, next:null,previous:null});
return 0;
}
let nodeToInsert = {value, next:null,previous:null};
let indexToInsert = this.head;
let nthnode = this.list[this.head];
while(nthnode && this.sortingFunction(nthnode.value, value)) {
indexToInsert = nthnode.next;
nthnode = this.list[indexToInsert];
}
if(indexToInsert === null) {
// new tail (biggest)
nodeToInsert.previous = this.tail;
this.list[this.tail].next = this.list.length;
this.tail = this.list.length;
} else if(indexToInsert === this.head) {
// new head (smallest)
nodeToInsert.next = this.head;
this.list[this.head].previous = this.list.length;
this.head = this.list.length;
} else {
nodeToInsert.next = indexToInsert;
if(this.list[this.list[indexToInsert].previous]?.next != undefined) {
this.list[this.list[indexToInsert].previous].next = this.list.length;
}
nodeToInsert.previous = this.list[indexToInsert].previous;
this.list[indexToInsert].previous = this.list.length;
}
this.list.push(nodeToInsert);
return 1;
}
reverse() {
let _temp;
for(let i = 0; i < this.list.length; i++) {
_temp = this.list[i].next;
this.list[i].next = this.list[i].previous;
this.list[i].previous = _temp;
}
_temp = this.head;
this.head = this.tail;
this.tail = _temp;
}
sort(sortingFunction) {
if(!sortingFunction) {return false;}
this.head = null;
this.tail = null;
const arr = this.list.map(x=>x);
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if(!arr[j+1]?.value) {continue;}
if (sortingFunction(arr[j].value, arr[j+1].value)) {
let tmp_next = arr[j].next;
let tmp_prev = arr[j].previous;
arr[j].next = arr[j+1].next;
arr[j].previous = arr[j+1].previous;
arr[j+1].next = tmp_next;
arr[j+1].previous = tmp_prev;
}
}
}
this.list = arr;
}
print() {
console.log(this.list);
console.log("Head:",this.head,"\nTail:",this.tail, "\nDefault is ascending order.");
}
printInOrder() {
let current = this.list[this.head];
while(current) {
console.log(current.value);
current = this.list[current.next];
}
}
}
const list = new LinkedList();
list.insert(100);
list.insert(30);
list.insert(50);
list.insert(400);
list.insert(10);
list.insert(200);
list.insert(-90);
console.log("When each node is sorted when it is inserted:")
list.print();
list.sort((a, b) => {
return a > b;
});
console.log("Now, when re-sorted:");
list.print();
这是一个利用 Array#sort()
const list = [
{ value: { num: 1, str: 'a' }, next: 3, prev: 2 },
{ value: { num: 2, str: 'e' }, next: 2, prev: null },
{ value: { num: 3, str: 'v' }, next: 0, prev: 1 },
{ value: { num: 4, str: 'g' }, next: null, prev: 0 }];
let head = 1, tail = 3;
function sort(sortingFunction) {
const sorted = list
.map((node, idx) => ({ node, idx }))
.sort(({ node: { value: a } }, { node: { value: b } }) => sortingFunction(a, b));
for (const [i, { node, idx }] of sorted.entries()) {
if (!i) {
node.prev = null;
head = idx;
} else node.prev = sorted[i - 1].idx;
if (i === sorted.length - 1) {
node.next = null;
tail = idx;
} else node.next = sorted[i + 1].idx;
}
}
const log_list = () => { let node = list[head]; while (node !== undefined) { console.log(node.value); node = list[node.next]; } };
// initial order logging
console.log('initial - ', 'head: ', head, ' tail: ', tail);
log_list();
console.log('list order: ', ...list.map((o) => o.value.num));
// sort descending
sort((a, b) => b.num - a.num);
// after sort logging
console.log('\nsorted descending - ', 'head: ', head, ' tail: ', tail);
log_list();
console.log('list order: ', ...list.map((o) => o.value.num));
// sort alphabetic
sort((a, b) => a.str.localeCompare(b.str));
// after sort logging
console.log('\nsorted alphabetic - ', 'head: ', head, ' tail: ', tail);
log_list();
console.log('list order: ', ...list.map((o) => o.value.num));
.as-console-wrapper { max-height: 100% !important; top: 0; }
以上为您提供了 javascript 引擎 (timsort in V8) 提供的优化排序的优势，但如果您想实现自己的排序，您也可以在列表内排序，而不是对包含它的数组进行排序。
您要求按值在数组中按顺序保持节点的顺序使这变得更加困难，因为交换时您需要记住将相邻节点更新为要比较的节点以保持列表连续。
这是一个快速的冒泡排序，它从头到尾遍历列表，直到没有交换发生。它接受一个回调，该回调应该 return >0 以在 a.
b 进行排序
const list = [
{ value: { num: 1, str: 'a' }, next: 3, prev: 2 },
{ value: { num: 2, str: 'e' }, next: 2, prev: null },
{ value: { num: 3, str: 'v' }, next: 0, prev: 1 },
{ value: { num: 4, str: 'g' }, next: null, prev: 0 }];
let head = 1, tail = 3;
function sort(sortingFunction) {
let flag = true, node = list[head];
while (flag) {
flag = false;
while (node.next !== null) {
if (sortingFunction(node.value, list[node.next].value) > 0) {
const prev_node = list[node.prev];
const _node = list[node.next];
const next_node = list[_node.next];
const temp = node.prev;
if (prev_node) prev_node.next = node.next;
node.prev = node.next;
node.next = _node.next;
if (next_node) next_node.prev = _node.prev;
_node.next = _node.prev;
_node.prev = temp;
if (_node.prev === null) head = node.prev;
if (node.next === null) tail = _node.next;
flag = true;
} else {
node = list[node.next];
}
}
node = list[head];
}
}
const log_list = () => { let node = list[head]; while (node !== undefined) { console.log(node.value); node = list[node.next]; } };
// // initial order logging
console.log('initial - ', 'head: ', head, ' tail: ', tail);
log_list();
console.log('list order: ', ...list.map((o) => o.value.num));
// sort numeric
sort((a, b) => b.num - a.num);
// after sort logging
console.log('\nsorted descending - ', 'head: ', head, ' tail: ', tail);
log_list();
console.log('list order: ', ...list.map((o) => o.value.num));
// sort str
sort((a, b) => a.str.localeCompare(b.str));
// after sort logging
console.log('\nsorted alphabetic - ', 'head: ', head, ' tail: ', tail);
log_list();
console.log('list order: ', ...list.map((o) => o.value.num));
.as-console-wrapper { max-height: 100% !important; top: 0; }
您的 sort 函数中存在一些问题：
内部循环查看按索引连续的对，但它应该比较按链接[=76]连续的对=]，因为这是您应该决定是否需要交换的地方。
您的代码交换涉及 4 个链接分配，但实际上涉及 6 个链接：
this.head和this.tail设置为null但再也没有设置为适当的值。
你的代码有一个很好的 iterator() 方法，我想在你的冒泡排序中重用它，但为了避免它会使用最近交换更改的 next 引用，我建议对该生成器进行微小的更改，以便它不受此影响：
* iterator() {
let current = this.head;
while(current != undefined) {
const node = this.list[current];
current = node.next; // <--- move this here!
yield node; // ...so the consumer can safely alter node.next
}
}
现在您的 sort 方法可以变成：
sort(sortingFunction) {
if (!sortingFunction) return;
for (let i = 0; i < this.list.length; i++) {
let prevNode = null;
// Iterate in the current order, so by following the links:
for (let currNode of this.iterator()) { // Requires the change in the generator
if (prevNode && sortingFunction(currNode.value, prevNode.value)) {
// Get the indexes of the current pair of nodes:
let currIndex = prevNode.next;
let prevIndex = currNode.previous;
// Update links from outer neighbors to these two nodes
if (currNode.next != null) this.list[currNode.next].previous = prevIndex;
else this.tail = prevIndex;
if (prevNode.previous != null) this.list[prevNode.previous].next = currIndex;
else this.head = currIndex;
// Update links from these two nodes to outer neighbors:
currNode.previous = prevNode.previous;
prevNode.next = currNode.next;
// Update links between the two nodes themselves:
prevNode.previous = currIndex;
currNode.next = prevIndex;
} else {
prevNode = currNode;
}
}
}
}
这是我忍不住在 forEachInOrder 和 some 中使用您的生成器函数的整个脚本：
class LinkedList {
constructor(sortingFunction) {
this.head;
this.tail;
this.list = [];
this.sortingFunction = sortingFunction ?? ((a,b) => {return a < b});
}
some(func) { // I adapted this to use the iterator
for (const node of this.iterator()) {
if (func(node)) {
return node.previous == null ? this.head : this.list[node.previous].next;
}
}
return -1;
}
forEachInOrder(func) { // I adapted this to use the iterator
for (const node of this.iterator()) func(node);
}
* iterator() {
let current = this.head;
while(current != undefined) {
const node = this.list[current];
current = node.next; // <--- move this here!
yield node;
}
}
insert(value) {
if(!this.list.length) {
this.head = 0;
this.tail = 0;
this.list.push({value, next:null,previous:null});
return 0;
}
let nodeToInsert = {value, next:null,previous:null};
let indexToInsert = this.head;
let nthnode = this.list[this.head];
while(nthnode && this.sortingFunction(nthnode.value, value)) {
indexToInsert = nthnode.next;
nthnode = this.list[indexToInsert];
}
if(indexToInsert === null) {
// new tail (biggest)
nodeToInsert.previous = this.tail;
this.list[this.tail].next = this.list.length;
this.tail = this.list.length;
} else if(indexToInsert === this.head) {
// new head (smallest)
nodeToInsert.next = this.head;
this.list[this.head].previous = this.list.length;
this.head = this.list.length;
} else {
nodeToInsert.next = indexToInsert;
if(this.list[this.list[indexToInsert].previous]?.next != undefined) {
this.list[this.list[indexToInsert].previous].next = this.list.length;
}
nodeToInsert.previous = this.list[indexToInsert].previous;
this.list[indexToInsert].previous = this.list.length;
}
this.list.push(nodeToInsert);
return 1;
}
reverse() { // I adapted this to use the (modified) iterator
for (const node of this.iterator()) {
[node.next, node.previous] = [node.previous, node.next];
}
[this.head, this.tail] = [this.tail, this.head];
}
sort(sortingFunction) {
if (!sortingFunction) {return false;}
for (let i = 0; i < this.list.length; i++) {
let prevNode = null;
// Iterate in the current order, so by following the links:
for (let currNode of this.iterator()) { // Requires the change in the generator
if (prevNode && sortingFunction(currNode.value, prevNode.value)) {
// Get the indexes of the current pair of nodes:
let currIndex = prevNode.next;
let prevIndex = currNode.previous;
// Update links from outer neighbors to these two nodes
if (currNode.next != null) this.list[currNode.next].previous = prevIndex;
else this.tail = prevIndex;
if (prevNode.previous != null) this.list[prevNode.previous].next = currIndex;
else this.head = currIndex;
// Update links from these two nodes to outer neighbors:
currNode.previous = prevNode.previous;
prevNode.next = currNode.next;
// Update links between the two nodes themselves:
prevNode.previous = currIndex;
currNode.next = prevIndex;
} else {
prevNode = currNode;
}
}
}
}
print() { // I adapted this a bit to get more condense output and add a call to printInOrder
console.log(JSON.stringify(this.list));
console.log("Head:",this.head,"\nTail:",this.tail, "\nDefault is ascending order.");
this.printInOrder();
}
printInOrder() { // I adapted this to use your nice iterator()
console.log(...Array.from(this.iterator(), node => node.value));
}
}
const list = new LinkedList();
list.insert(100);
list.insert(30);
list.insert(50);
list.insert(400);
list.insert(10);
list.insert(200);
list.insert(-90);
console.log("When each node is sorted when it is inserted:")
list.print();
list.sort((a, b) => {
return a > b;
});
console.log("Now, when re-sorted:");
list.print();
再注意一点：您的 sortingFunction return 是一个布尔值（指示两个给定参数的顺序是否正确），这与可以传递给本机的比较器函数不同Array#sort 方法：需要 return 一个数字，它允许通过 returning a negative[=76= 来指示参数的顺序是否正确] 值，等于 0 和反转 positive 值。您可能希望在实施中遵循相同的“合同”。
使用更高效的排序算法
您可以进行 O(nlogn) 归并排序，而不是 O(n²) 冒泡排序。
我在这里添加了一个mergeSort方法，以及一个创建分区的辅助方法：splice。它从链接列表中提取一个部分（删除它）并将其 return 作为一个新实例。为了使这种拼接工作良好，它像共享内存池一样使用 相同的 列表，但有自己的 head 和 tail。这意味着列表的长度不再是链表大小的指示，因此一些引用 length 的代码必须更改，例如冒泡排序例程中的外部循环：
class LinkedList {
constructor(sortingFunction) {
this.head = null; // Initialise with null explicitly
this.tail = null;
this.list = [];
this.sortingFunction = sortingFunction ?? ((a,b) => {return a < b});
}
some(func) { // I adapted this to use the iterator
for (const node of this.iterator()) {
if (func(node)) {
return node.previous == null ? this.head : this.list[node.previous].next;
}
}
return -1;
}
forEachInOrder(func) { // I adapted this to use the iterator
for (const node of this.iterator()) func(node);
}
* iterator() {
let current = this.head;
while(current != undefined) {
const node = this.list[current];
current = node.next; // <--- move this here!
yield node;
}
}
insert(value) {
if (this.head == null) { // Avoid using list.length
this.head = this.list.length; // While here it is appropriate to use list.length!
this.tail = this.list.length;
this.list.push({value, next:null,previous:null});
return 0;
}
let nodeToInsert = {value, next:null,previous:null};
let indexToInsert = this.head;
let nthnode = this.list[this.head];
while(nthnode && this.sortingFunction(nthnode.value, value)) {
indexToInsert = nthnode.next;
nthnode = this.list[indexToInsert];
}
if(indexToInsert === null) {
// new tail (biggest)
nodeToInsert.previous = this.tail;
this.list[this.tail].next = this.list.length;
this.tail = this.list.length;
} else if(indexToInsert === this.head) {
// new head (smallest)
nodeToInsert.next = this.head;
this.list[this.head].previous = this.list.length;
this.head = this.list.length;
} else {
nodeToInsert.next = indexToInsert;
this.list[this.list[indexToInsert].previous].next = this.list.length;
nodeToInsert.previous = this.list[indexToInsert].previous;
this.list[indexToInsert].previous = this.list.length;
}
this.list.push(nodeToInsert);
return 1;
}
reverse() {
for (const node of this.iterator()) {
[node.next, node.previous] = [node.previous, node.next];
}
[this.head, this.tail] = [this.tail, this.head];
}
sort(sortingFunction) {
if (!sortingFunction) return false;
let dirty = true;
while (dirty) { // Removed dependency on length
dirty = false;
let prevNode = null;
// Iterate in the current order, so by following the links:
for (const currNode of this.iterator()) { // Requires the change in the generator
if (prevNode && sortingFunction(currNode.value, prevNode.value)) {
// Get the indexes of the current pair of nodes:
let currIndex = prevNode.next;
let prevIndex = currNode.previous;
// Update links from outer neighbors to these two nodes
if (currNode.next != null) this.list[currNode.next].previous = prevIndex;
else this.tail = prevIndex;
if (prevNode.previous != null) this.list[prevNode.previous].next = currIndex;
else this.head = currIndex;
// Update links from these two nodes to outer neighbors:
currNode.previous = prevNode.previous;
prevNode.next = currNode.next;
// Update links between the two nodes themselves:
prevNode.previous = currIndex;
currNode.next = prevIndex;
dirty = true;
} else {
prevNode = currNode;
}
}
}
}
// Added this method which can also be of use for algorithms that use partitioning
splice(head, tail) {
// Remove this slice from the current linked list
if (tail != this.tail) this.list[this.list[tail].next].previous = this.list[head].previous;
else this.tail = this.list[head].previous;
if (head != this.head) this.list[this.list[head].previous].next = this.list[tail].next;
else this.head = this.list[tail].next;
this.list[tail].next = null;
this.list[head].previous = null;
// Wrap the removed slice into a new linked list instance, but one that shares the memory list
let slice = new LinkedList(this.sortingFunction);
slice.list = this.list;
slice.head = head;
slice.tail = tail;
return slice;
}
mergeSort(sortingFunction) {
if (!sortingFunction || this.head == null || this.head == this.tail) return; // base case
// Find last node of first half
let fastIter = this.iterator();
fastIter.next();
let half;
for (half of this.iterator()) {
if (fastIter.next().done || fastIter.next().done) break;
}
// Split list into two halves
let right = this.splice(half.next, this.tail);
let left = this; // ...what remains after the splice.
// Recursively sort the two shorter lists
left.mergeSort(sortingFunction);
right.mergeSort(sortingFunction);
// Make sure the "left" sublist is the one with a head value that comes before the other head value
if (sortingFunction(this.list[right.head].value, this.list[left.head].value)) [left, right] = [right, left];
// Merge the two sorted lists
let tailIndex = left.head;
let otherIndex = right.head;
for (let currIndex = this.list[tailIndex].next; currIndex != null || otherIndex != null; currIndex = this.list[tailIndex].next) {
if (currIndex == null || otherIndex != null && sortingFunction(this.list[otherIndex].value, this.list[currIndex].value)) {
this.list[tailIndex].next = otherIndex;
this.list[otherIndex].previous = tailIndex;
tailIndex = otherIndex;
otherIndex = currIndex;
} else {
tailIndex = currIndex;
}
}
this.head = left.head;
this.tail = tailIndex;
}
print() { // I adapted this a bit to get more condense output and add a call to printInOrder
console.log(JSON.stringify(this.list));
console.log("Head:",this.head,"\nTail:",this.tail, "\nDefault is ascending order.");
this.printInOrder();
}
printInOrder() { // I adapted this to use your nice iterator()
console.log(...Array.from(this.iterator(), node => node.value));
}
}
const linked = new LinkedList();
linked.insert(100);
linked.insert(30);
linked.insert(50);
linked.insert(400);
linked.insert(10);
linked.insert(200);
linked.insert(-90);
console.log("When each node is sorted when it is inserted:")
linked.print();
linked.mergeSort((a, b) => {
return a > b;
});
console.log("Now, when re-sorted:");
linked.print();