c-理解链表排序

Question

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

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环路比较两个节点point和small。如果数据需要切换，则下一个代码块实际进行切换，然后stay移动到列表中的下一个节点，point是之后的节点。代码如何知道返回到第一个节点并不断进行比较，从而使2与1切换？谢谢你的帮助。

Answer 1

这段代码实现了选择排序：从stay(small == stay(开始，它搜索后面的最小值和一找到(即到达列表末尾(的交换。

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

因此，实际上，您的排序步骤如下：

5->2->1->31->2->5->31->2->5->3(第二个节点与自身交换(1->2->3->51->2->3->5(与自身交换的第四个节点(

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

第一个节点从一开始就被正确地处理(在外循环的第一次运行中(，因为stay最初被设置为head。