哪一个更快/更容易排序？数组或链表？

Question

我正在编写一个需要使用数组或链表存储数据的项目.稍后,必须对数据进行排序.我觉得编码数组更容易排序,因为我们只是交换.对于链接List,我们不得不担心(和代码)有关指针和访问每个元素比数组更昂贵.我对吗？

Answer 1

这在很大程度上取决于您的排序算法以及您要排序的内容.遍历链表的成本肯定高于索引数组中的元素.但是,如果您的排序算法涉及移位元素,则可以在链接列表中以恒定时间完成(而在数组中,必须逐个元素地复制,复制每个元素).链接列表中的交换元素也是恒定时间(只是更改指针),而在数组中它将复制元素(也可能是恒定时间,具体取决于您的数据).

对于要使用quicksort排序的一组整数,使用数组可能更快; 对于要使用选择排序进行排序的一组大型结构,链接列表会更快.

然后,存在如何访问元素的问题.如果您的排序意图是稍后通过二进制搜索访问元素,那么您肯定希望使用数组(因为二进制搜索通常比链接列表上的线性搜索慢,除非链接列表类似于平衡B-树).