Я хочу сохранить связанный список в отсортированном порядке при вставке элементов (около 200000 элементов в списке), какой алгоритм вы можете порекомендовать?Я сделал простую реализацию, используя сортировку вставками, но ее производительность очень и очень плохая (большая загрузка процессора).
Спасибо за вашу помощь.
Я провел некоторое сравнение между сортировкой слиянием и вставкойсортировка, но кажется, что сортировка вставки имеет лучшую производительность, я немного смущен этим результатом.Можете ли вы сказать мне, что не так, и если есть лучший алгоритм?
Мой код (для простоты я исключил узел 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;
}