鱼C论坛

 找回密码
 立即注册
查看: 1908|回复: 10

[已解决]C中输入任意多个数,排序

[复制链接]
发表于 2019-5-8 20:07:59 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
    任意多是指事先不知道多少个数,在输入时想什么时候停止就停止,除了定义一个足够大的数组外,还有没有别的方法?
不需要程序问我想输入多少个数(。。)
最佳答案
2019-5-8 21:31:55
本帖最后由 Croper 于 2019-5-8 21:33 编辑

你这是两个问题:
第一:如何判断一串数字输入完毕的问题
  1)确定输入的数字间以什么分割:最好空格或tab分割,这样可以使用scanf直接读取,其他的分割方式,如','分割,需要进行特殊处理
  2)确定以什么标志输入结束,以及如何判断输入结束:如果以回车结束,需要用getchar判断'\n'符号,同时需要考虑空格接回车等不太规范的输入

第二、如何储存这些数字:
   1) 申请一个足够大的数组,推荐
   2)申请一个较小的数组,不够再使用realloc扩大容量,如果数据量非常大的话可考虑
   3)链表,不推荐,排序的效率将会大大降低

反正思路就这样,怎么实现就看你了
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2019-5-8 20:32:46 | 显示全部楼层
思路,用回车符判断输入结束就可以了
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-5-8 21:31:55 | 显示全部楼层    本楼为最佳答案   
本帖最后由 Croper 于 2019-5-8 21:33 编辑

你这是两个问题:
第一:如何判断一串数字输入完毕的问题
  1)确定输入的数字间以什么分割:最好空格或tab分割,这样可以使用scanf直接读取,其他的分割方式,如','分割,需要进行特殊处理
  2)确定以什么标志输入结束,以及如何判断输入结束:如果以回车结束,需要用getchar判断'\n'符号,同时需要考虑空格接回车等不太规范的输入

第二、如何储存这些数字:
   1) 申请一个足够大的数组,推荐
   2)申请一个较小的数组,不够再使用realloc扩大容量,如果数据量非常大的话可考虑
   3)链表,不推荐,排序的效率将会大大降低

反正思路就这样,怎么实现就看你了
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-5-8 21:52:26 | 显示全部楼层
Croper 发表于 2019-5-8 21:31
你这是两个问题:
第一:如何判断一串数字输入完毕的问题
  1)确定输入的数字间以什么分割:最好空格或t ...

嗯,谢谢你的详细的补充。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-5-8 21:56:13 | 显示全部楼层
Croper 发表于 2019-5-8 21:31
你这是两个问题:
第一:如何判断一串数字输入完毕的问题
  1)确定输入的数字间以什么分割:最好空格或t ...

我认为链表的排序效率高过数组
链表只需要修改指针的指向就行了,数组需要移动大量数据元素,如果这个数据元素比较大的话,那效率更是不容乐观
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-5-8 22:50:55 | 显示全部楼层
本帖最后由 Croper 于 2019-5-8 22:53 编辑
人造人 发表于 2019-5-8 21:56
我认为链表的排序效率高过数组
链表只需要修改指针的指向就行了,数组需要移动大量数据元素,如果这个数 ...


嗯。。。同样的方法两者代码写出来都是同样的数量级(O[nlogn]或O[n^2],视排序方法不同),但是链表本神的访问就比数组要慢得多
(忘了在哪儿看的了,即使是a[1](链表就是head->next)这种访问,链表都要比数组慢一个数量级),
链表的优势在插入,和删除中间元素,但主流的排序方法除了插入排序,似乎涉及不到这一点,
所以除非插入排序,链表完全没有优势吧。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-5-11 22:07:53 | 显示全部楼层
Croper 发表于 2019-5-8 22:50
嗯。。。同样的方法两者代码写出来都是同样的数量级(O[nlogn]或O[n^2],视排序方法不同),但是链表本神 ...

我又花时间研究了一下这部分的内容,我发现了我之前犯的错误,但是我依然没有找到 数组的排序效率高过链表的排序效率的方法

“我认为链表的排序效率高过数组
链表只需要修改指针的指向就行了,数组需要移动大量数据元素,如果这个数据元素比较大的话,那效率更是不容乐观”


数组需要移动大量数据元素
好的排序算法可以避免移动大量数据元素,但是对于数组,移动数据元素是不可避免的,而链表只需要修改指针


“我认为链表的排序效率高过数组
链表只需要修改指针的指向就行了,而数组需要移动数据元素,如果这个数据元素比较大的话,那效率更是不容乐观”

下面用代码说话
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. typedef struct
  5. {
  6.         size_t id;
  7.         char name[64];
  8. } user_info_t;

  9. void swap(user_info_t *a, user_info_t *b)
  10. {
  11.         user_info_t temp = *a;
  12.         *a = *b;
  13.         *b = temp;
  14. }

  15. // 按id排序
  16. void sort(user_info_t info[], size_t size)
  17. {
  18.         for(size_t i = 0; i < size; ++i)
  19.         {
  20.                 for(size_t j = i + 1; j < size; ++j)
  21.                 {
  22.                         if(info[i].id > info[j].id)
  23.                                 swap(&info[i], &info[j]);
  24.                 }
  25.         }
  26. }

  27. int main(void)
  28. {
  29.         printf("user_info_t size: %ld\n", sizeof(user_info_t));

  30.         user_info_t info[1024];
  31.         for(size_t i = 0; i < 1024; ++i)
  32.         {
  33.                 info[i].id = 1024 - i;
  34.         }

  35.         sort(info, 1024);
  36.         for(size_t i = 0; i < 1024; ++i)
  37.                 printf("%ld ", info[i].id);
  38.         printf("\n");
  39.         return 0;
  40. }
复制代码

1.png



数组版本用时33ms


  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. typedef struct
  5. {
  6.         size_t id;
  7.         char name[64];
  8. } user_info_t;

  9. typedef user_info_t elem_type;

  10. typedef struct node_tag
  11. {
  12.         elem_type data;
  13.         struct node_tag *next;
  14. } node_t;

  15. typedef struct
  16. {
  17.         node_t *head;
  18. } list_t;

  19. void list_init(list_t *l)
  20. {
  21.         l->head = (node_t *)malloc(sizeof(node_t));
  22.         l->head->next = NULL;
  23. }

  24. void list_add(list_t *l, const elem_type *e)
  25. {
  26.         node_t *node = (node_t *)malloc(sizeof(node_t));
  27.         node->data = *e;
  28.         node->next = l->head->next;
  29.         l->head->next = node;
  30. }

  31. void list_clear(list_t *l)
  32. {
  33.         node_t *node = l->head->next;
  34.         while(node)
  35.         {
  36.                 node_t *temp = node;
  37.                 node = node->next;
  38.                 free(temp);
  39.         }
  40.         l->head->next = NULL;
  41. }

  42. void list_traverse(const list_t *l)
  43. {
  44.         node_t *node = l->head->next;
  45.         while(node)
  46.         {
  47.                 printf("%ld ", node->data.id);
  48.                 node = node->next;
  49.         }
  50.         printf("\n");
  51. }

  52. void list_destroy(list_t *l)
  53. {
  54.         list_clear(l);
  55.         free(l->head);
  56.         l->head = NULL;
  57. }

  58. void swap(node_t *a, node_t *b)
  59. {
  60.         node_t *temp = a->next;
  61.         a->next = b->next;
  62.         b->next = temp;
  63.         temp = a->next->next;
  64.         a->next->next = b->next->next;
  65.         b->next->next = temp;
  66. }

  67. // 按id排序
  68. void sort(list_t *l)
  69. {
  70.         for(node_t *i = l->head; i->next; i = i->next)
  71.         {
  72.                 for(node_t *j = i->next; j->next; j = j->next)
  73.                 {
  74.                         if(i->next->data.id > j->next->data.id)
  75.                         {
  76.                                 node_t *i_next = i->next;
  77.                                 swap(i, j);
  78.                                 if(i_next == j)                        // 如果i和j紧挨着,交换后j的指向会出错,这里修正一下
  79.                                         j = i->next;
  80.                         }
  81.                 }
  82.         }
  83. }

  84. int main(void)
  85. {
  86.         printf("user_info_t size: %ld\n", sizeof(user_info_t));

  87.         user_info_t info = {0, {0}};
  88.         list_t l;
  89.         list_init(&l);
  90.         for(size_t i = 0; i < 1024; ++i)
  91.         {
  92.                 info.id = i;
  93.                 list_add(&l, &info);
  94.         }
  95.         sort(&l);
  96.         list_traverse(&l);
  97.         list_destroy(&l);
  98.         return 0;
  99. }
复制代码


2.png

链表版本用时21ms

因为链表版本只是修改指针指向,并不移动数据元素
我认为这个和排序算法无关,只要两者使用相同的排序算法,链表效率一定高过数组,这是我目前认为的,如果你不同意,请用代码说服我^_^
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-5-11 22:24:46 | 显示全部楼层
Croper 发表于 2019-5-8 22:50
嗯。。。同样的方法两者代码写出来都是同样的数量级(O[nlogn]或O[n^2],视排序方法不同),但是链表本神 ...
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. typedef struct
  5. {
  6.         size_t id;
  7.         char name[4096];
  8. } user_info_t;

  9. typedef user_info_t elem_type;

  10. typedef struct node_tag
  11. {
  12.         elem_type data;
  13.         struct node_tag *next;
  14. } node_t;

  15. typedef struct
  16. {
  17.         node_t *head;
  18. } list_t;

  19. void list_init(list_t *l)
  20. {
  21.         l->head = (node_t *)malloc(sizeof(node_t));
  22.         l->head->next = NULL;
  23. }

  24. void list_add(list_t *l, const elem_type *e)
  25. {
  26.         node_t *node = (node_t *)malloc(sizeof(node_t));
  27.         node->data = *e;
  28.         node->next = l->head->next;
  29.         l->head->next = node;
  30. }

  31. void list_clear(list_t *l)
  32. {
  33.         node_t *node = l->head->next;
  34.         while(node)
  35.         {
  36.                 node_t *temp = node;
  37.                 node = node->next;
  38.                 free(temp);
  39.         }
  40.         l->head->next = NULL;
  41. }

  42. void list_traverse(const list_t *l)
  43. {
  44.         node_t *node = l->head->next;
  45.         while(node)
  46.         {
  47.                 printf("%ld ", node->data.id);
  48.                 node = node->next;
  49.         }
  50.         printf("\n");
  51. }

  52. void list_destroy(list_t *l)
  53. {
  54.         list_clear(l);
  55.         free(l->head);
  56.         l->head = NULL;
  57. }

  58. void swap(node_t *a, node_t *b)
  59. {
  60.         node_t *temp = a->next;
  61.         a->next = b->next;
  62.         b->next = temp;
  63.         temp = a->next->next;
  64.         a->next->next = b->next->next;
  65.         b->next->next = temp;
  66. }

  67. // 按id排序
  68. void sort(list_t *l)
  69. {
  70.         for(node_t *i = l->head; i->next; i = i->next)
  71.         {
  72.                 for(node_t *j = i->next; j->next; j = j->next)
  73.                 {
  74.                         if(i->next->data.id > j->next->data.id)
  75.                         {
  76.                                 node_t *i_next = i->next;
  77.                                 swap(i, j);
  78.                                 if(i_next == j)                        // 如果i和j紧挨着,交换后j的指向会出错,这里修正一下
  79.                                         j = i->next;
  80.                         }
  81.                 }
  82.         }
  83. }

  84. int main(void)
  85. {
  86.         printf("user_info_t size: %ld\n", sizeof(user_info_t));

  87.         user_info_t info = {0, {0}};
  88.         list_t l;
  89.         list_init(&l);
  90.         for(size_t i = 0; i < 1024; ++i)
  91.         {
  92.                 info.id = i;
  93.                 list_add(&l, &info);
  94.         }
  95.         sort(&l);
  96.         list_traverse(&l);
  97.         list_destroy(&l);
  98.         return 0;
  99. }
复制代码


1.png

23ms,链表几乎不受数据元素大小的影响


  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  4. typedef struct
  5. {
  6.         size_t id;
  7.         char name[4096];
  8. } user_info_t;

  9. void swap(user_info_t *a, user_info_t *b)
  10. {
  11.         user_info_t temp = *a;
  12.         *a = *b;
  13.         *b = temp;
  14. }

  15. // 按id排序
  16. void sort(user_info_t info[], size_t size)
  17. {
  18.         for(size_t i = 0; i < size; ++i)
  19.         {
  20.                 for(size_t j = i + 1; j < size; ++j)
  21.                 {
  22.                         if(info[i].id > info[j].id)
  23.                                 swap(&info[i], &info[j]);
  24.                 }
  25.         }
  26. }

  27. int main(void)
  28. {
  29.         printf("user_info_t size: %ld\n", sizeof(user_info_t));

  30.         user_info_t info[1024];
  31.         for(size_t i = 0; i < 1024; ++i)
  32.         {
  33.                 info[i].id = 1024 - i;
  34.         }

  35.         sort(info, 1024);
  36.         for(size_t i = 0; i < 1024; ++i)
  37.                 printf("%ld ", info[i].id);
  38.         printf("\n");
  39.         return 0;
  40. }
复制代码

2.png

350ms,因为数组在不停的移动数据元素

虽然说name预留4096字节有点夸张,但是这只是为了演示数据元素比较大的情况
name预留4096字节恐怕只有在这里才会出现,但是在现实中数据元素比较大的情况并不罕见

另外,上面也证明了可以用代码量换时间
数组46行,链表112行^_^

评分

参与人数 1荣誉 +5 鱼币 +5 贡献 +3 收起 理由
Croper + 5 + 5 + 3 鱼C有你更精彩^_^

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-5-12 11:42:42 | 显示全部楼层
本帖最后由 Croper 于 2019-5-12 11:59 编辑
人造人 发表于 2019-5-11 22:24
23ms,链表几乎不受数据元素大小的影响


嗯,你提到了关于数组移动元素的问题,我之前按照楼主的意思,一直把这个数组默认为整数数组,移动元素的时间代价应该是很小的,所以完全没有考虑这一点,

不过你这么一说,我也做了下实验

排序方法以及排序时使用的元素:
  1. //关于数组和链表排序速度的实验,排序方法:快排

  2. #include <time.h>
  3. #include <random>
  4. #include <iostream>

  5. using namespace std;

  6. //数组和链表的大小
  7. const int ARRSIZE = 100000;  
  8. //测试次数
  9. const int TESTTIME = 10;

  10. //数组排序
  11. template <typename T>
  12. void qsort(T* a, int size) {
  13.         struct ele {
  14.                 T* a;
  15.                 int size;
  16.         };
  17.        
  18.         ele *stk = new ele[ARRSIZE];
  19.         int c_stk=0;

  20.         while (size>1){
  21.                 int p = 0, q = size - 1;
  22.                 T t = a[0];
  23.                 T n = a[1];
  24.                 while (q > p) {
  25.                         if (n < t) {
  26.                                 a[p++] = n;
  27.                                 if (p + 1 < size) n = a[p + 1];
  28.                         }
  29.                         else {
  30.                                 T tmp = a[q];
  31.                                 a[q--] = n;
  32.                                 n = tmp;
  33.                         }
  34.                 }
  35.                 a[p] = t;

  36.                 int size2 = size - p - 1;
  37.                 if (size2 > 1) stk[c_stk++]={ a + p + 1,size2 };

  38.                 size = p;
  39.                 if (size < 2 && c_stk!=0) {
  40.                         --c_stk;
  41.                         size = stk[c_stk].size;
  42.                         a = stk[c_stk].a;
  43.                 }
  44.         }
  45. }


  46. //链表节点声明
  47. template <typename T>
  48. struct Node {
  49.         T val;
  50.         Node* next;
  51.         Node(T n) :val(n), next(nullptr) {};
  52. };

  53. //删除链表
  54. template <typename T>
  55. void dellist(Node<T>* head) {
  56.         while (head != nullptr) {
  57.                 Node<T>* tmp = head->next;
  58.                 delete head;
  59.                 head = tmp;
  60.         }
  61. }


  62. //链表排序
  63. template <typename T>
  64. void qsort(Node<T>*& head) {
  65.         struct ele {
  66.                 Node<T>** begin;
  67.                 Node<T>* end;
  68.         };

  69.         ele *stk = new ele[ARRSIZE];
  70.         int c_stk = 0;

  71.         Node<T> **begin = &head;
  72.         Node<T> *end = nullptr;
  73.         while (*begin != end && (*begin)->next!=end) {
  74.                 Node<T> *p = *begin;
  75.                 Node<T> *mid = *begin;
  76.                 Node<T> *& newhead=*begin;
  77.                 while (p->next!=end) {
  78.                         if (p->next->val < mid->val) {
  79.                                 Node<T>* tmp = p->next->next;
  80.                                 p->next->next = newhead;
  81.                                 newhead = p->next;
  82.                                 p->next = tmp;
  83.                         }
  84.                         else {
  85.                                 p = p->next;
  86.                         }
  87.                 }

  88.                 if (mid->next != end && mid->next->next != end) {
  89.                         stk[c_stk++] = { &(mid->next),end };
  90.                 }

  91.                 end = mid;
  92.                 if ((*begin==end || (*begin)->next == end) && c_stk!=0) {
  93.                         --c_stk;
  94.                         begin = stk[c_stk].begin;
  95.                         end = stk[c_stk].end;
  96.                 }
  97.         }
  98. }

  99. //这是能指定大小的需要排序的元素元素,重载了operator<();
  100. template <int SIZE>
  101. struct mulint {
  102.         int val[SIZE];
  103.        
  104.         mulint() {};
  105.         mulint(int n) {
  106.                 val[0] = n;
  107.         }
  108.         mulint& operator=(int n) {
  109.                 val[0] = n;
  110.                 return *this;
  111.         }
  112.         bool operator<(const mulint& m2) {
  113.                 return val[0] < m2.val[0];
  114.         }
  115. };
复制代码


测试代码
  1. template <int N>
  2. void test() {
  3.         clock_t t1, t2;
  4.         t1 = t2 = 0;

  5.         for (int i = 0; i < TESTTIME; ++i) {
  6.                 //初始化数组和链表,保证其中的元素完全一样
  7.                 mulint<N> a[ARRSIZE];
  8.                 Node<mulint<N>>* preb = new Node<mulint<N>>(0);
  9.                 Node<mulint<N>>* p = preb;

  10.                 for (int j = 0; j < ARRSIZE; ++j) {
  11.                         int t = rand() % ARRSIZE;
  12.                         a[j] = t;
  13.                         p->next = new Node<mulint<N>>(t);
  14.                         p = p->next;
  15.                 }

  16.                 //测试排序时间
  17.                 clock_t t = clock();
  18.                 qsort(a, ARRSIZE);
  19.                 t1 += clock() - t;


  20.                 t = clock();
  21.                 qsort(preb->next);
  22.                 t2 += clock() - t;

  23.                 dellist(preb);
  24.         }

  25.         cout <<"数据大小:"<<N<< " 数组排序耗费时间:" << t1 << endl;
  26.         cout <<"数据大小:"<<N<< " 链表排序耗费时间:" << t2 << endl;
  27. }

  28. int main() {
  29.         test<1>();
  30.         test<10>();
  31.         test<20>();
  32.         test<30>();
  33.         test<40>();
  34.         test<50>();
  35.         test<60>();
  36.         test<70>();
  37.         test<80>();
  38.         test<90>();
  39.         system("pause");
  40. }
复制代码


测试结果:
数据大小:1 数组排序耗费时间:784
数据大小:1 链表排序耗费时间:1059
数据大小:10 数组排序耗费时间:1279
数据大小:10 链表排序耗费时间:1026
数据大小:20 数组排序耗费时间:1454
数据大小:20 链表排序耗费时间:1082
数据大小:30 数组排序耗费时间:1486
数据大小:30 链表排序耗费时间:1124
数据大小:40 数组排序耗费时间:1661
数据大小:40 链表排序耗费时间:1134
数据大小:50 数组排序耗费时间:1677
数据大小:50 链表排序耗费时间:1147
数据大小:60 数组排序耗费时间:1735
数据大小:60 链表排序耗费时间:1194
数据大小:70 数组排序耗费时间:1772
数据大小:70 链表排序耗费时间:1167
数据大小:80 数组排序耗费时间:1670
数据大小:80 链表排序耗费时间:1177
数据大小:90 数组排序耗费时间:1830
数据大小:90 链表排序耗费时间:1220


嗯。。。看起来似乎数组并没有多大优势,
但是仔细想一想,似乎在哪里看过,数组访问速度的优势很大程度是因为其能通过基于cpu加速,而链表必须老老实实访问内存。
但是debug模式下,这个优势并没有得到体现,于是改成了release模式,再次测试:


数据大小:1 数组排序耗费时间:69
数据大小:1 链表排序耗费时间:265
数据大小:10 数组排序耗费时间:93
数据大小:10 链表排序耗费时间:324
数据大小:20 数组排序耗费时间:115
数据大小:20 链表排序耗费时间:350
数据大小:30 数组排序耗费时间:164
数据大小:30 链表排序耗费时间:394
数据大小:40 数组排序耗费时间:257
数据大小:40 链表排序耗费时间:405
数据大小:50 数组排序耗费时间:337
数据大小:50 链表排序耗费时间:424
数据大小:60 数组排序耗费时间:381
数据大小:60 链表排序耗费时间:520
数据大小:70 数组排序耗费时间:481
数据大小:70 链表排序耗费时间:445
数据大小:80 数组排序耗费时间:528
数据大小:80 链表排序耗费时间:424
数据大小:90 数组排序耗费时间:632
数据大小:90 链表排序耗费时间:520

结果比较明显了,在数据大小比较小的时候,数组排序的效率能达到链表的三到四倍左右。
在数据大小大概为70*sizeof(int)=280Byte左右,两者速度差不多;再大一些,就是链表的优势区了
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-5-12 11:48:45 | 显示全部楼层
本帖最后由 Croper 于 2019-5-12 11:57 编辑

之后继续想了一下。。数据大的话谁会到处移动数据啊。。
正常来说,不应该是建立一个索引,然后通过索引访问么。。?

所以再次试了一下,这次为数组建立索引,然后通过索引访问数组,排序时也只移动索引,不移动元素本身:

  1. //索引
  2. template <int N>
  3. struct mptr {
  4.         mulint<N>* p;
  5.         bool operator<(const mptr& p2) {
  6.                 return p->val[0] < p2.p->val[0];
  7.         }
  8. };


  9. template <int N>
  10. void test2() {
  11.         clock_t t1, t2;
  12.         t1 = t2 = 0;

  13.         for (int i = 0; i < TESTTIME; ++i) {
  14.                 //初始化数组和链表,保证其中的元素完全一样
  15.                 mulint<N> a[ARRSIZE];
  16.                 Node<mulint<N>>* preb = new Node<mulint<N>>(0);
  17.                 Node<mulint<N>>* p = preb;

  18.                 for (int j = 0; j < ARRSIZE; ++j) {
  19.                         int t = rand() % ARRSIZE;
  20.                         a[j] = t;
  21.                         p->next = new Node<mulint<N>>(t);
  22.                         p = p->next;
  23.                 }

  24.                 //建立数组的索引:
  25.                 mptr<N> index[ARRSIZE];
  26.                 for (int j = 0; j < ARRSIZE; ++j) {
  27.                         index[j].p = a + j;
  28.                 }
  29.                 //测试排序时间
  30.                 clock_t t = clock();
  31.                 qsort(index, ARRSIZE);
  32.                 t1 += clock() - t;

  33.                 t = clock();
  34.                 qsort(preb->next);
  35.                 t2 += clock() - t;

  36.                 dellist(preb);
  37.         }

  38.         cout << "数据大小:" << N << " 数组排序耗费时间:" << t1 << endl;
  39.         cout << "数据大小:" << N << " 链表排序耗费时间:" << t2 << endl;
  40. }

  41. int main() {
  42.         test2<1>();
  43.         test2<10>();
  44.         test2<20>();
  45.         test2<30>();
  46.         test2<40>();
  47.         test2<50>();
  48.         test2<60>();
  49.         test2<70>();
  50.         test2<80>();
  51.         test2<90>();
  52.         system("pause");
  53. }
复制代码


结果:
数据大小:1 数组排序耗费时间:118
数据大小:1 链表排序耗费时间:328
数据大小:10 数组排序耗费时间:112
数据大小:10 链表排序耗费时间:347
数据大小:20 数组排序耗费时间:129
数据大小:20 链表排序耗费时间:353
数据大小:30 数组排序耗费时间:136
数据大小:30 链表排序耗费时间:389
数据大小:40 数组排序耗费时间:136
数据大小:40 链表排序耗费时间:391
数据大小:50 数组排序耗费时间:140
数据大小:50 链表排序耗费时间:429
数据大小:60 数组排序耗费时间:149
数据大小:60 链表排序耗费时间:512
数据大小:70 数组排序耗费时间:150
数据大小:70 链表排序耗费时间:445
数据大小:80 数组排序耗费时间:157
数据大小:80 链表排序耗费时间:439
数据大小:90 数组排序耗费时间:153
数据大小:90 链表排序耗费时间:490


可以看到,通过索引访问数组之后,数组的排序速度基本是3倍于链表,
更不用说数组在随机访问等其他方面的优势了
所以综上:
我仍然认为链表的排序速度低于数组

评分

参与人数 1荣誉 +5 鱼币 +5 贡献 +3 收起 理由
人造人 + 5 + 5 + 3 鱼C有你更精彩^_^

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-5-18 16:37:00 | 显示全部楼层
Croper 发表于 2019-5-12 11:48
之后继续想了一下。。数据大的话谁会到处移动数据啊。。
正常来说,不应该是建立一个索引,然后通过索引访 ...

今天我花时间研究了一下这部分内容
只要把 数组中存储对象本身 改为 数组中存储对象指针,链表的排序优势就不复存在

你赢了^_^
但前提是 数组中存储对象指针
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-8 02:06

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表