双向链表的插入排序如何跳过节点

Question

尝试实现双向链表的插入排序功能，无法摆脱冒泡排序

在“交换”的每次迭代之后，它应该打印整个 DLL，因此为什么我在 for 循环的中间有一个打印，但是我无法让代码跳过更大的节点，它们只是swap，不是插入排序而是冒泡排序。有什么帮助或建议吗？

void insertionSort(ofstream &fout){
    node *cu, *j, *temp;

    int length;
    length = getLength(head);
    if(head == nullptr || head->next == nullptr){
      return;
    }
    for(cu = head->next; cu != nullptr; cu = cu->next){
      temp = cu;
      j = cu->prev;
      while(j != nullptr && j->data > temp->data){
  
      cout << print(head) << endl;
      j = cu->prev;
      }
    } 

}

我要排序的双向链表：

40 34 49 13 21 1 3

我的输出：

[34,40,49,13,21,1,3]
[34,40,13,49,21,1,3]
[34,13,40,49,21,1,3]
[13,34,40,49,21,1,3]
[13,34,40,21,49,1,3]
[13,34,21,40,49,1,3]
[13,21,34,40,49,1,3]
[13,21,34,40,1,49,3]
[13,21,34,1,40,49,3]
[13,21,1,34,40,49,3]
[13,1,21,34,40,49,3]
[1,13,21,34,40,49,3]
[1,13,21,34,40,3,49]
[1,13,21,34,3,40,49]
[1,13,21,3,34,40,49]
[1,13,3,21,34,40,49]
[1,3,13,21,34,40,49]

Answer 1

一些问题：

• 您共享的代码不会改变链接列表：没有分配给

  prev

  ，也没有分配给

  next

  成员，也没有分配给

  head

  。

• while

  循环将有成为无限循环的风险，因为

  j

  的值不会改变。它总是

  cu->prev

  .

• getLength

  被调用，但结果

  length

  从未被使用。没有必要打这个电话。

• 永远不会使用参数

  fout

  。相反，该函数应将

  head

  作为参数。

• 算法应该extract

  cu

  节点一旦决定它应该移动，一旦找到插入点，它应该inserted回到列表中。如果这个节点移动到列表的最开始，

  head

  应该被更新。

这是您的代码的更正和完成：

void insertionSort(node* &head) {
    node *cu, *j, *temp;

    if (head == nullptr) return;
    for (cu = head->next; cu != nullptr; cu = cu->next) {
        temp = cu;
        j = cu->prev;
        if (j->data > temp->data) {
            cu = j; // Prepare for next iteration
            // Remove temp from the list
            j->next = temp->next;
            if (temp->next) temp->next->prev = j;
            // Find insertion point
            while (j != nullptr && j->data > temp->data) {
                j = j->prev;
            }
            // Insert temp back into list
            temp->prev = j;
            temp->next = j ? j->next : head;
            if (j) j->next = temp;
            else   head = temp;
            if (temp->next) temp->next->prev = temp;
        }
    }
}