我很难理解这段代码如何对链表进行排序。

node* sort(node *head) {
    struct node* point;
    struct node* small;
    struct node* stay;
    int temp;
    stay = head;

    while (stay != NULL) {
        point = stay->next;
        small = stay;
        while (point != NULL) {
            if (point->data < small->data) {
                small = point;
            }
            point = point->next;
        }
        temp = stay->data;
        stay->data = small->data;
        small->data = temp;
        stay = stay->next;
    }
    return head;
}


我尝试在纸上进行跟踪,并且我的思考过程使我相信,如果我们要运行此功能,则列表将按以下方式排序:

5 -> 2 -> 1 -> 3
2 -> 5 -> 1 -> 3
2 -> 1 -> 5 -> 3
2 -> 1 -> 3 -> 5


我的理解是,第一个while循环每次都会遍历列表,直到到达最后一个节点,而第二个while循环比较两个节点pointsmall。如果需要交换数据,则下一个代码块实际上会进行交换,然后stay移至列表中的下一个节点,其中point是此后的节点。代码如何知道要回到第一个节点并进行比较,以使2与1切换?谢谢您的帮助。

最佳答案

这段代码实现了选择排序:从staysmall == stay)开始,它搜索紧随其后的最小值,并在找到(即到达列表末尾)交换时立即搜索。

请注意,在stay最小的情况下,它会与自身交换(您可以在if(small != stay) { /* swap */ }之前通过适当的测试来防止这种情况发生。

因此,实际上,您的排序步骤如下:5-> 2-> 1-> 3
1-> 2-> 5-> 3
1-> 2-> 5-> 3(第二个节点已互换)
1-> 2-> 3-> 5
1-> 2-> 3-> 5(第四个节点已互换)

实际上,还有一步,因为最后一个节点总是与其自身交换(while(stay != NULL)仅在最后一个节点之后停止)。

因为stay最初设置为head,所以从头开始(在外循环的第一轮中)就正确对待了第一个节点。

10-08 11:29