对链接数组进行排序
Alp*_*owl 5 javascript arrays sorting linked-list
语境：
我有一个LinkedList类，其中包含并按正确的顺序自动插入节点。请注意，这是一个链表数据结构（保存节点/元素的数组代表 RAM，指针 - head、tail以及 和next代表prevRAM 中的地址（但在本例中，它们是数组的索引，其中节点被保留）。
例如
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，然后停止。
注意：当我插入一个新节点时，它会被推到数组的末尾，但其相邻节点的指针会发生变化（sonext和），以便从到 的prev类似火车的路径包括中的所有节点特定顺序（默认为升序）。所以插入的节点总是在末尾，只有它的指针表示它的位置。headtail
我的问题：
这是我的问题：（请参阅问题末尾的代码）
想象一下，我创建了一个链表，默认排序（升序），并且我有值 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 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;
}
}
您的功能中的一些问题sort：
- \n
内部循环查看按索引连续的对，但它应该比较按链接连续的对，因为这是您应该决定是否需要交换的地方。
\n \n您的代码的交换涉及 4 个链接分配，但实际上涉及6 个链接：
\n \n
- \n
this.head并被this.tail设置为null但永远不会再次设置为适当的值。 \n
您的代码有一个很好的iterator()方法，我想在您的冒泡排序中重用该方法，但为了避免它将使用next最近交换已更改的引用，我建议对该生成器进行微小的更改，以便它将免受影响那：
* iterator() {\n let current = this.head;\n while(current != undefined) {\n const node = this.list[current];\n current = node.next; // <--- move this here!\n yield node; // ...so the consumer can safely alter node.next\n }\n }\n现在你的sort方法可以变成：
sort(sortingFunction) {\n if (!sortingFunction) return;\n \n for (let i = 0; i < this.list.length; i++) {\n let prevNode = null;\n // Iterate in the current order, so by following the links:\n for (let currNode of this.iterator()) { // Requires the change in the generator \n if (prevNode && sortingFunction(currNode.value, prevNode.value)) {\n // Get the indexes of the current pair of nodes:\n let currIndex = prevNode.next;\n let prevIndex = currNode.previous;\n // Update links from outer neighbors to these two nodes\n if (currNode.next != null) this.list[currNode.next].previous = prevIndex;\n else this.tail = prevIndex;\n if (prevNode.previous != null) this.list[prevNode.previous].next = currIndex;\n else this.head = currIndex;\n // Update links from these two nodes to outer neighbors:\n currNode.previous = prevNode.previous;\n prevNode.next = currNode.next;\n // Update links between the two nodes themselves:\n prevNode.previous = currIndex;\n currNode.next = prevIndex;\n } else {\n prevNode = currNode;\n }\n }\n }\n }\n这是整个脚本，我无法抗拒在forEachInOrder和中使用生成器函数some：
* iterator() {\n let current = this.head;\n while(current != undefined) {\n const node = this.list[current];\n current = node.next; // <--- move this here!\n yield node; // ...so the consumer can safely alter node.next\n }\n }\n还要注意一点：您sortingFunction返回一个布尔值（指示两个给定参数的顺序是否正确），这与可以传递给本机方法的比较器函数不同Array#sort：预计返回一个数字，这允许通过返回负值、等于 0 和反转正值来指示参数的顺序是否正确。您可能希望在实施中遵循相同的“合同”。
使用更高效的排序算法
\n您可以选择 O(nlogn) 合并排序，而不是 O(n\xc2\xb2) 冒泡排序。
\n我在这里添加了一个mergeSort方法和一个辅助方法来创建分区：splice。它从链表中提取一个部分（将其删除）并将其作为新实例返回。为了使这种拼接正常工作，它使用与共享内存池相同的head列表，但具有自己的和tail。这意味着列表的长度不再指示链接列表的大小，因此引用的一些代码length必须更改，例如冒泡排序例程中的外循环：
sort(sortingFunction) {\n if (!sortingFunction) return;\n \n for (let i = 0; i < this.list.length; i++) {\n let prevNode = null;\n // Iterate in the current order, so by following the links:\n for (let currNode of this.iterator()) { // Requires the change in the generator \n if (prevNode && sortingFunction(currNode.value, prevNode.value)) {\n // Get the indexes of the current pair of nodes:\n let currIndex = prevNode.next;\n let prevIndex = currNode.previous;\n // Update links from outer neighbors to these two nodes\n if (currNode.next != null) this.list[currNode.next].previous = prevIndex;\n else this.tail = prevIndex;\n if (prevNode.previous != null) this.list[prevNode.previous].next = currIndex;\n else this.head = currIndex;\n // Update links from these two nodes to outer neighbors:\n currNode.previous = prevNode.previous;\n prevNode.next = currNode.next;\n // Update links between the two nodes themselves:\n prevNode.previous = currIndex;\n currNode.next = prevIndex;\n } else {\n prevNode = currNode;\n }\n }\n }\n }\n