C 编程 - 单链表中的插入排序

Question

我的作业快完成了，最后一部分是编写一个通过插入排序对单链表进行排序的函数。我还受到作业的预定义结构和 typedef 的约束:

struct le {
    int value;
    struct le *next;
};

typedef struct le listenelement;
typedef listenelement *list;

那些我无法改变的。插入排序函数必须使用这些参数。如果参数 m 为负数，则列表应按降序排序，否则按升序排序。

void sort(int m, list *l);

编辑:

这是我尝试从这里实现答案..我仍然无法让它工作。我尝试创建一个新列表，它是名为“asc”(升序排序列表)的最终结果和一个辅助列表“aux”，但我被卡住了..

void sort(int m, list *l){              
    if ((m == 0) || (*l == NULL)) {
        printf("Error.\n");
    } else {
        if (m>0) {
            listenelement head = {0,NULL};              
            list asc = {&head};
            list aux = *l;
            while (aux != NULL) {                       
                int val = aux->value;                                                   
                delete_elem(val,&aux);                                                  
                while ((asc->next != NULL) && ((asc->value)<val)) {         
                    printf("%d\n", (asc->value));                                       
                    asc=asc->next;
                }
                insert(val,&asc);   
                asc = &head;                            
            }
            *l = &head;
        }
    }
}

Answer 1

insertion sort can't work on a singly linked list, can it? You can only go forward in them.

数组的常见插入排序实现没有与单链表很好地配合的精确模拟，但这并不意味着该算法不能应用于这样的 list 。您只需要对该算法有更广泛的了解，维基百科characterizes如:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

请注意，该特征与您可以遍历项目的顺序无关。您陷入了插入步骤的通常实现中，该步骤涉及向后迭代列表以找到插入位置。实际上，您可以使用单链表来做到这一点，即从最近到最远测试每个先前的元素，但这会将整个算法的渐近复杂度更改为 O(N³ )。不好。而且没有必要。

通过从头开始向前迭代子列表来查找插入位置有什么问题吗？这仍然满足算法定义(如维基百科给出的)，保留了渐近复杂性，并且在一般情况下，它从按排序顺序排列的初始子列表中获得了与通常实现一样多的优势。

主要的区别在于最佳情况和最坏情况。通常实现的最好情况是元素最初是按顺序排列的，最坏的情况是它们最初是按相反顺序排列的。这些只是简单地翻转以实现向前迭代方法，但是通过链表和仔细的实现，这两种情况几乎可以同样好。向后迭代实现确实对数组有一些额外的实际影响，但这些不适用于链表。