c - 对链接列表进行排序

Question

想要对链接列表进行排序，但我的代码不想:)

这里是:

void swap(element *p,element*q) {
    int aux;

    aux=p->info;
    p->info=q->info;
    q->info=aux;
}

void ordonare(element *lista) {
    element *p,*q;

    for(p=lista; p!=NULL; p=p->urmator) {
        if(p->info>p->urmator->info) {
            swap(p,p->urmator);
        }
    }
}

如果这有效，它只会对值进行排序，而不会更改节点的位置。 我似乎在这里找不到错误，如果您也能指出节点将改变其位置的解决方案，我将不胜感激。

谢谢， 拉杜

更新

上面的代码可以工作，但正如 @Daniel.S 提到的，它只对列表进行一次迭代。

我应该设置什么条件才能迭代直到排序？

谢谢!!:)

Answer 1

查找merge sort ，它非常适合列表并且易于实现。该链接有一个示例实现:

Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.