0

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

继承人的代码:

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

1 回答 1

0

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

在类似算法的插入排序中,显然需要在不合适的元素之间进行某种交换(即需要插入)。因此,首先要考虑如何交换数组的两个元素。特别注意一头或一尾的情况。

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

接下来你必须考虑我们需要排序的情况。在这种情况下,它相当简单。如果当前元素和下一个元素是有序的(假设升序,当前<下一个)。然后什么都不需要做,只需让下一个成为当前的。

那么您显然可以推断出违反这种情况的情况是您需要交换元素。交换后(适当注意指针的位置和排序后的位置),重复该过程直到碰到空墙。

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

于 2013-10-24T03:14:48.063 回答