我又花时间研究了一下这部分的内容，我发现了我之前犯的错误，但是我依然没有找到 数组的排序效率高过链表的排序效率的方法
“我认为链表的排序效率高过数组
链表只需要修改指针的指向就行了，数组需要移动大量数据元素，如果这个数据元素比较大的话，那效率更是不容乐观”
数组需要移动大量数据元素
好的排序算法可以避免移动大量数据元素，但是对于数组，移动数据元素是不可避免的，而链表只需要修改指针
“我认为链表的排序效率高过数组
链表只需要修改指针的指向就行了，而数组需要移动数据元素，如果这个数据元素比较大的话，那效率更是不容乐观”
下面用代码说话#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{
size_t id;
char name[64];
} user_info_t;
void swap(user_info_t *a, user_info_t *b)
{
user_info_t temp = *a;
*a = *b;
*b = temp;
}
// 按id排序
void sort(user_info_t info[], size_t size)
{
for(size_t i = 0; i < size; ++i)
{
for(size_t j = i + 1; j < size; ++j)
{
if(info[i].id > info[j].id)
swap(&info[i], &info[j]);
}
}
}
int main(void)
{
printf("user_info_t size: %ld\n", sizeof(user_info_t));
user_info_t info[1024];
for(size_t i = 0; i < 1024; ++i)
{
info[i].id = 1024 - i;
}
sort(info, 1024);
for(size_t i = 0; i < 1024; ++i)
printf("%ld ", info[i].id);
printf("\n");
return 0;
}
数组版本用时33ms
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{
size_t id;
char name[64];
} user_info_t;
typedef user_info_t elem_type;
typedef struct node_tag
{
elem_type data;
struct node_tag *next;
} node_t;
typedef struct
{
node_t *head;
} list_t;
void list_init(list_t *l)
{
l->head = (node_t *)malloc(sizeof(node_t));
l->head->next = NULL;
}
void list_add(list_t *l, const elem_type *e)
{
node_t *node = (node_t *)malloc(sizeof(node_t));
node->data = *e;
node->next = l->head->next;
l->head->next = node;
}
void list_clear(list_t *l)
{
node_t *node = l->head->next;
while(node)
{
node_t *temp = node;
node = node->next;
free(temp);
}
l->head->next = NULL;
}
void list_traverse(const list_t *l)
{
node_t *node = l->head->next;
while(node)
{
printf("%ld ", node->data.id);
node = node->next;
}
printf("\n");
}
void list_destroy(list_t *l)
{
list_clear(l);
free(l->head);
l->head = NULL;
}
void swap(node_t *a, node_t *b)
{
node_t *temp = a->next;
a->next = b->next;
b->next = temp;
temp = a->next->next;
a->next->next = b->next->next;
b->next->next = temp;
}
// 按id排序
void sort(list_t *l)
{
for(node_t *i = l->head; i->next; i = i->next)
{
for(node_t *j = i->next; j->next; j = j->next)
{
if(i->next->data.id > j->next->data.id)
{
node_t *i_next = i->next;
swap(i, j);
if(i_next == j) // 如果i和j紧挨着，交换后j的指向会出错，这里修正一下
j = i->next;
}
}
}
}
int main(void)
{
printf("user_info_t size: %ld\n", sizeof(user_info_t));
user_info_t info = {0, {0}};
list_t l;
list_init(&l);
for(size_t i = 0; i < 1024; ++i)
{
info.id = i;
list_add(&l, &info);
}
sort(&l);
list_traverse(&l);
list_destroy(&l);
return 0;
}
链表版本用时21ms
因为链表版本只是修改指针指向，并不移动数据元素
我认为这个和排序算法无关，只要两者使用相同的排序算法，链表效率一定高过数组，这是我目前认为的，如果你不同意，请用代码说服我^_^
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2019-5-8 20:07:59
置顶卡
千斤顶
显身卡
楼主
发表于 2019-5-8 21:31:55
