所以我理解插入排序是如何工作的，但试图将这个概念应用于双链表会让我的大脑崩溃。有人能解释一下算法在这种情况下是如何工作的吗？在给定预先存在的链表的情况下，我无法理解每个节点之间的比较后节点指针是如何变化的。我目前在Java中工作，参考以下代码示例：https://www.geeksforgeeks.org/insertion-sort-doubly-linked-list/
下面是两个函数，sortedInsert和insertionSort，其中前者是辅助函数。
sortedInsert中的else子句在做什么？还有为什么作者"；删除所有链接以创建当前的"链接"；在insertionSort函数中？
// function to insert a new node in sorted way in
// a sorted doubly linked list
static Node sortedInsert(Node head_ref, Node newNode)
{
Node current;
// if list is empty
if (head_ref == null)
head_ref = newNode;
// if the node is to be inserted at the beginning
// of the doubly linked list
else if ((head_ref).data >= newNode.data)
{
newNode.next = head_ref;
newNode.next.prev = newNode;
head_ref = newNode;
}
else
{
current = head_ref;
// locate the node after which the new node
// is to be inserted
while (current.next != null &&
current.next.data < newNode.data)
current = current.next;
//Make the appropriate links /
newNode.next = current.next;
// if the new node is not inserted
// at the end of the list
if (current.next != null)
newNode.next.prev = newNode;
current.next = newNode;
newNode.prev = current;
}
return head_ref;
}
// function to sort a doubly linked list using insertion sort
static Node insertionSort(Node head_ref)
{
// Initialize 'sorted' - a sorted doubly linked list
Node sorted = null;
// Traverse the given doubly linked list and
// insert every node to 'sorted'
Node current = head_ref;
while (current != null)
{
// Store next for next iteration
Node next = current.next;
// removing all the links so as to create 'current'
// as a new node for insertion
current.prev = current.next = null;
// insert current in 'sorted' doubly linked list
sorted=sortedInsert(sorted, current);
// Update current
current = next;
}
// Update head_ref to point to sorted doubly linked list
head_ref = sorted;
return head_ref;
}
else子句在sortedInsert中做什么？
前两个块(在else之前(处理两种边界情况：
- 列表为空时该怎么办
- 如果必须在列表的第一个节点之前插入新节点，该怎么办
因此else块处理所有其他情况，即新节点将不是列表的新头，但当前头节点将保持原样。
它首先找到一个节点(current(，对于该节点，下一个节点持有的值应在新节点的值之后(或者，它后面没有下一个节点(。因此(由于前面的边界情况(，我们知道current节点的值应该在新节点的值之前。因此，如果我们找到这样一个current，我们就知道新节点必须插入在current和current.next之间。
简而言之，while循环找到插入newNode的位置。这是任何插入排序算法中的一个典型阶段。
评论的部分"；使适当的链接"；然后将完成多达4个重新布线任务。
下面是一个例子。假设链表在sortedInsert被一个值为25的新节点调用时有3个值10、20和30：
head_ref
↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│data: 10 │ │data: 20 │ │data: 30 │
│next: ────────> │next: ────────> │next: null │
│prev: null │ │prev: ─┐ │ │prev: ─┐ │
└───────────┘ └───────│───┘ └───────│───┘
^ │ ^ │
└─────────────┘ └─────────────┘
┌───────────┐
│data: 25 │
│next: null │
│prev: null │
└───────────┘
↑
newNode
因为head_ref不为空，并且head_ref.data < newNode.data，所以我们在else块中定义了current。while循环将迭代一次，并使current引用在此点停止：
head_ref current
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│data: 10 │ │data: 20 │ │data: 30 │
│next: ────────> │next: ────────> │next: null │
│prev: null │ │prev: ─┐ │ │prev: ─┐ │
└───────────┘ └───────│───┘ └───────│───┘
^ │ ^ │
└─────────────┘ └─────────────┘
现在CCD_ 19，我们已经找到了CCD_ 20的插入点。
第一次重新布线是用newNode.next = current.next完成的，结果是：
head_ref current
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│data: 10 │ │data: 20 │ │data: 30 │
│next: ────────> │next: ────────> │next: null │
│prev: null │ │prev: ─┐ │ │prev: ─┐ │
└───────────┘ └───────│───┘ └───────│───┘
^ │ ^ │ ^
└─────────────┘ └─────────────┘ │
│
┌───────────┐ │
│data: 25 │ │
│next: ────────────┘
│prev: null │
└───────────┘
↑
newNode
下一次重新布线仅在current不是尾节点时发生：newNode.next.prev = newNode，这就是我们的情况：
head_ref current
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│data: 10 │ │data: 20 │ │data: 30 │
│next: ────────> │next: ────────> │next: null │
│prev: null │ │prev: ─┐ │ │prev: ─┐ │
└───────────┘ └───────│───┘ └───────│───┘
^ │ │ ^
└─────────────┘ │ │
│ │
┌───────────┐ │ │
│data: 25 │ <──┘ │
│next: ────────────┘
│prev: null │
└───────────┘
↑
newNode
在这个阶段，新节点将正确地与它后面的节点(值为30的节点(链接。现在再保留两个赋值，以在新节点(值为20的节点(之前的节点之间建立链接。第一个赋值是current.next = newNode，结果是：
head_ref current
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│data: 10 │ │data: 20 │ │data: 30 │
│next: ────────> │next: ────────┐ │next: null │
│prev: null │ │prev: ─┐ │ │ │prev: ─┐ │
└───────────┘ └───────│───┘ │ └───────│───┘
^ │ │ │ ^
└─────────────┘ │ │ │
v │ │
┌───────────┐ │ │
│data: 25 │ <─┘ │
│next: ───────────┘
│prev: null │
└───────────┘
↑
newNode
最后用newNode.prev = current:完成重新布线
head_ref current
↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐
│data: 10 │ │data: 20 │ │data: 30 │
│next: ────────> │next: ────────┐ │next: null │
│prev: null │ │prev: ─┐ │ │ │prev: ─┐ │
└───────────┘ └───────│───┘ │ └───────│───┘
^ │ ^ │ │ ^
└─────────────┘ │ │ │ │
│ v │ │
│ ┌───────────┐ │ │
│ │data: 25 │ <─┘ │
│ │next: ───────────┘
│ │prev: ─┐ │
│ └───────│───┘
└─────────┘
↑
newNode
这也没什么不同：
head_ref current newNode
↓ ↓ ↓
┌───────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐
│data: 10 │ │data: 20 │ │data: 25 │ │data: 30 │
│next: ────────> │next: ────────> │next: ────────> │next: null │
│prev: null │ │prev: ─┐ │ │prev: ─┐ │ │prev: ─┐ │
└───────────┘ └───────│───┘ └───────│───┘ └───────│───┘
^ │ ^ │ ^ │
└─────────────┘ └─────────────┘ └─────────────┘
调用方返回头引用head_ref，该引用实际上没有更改。只有当新节点成为列表中的第一个节点时，它才会发生变化，而这正是前两个if块所处理的。
还有为什么作者"删除所有链接以创建当前的"链接"；在
insertionSort函数中？
这只是从输入列表中提取节点的一种干净方法：它不再是输入列表的一部分，并准备成为新列表(sorted(的一部分。从技术上讲，这对于上述情况来说是不必要的，因为newNode的prev和next成员无论如何都会得到新的引用，但对于前两种边界情况来说，这仍然很重要，因为在实际需要的地方，我们不会分配null值。
或者，您可以在sortedInsert中指定这些null引用。
希望这能澄清。