问关于数据结构和排序算法的几个问题

EN

链接-列表或数组

数组是比较常见的选择。

当您的数据已经在链接列表中时，或者您在应用程序的链接列表中需要它时，通常使用链接列表。

这并不是说我看到有正当理由使用其中一种而不是另一种(除了大多数排序算法都集中在数组上)。两者都可以在O(n log n)中排序，至少可以使用基于比较的排序算法。

什么时候使用什么

通过比较排序，插入排序通常用于<10-20个元素，因为它具有较低的常数因子，即使它有O(n平方)运行时间。对于更多的元素，快速排序或合并排序 (都在O(n log )中运行)或其中一种的派生通常更快(尽管还有其他的O(n log )排序算法)。

插入排序对几乎已排序的数据也表现良好(O(n))。

对于非基于比较的排序，它实际上取决于您的数据。基排序、桶排序和计数排序都是众所周知的例子，每个示例都有各自的用途。简单地看一看它们的运行时间，您就可以很好地了解应该在什么时候使用它们。例如，如果要排序的值范围很小，则计数排序是很好的。

您可以看到排序算法列表的维基百科。

请记住，使用这些排序算法中的任何一个，排序小于10000个元素的速度都会非常快--除非您需要绝对最好的性能，否则您真的可以选择您想要的哪一个。

据我理解，对于这两个问题，都没有明确的答案，因为两者都取决于用法的上下文。然而，以下几点可能很重要：

1. 如果要排序的记录很大，并且实现为值类型，则数组可能是可插入的，因为记录的交换涉及数据的复制，这可能比重定向引用慢。
2. 一些用于切换排序算法的实例大小通常是通过在特定上下文中的实验找到的；也许快速排序用于“大型”实例，而合并排序用于“小”实例，其中“大”和“小”之间的实际最佳分离是通过在特定上下文中进行尝试来找到的。