|
发表于 2019-5-11 22:07:53
|
显示全部楼层
我又花时间研究了一下这部分的内容,我发现了我之前犯的错误,但是我依然没有找到 数组的排序效率高过链表的排序效率的方法
“我认为链表的排序效率高过数组
链表只需要修改指针的指向就行了,数组需要移动大量数据元素,如果这个数据元素比较大的话,那效率更是不容乐观”
数组需要移动大量数据元素
好的排序算法可以避免移动大量数据元素,但是对于数组,移动数据元素是不可避免的,而链表只需要修改指针
“我认为链表的排序效率高过数组
链表只需要修改指针的指向就行了,而数组需要移动数据元素,如果这个数据元素比较大的话,那效率更是不容乐观”
下面用代码说话
- #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
链表版本用时21ms
因为链表版本只是修改指针指向,并不移动数据元素
我认为这个和排序算法无关,只要两者使用相同的排序算法,链表效率一定高过数组,这是我目前认为的,如果你不同意,请用代码说服我^_^
|
|