javascript - 对链接数组进行排序

语境:
我有一个 LinkedList 类，它包含并以正确的顺序自动插入节点。请注意，这是一个链表数据结构(保存节点/元素的数组代表 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 )。
我的代码
这是到目前为止 re-sort 函数的代码，该函数目前使用冒泡排序但不起作用:

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});
   }

   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();

最佳答案

您的 sort 中的一些问题功能:

内部循环查看按索引连续的对，但它应该比较按链接连续的对，因为这是您应该决定是否需要交换的地方。

您的代码交换涉及 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返回一个 bool 值(指示两个给定参数的顺序是否正确)，这与可以传递给 native Array#sort 的比较器函数不同方法:期望返回一个数字，该数字允许通过返回负值、等于 0 和反转正值来指示参数是否按正确顺序排列。您可能希望在实现中遵循相同的“契约(Contract)”。
使用更高效的排序算法
代替 O(n²) 冒泡排序，您可以使用 O(nlogn) 合并排序。
我在这里添加了一个 mergeSort方法和一个辅助方法来进行分区:splice .它从链表中提取一个部分(删除它)并将其作为新实例返回。为了使这种拼接工作正常，它使用与共享内存池相同的列表，但有自己的 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();

关于javascript - 对链接数组进行排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/69691689/

javascript - 对链接数组进行排序

上一篇：javascript - Date-fns 格式的距离不是用正确的词

下一篇：javascript - Fabric.js Canvas - 使一种对象始终位于另一种对象下方