首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >链表排序插入与数组排序。哪个更快?

问链表排序插入与数组排序。哪个更快?
EN

Stack Overflow用户
提问于 2015-06-06 19:19:17
回答 1查看 1.7K关注 0票数 1

我有一个链接列表,它在插入元素时对元素进行排序,但是当我必须对20,000+元素排序时,这有点慢。通常情况下,将所有元素添加到数组/链接列表中,然后对后面的单词进行排序是否更快/更有效。这是假设元素没有特定的顺序,所以不会被部分排序。我觉得这会更快排序后,因为你没有遍历名单20,000次,但我正在寻找更多的澄清。

EN

回答 1

Stack Overflow用户

发布于 2015-06-08 18:09:36

正在使用的数据结构(链接列表与数组)以及您正在使用的实现非常重要。

带数组的

在一次执行中插入所有元素,然后对其进行排序,速度会更快。这是因为在数组中间插入一个新元素将导致数组的其余部分被移动。例如:

在[1,2,5,7,8]中插入3

将导致元素3插入第三点(其中5是)。这将导致5被复制到第4点,7被复制到第5点,8被复制到第6点。

每次按排序顺序插入元素时,都会发生这种类型的洗牌,这是很昂贵的。

具有链接列表的

在链接列表的情况下,我们所看到的数组类型的洗牌不会发生,因为插入只需要更新前面和下面的元素的指针。例如:

在1 -> 2 -> 5 -> 7 -> 8中插入3

将需要将"next“元素指针更新为3,"next”元素指针3更新为5,元素1、7和8保持不变。

因此,如果您插入所有内容,然后对其进行排序,或者一次插入一个正确的位置,那么成本可能是相同的。

实现事项

所有这些都是理论上的讨论。您使用的实现非常重要。因此,您应该查看该实现的文档,以了解它如何实现这些操作。

票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/30686658

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档