c - 哪一个在排序时更快/更容易？数组还是链表？

Question

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

Answer 1

这在很大程度上取决于您的排序算法和您正在排序的内容。遍历链表的成本肯定高于索引数组中的元素。但是，如果您的排序算法涉及移动元素，则可以在链表中以恒定时间完成（而在数组中必须逐个元素完成，复制每个元素）。交换链表中的元素也是常数时间（只需更改指针），而在数组中它将复制元素（可能也是常数时间，具体取决于您的数据）。

对于要使用快速排序对一组整数进行排序，使用数组可能更快；对于要使用选择排序进行排序的一组大型结构，链表会更快。

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

Answer 2

根据您将实现的排序类型，您可能希望随机访问集合中的元素。考虑到这一点，数组确实是更好的选择。

我会继续猜测这是一个学校/学习项目（否则你会使用预先存在的排序函数，不是吗），所以你选择的排序算法会对这个决定产生影响。

通常，最快的排序是快速排序（或归并排序），它受益于随机访问（因此是数组）。你关于交换的想法也很好。通常您希望就地排序并避免分配额外的内存。

Answer 3

我不一定会推荐这种方法（取决于你在做什么），但如果你知道排序标准，你可以使用链表树进行排序。

说它是数字：

struct treeNode {
  struct treeNode* greater;
  struct treeNode* lesser;
  int myValue;
};

创建算法可能是最困难的（当出现某些中间值时，您将不得不推送节点）......取决于您喜欢使用递归和辅助函数的程度。