c - 用c编写的listSort函数工作错误

Question

我编写了一个使用 SelectionSort 方法对链接列表进行排序的函数。但我的逻辑有问题，但无法解决。我从调试器中发现，第二个 for 循环在第二次迭代后变成了无限循环。但我不明白为什么。在调试器中，我看到列表中最后一个节点中有 NULL。

void listSort(node_pointer node) {

for (; node != NULL; node = node->next)
{
    node_pointer min = node;
    printf("node: %d\n", node);
    for (node_pointer j = node->next; j != NULL; j = j->next) {

        printf("next node address%d \n", node);
        if (j->value < min->value) {
            min = j;

        }

        node_pointer tmp = node;
        node = min;
        tmp->next = node->next; 
        min->next = tmp; 

    }

}

}

这里是所有需要的代码:

http://pastebin.com/NaUMtLv2

Answer 1

您正在交换内部 for 循环内的节点，这是错误的。在选择排序中，交换是在外部 for 循环中完成的。逻辑如下:我们选择一个元素，将其视为最小值，然后将所有接下来的元素与它进行比较以找到最小值。然后我们将这个新的最小值与最初考虑的最小值元素交换。因此，正确的代码是:

void listSort(node_pointer node) {

    for (; node != NULL; node = node->next) {
        node_pointer min = node;
        printf("node: %d\n", node);

        for (node_pointer j = node->next; j != NULL; j = j->next) {
            printf("next node address%d \n", node);
            if (j->value < min->value) {
                min = j;
            }
        }

        node_pointer tmp;
        //Swap only values, no need to break the structure of nodes
        tmp->value = node->value;
        node->value = min->value;
        min->value = tmp->value; 
    }
}