在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).