c - 在c中排序双向链表

Question

我想在插入元素时保持链表排序(列表中大约有 200000 个元素)，您可以推荐哪种算法？我使用插入排序做了一个简单的实现，但是它的性能非常非常差(大量的 CPU 使用率)。

感谢您的帮助。

我对合并排序和插入排序做了一些比较，但似乎插入排序的性能更好，我对这个结果有点困惑。你能告诉我哪里出了问题，是否有更好的算法？

我的代码(为简单起见，我省略了节点结构中的 prev 节点):

struct node {
    int number;
    struct node *next;
};

插入排序:

void insert_node(int value) {
    struct node *new_node = NULL;
    struct node *cur_node = NULL;
    struct node *last_node = NULL;
    int found; /* 1 means found a place to insert the new node in, 0 means not*/


    new_node = (struct node *)malloc(sizeof(struct node *));
    if(new_node == NULL) {
        printf("memory problem\n");
    }
    new_node->number = value;
    /* If the first element */
    if (head == NULL) {
        new_node->next = NULL;
        head = new_node;
    } 

    else if (new_node->number < head->number) {
        new_node->next = head;
        head = new_node;    
    } 

    else {
        cur_node = head;
        found = 0;
        while (( cur_node != NULL ) && ( found == 0 )) {
            if( new_node->number < cur_node->number )
            {
                found = 1;
            }
            else
            {
                last_node = cur_node;
                cur_node = cur_node->next;
            }
        }
    /* We got the right place to insert our node */
    if( found == 1 )
    {
        new_node->next = cur_node; 
    }
    /* Insert at the tail of the list */
    else
    {
        last_node->next = new_node;
        new_node->next = NULL;
    }           
}

合并排序:

/* add a node to the linked list */
struct node *addnode(int number, struct node *next) {
    struct node *tnode;

    tnode = (struct node*)malloc(sizeof(*tnode));

    if(tnode != NULL) {
        tnode->number = number;
        tnode->next = next;
    }

    return tnode;
}

/* perform merge sort on the linked list */
struct node *merge_sort(struct node *head) {
    struct node *head_one;
    struct node *head_two;

    if((head == NULL) || (head->next == NULL))
        return head;

    head_one = head;
    head_two = head->next;
    while((head_two != NULL) && (head_two->next != NULL)) {
        head = head->next;
        head_two = head->next->next;
    }
    head_two = head->next;
    head->next = NULL;

    return merge(merge_sort(head_one), merge_sort(head_two));
}

/* merge the lists.. */
struct node *merge(struct node *head_one, struct node *head_two) {
    struct node *head_three;

    if(head_one == NULL)
        return head_two;

    if(head_two == NULL)
        return head_one;

    if(head_one->number < head_two->number) {
        head_three = head_one;
        head_three->next = merge(head_one->next, head_two);
    } else {
        head_three = head_two;
        head_three->next = merge(head_one, head_two->next);
    }

    return head_three;
}

Answer 1

要在链表中插入元素，已排序的前提条件无济于事!没有算法可以提供帮助。

您可能想为您的元素考虑另一种结构。根据您的情况，一个简单的堆或二叉搜索树可能会很好地为您服务。

如果您想将大量元素插入到一个大型排序链表中，您可以对它们进行排序，然后进行非常快速的合并 O(N)。