插入排序以对链接列表中的节点进行排序

Question

我试图使用插入排序方法对链接列表中的节点进行排序。我已经调整了代码很多次，但我似乎不太明白，不断得到不同类型的结果，没有

排序。

这是代码：

Node* sort_list(Node* head)
{
    Node* node_ptr = NULL;
    for(Node* i = head->next; i->next != NULL; i = i->next){
            if (i->key < head->key) {
                node_ptr = i;
                head = head->next;
    }
    }
    return node_ptr;
}

Answer 1

这是一个家庭作业问题，所以我不会直接编写代码，而是首先指出你哪里出错了。

在像插入排序这样的算法中，显然需要在不合适的元素之间进行某种交换（需要插入）。因此，首先考虑如何交换数组的两个元素。特别注意一个是头或一个是尾的情况。

你

实现的代码没有任何指针交换的痕迹，所以这就是你错的地方。

接下来，您必须考虑我们需要排序的情况。在这种情况下，它相当简单。如果当前元素和下一个元素按排序顺序排列（假设升序，则当前元素<下一个）。然后什么也不需要做，只需使下一个成为电流。>

然后，您可以明显推断出违反这种情况是需要交换元素的时候。交换后（适当注意指针在排序后的位置和位置），重复该过程，直到您遇到空墙。

PS：这可能是另一个SO问题的重复。