双向链表插入排序实现问题：陷入冒泡排序逻辑无法跳出

我正在尝试实现双向链表（Doubly Linked List，DLL）的插入排序函数，但始终摆脱不了冒泡排序的逻辑。需求要求每次“交换”迭代后打印整个DLL，我在for循环里加了打印语句，但当前代码只会逐个交换，没法跳过较大节点，本质是冒泡排序而非插入排序，求帮助或建议。

实现代码 #

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]

问题分析与修正方案 #

你的代码核心问题是没有真正执行插入排序的逻辑：只做了遍历判断，没有将当前节点从原位置移除，再插入到正确的位置，反而不断重置j到cu->prev，导致逻辑变成了类似冒泡的相邻交换。

插入排序的核心思路是：将当前未排序节点，向前遍历已排序区间，找到第一个不大于它的节点，把它插入到该节点的后面（或链表头部如果所有已排序节点都更大）。对于双向链表，需要处理节点的prev和next指针，步骤如下：

修正后的代码示例 #

void insertionSort(ofstream &fout){
    if(head == nullptr || head->next == nullptr){
      return;
    }

    node *current = head->next;
    while(current != nullptr){
        // 保存当前节点的下一个节点，避免移动后丢失遍历路径
        node *next_node = current->next;
        node *j = current->prev;

        // 先把当前节点从原位置断开
        current->prev->next = current->next;
        if(current->next != nullptr){
            current->next->prev = current->prev;
        }

        // 向前遍历已排序区间，找到插入位置
        while(j != nullptr && j->data > current->data){
            j = j->prev;
        }

        // 将当前节点插入到正确位置
        if(j == nullptr){
            // 插入到链表头部
            current->next = head;
            head->prev = current;
            current->prev = nullptr;
            head = current;
        } else {
            current->next = j->next;
            if(j->next != nullptr){
                j->next->prev = current;
            }
            j->next = current;
            current->prev = j;
        }

        // 每次插入操作完成后打印链表
        cout << print(head) << endl;
        current = next_node;
    }
}

关键修正点说明 #

1. 保存后续节点：移动当前节点前记录current->next，避免移动后丢失未排序部分的遍历入口。
2. 断开原位置连接：修改当前节点前后节点的指针，将其从链表临时移除，为插入做准备。
3. 正确寻找插入位置：从current->prev向前遍历，直到找到第一个不大于当前节点值的节点，或到达链表头部。
4. 插入节点：根据j是否为空，决定插入到头部还是j的后方，同时正确设置双向指针，保证链表结构完整。
5. 调整打印时机：每次完成插入操作后打印链表，符合需求的同时避免无效输出。

修正后的输出示例 #

插入排序直接将节点插入到正确位置，输出步骤会比冒泡排序少很多，针对初始链表的输出大致为：

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

内容的提问来源于stack exchange，提问作者yuujitran