performance - 对数组进行排序

Question

我想知道哪个对元素数组进行排序更好。

当我完成填充数组时，最好在最后对数组进行排序以获得良好的性能吗？或者每次我添加一个元素时最好对其进行排序？

Answer 1

这取决于什么对你来说很重要。您是否需要能够非常快速地插入（很多条目但很少查询），或者您是否需要能够非常快速地查询并缓慢插入（很多查询但没有很多条目）？

这基本上是你要解决的问题。当您知道这一点时，您可以选择适当的排序算法并应用它。

编辑：这是假设任一选择实际上很重要。这在很大程度上取决于您的活动（插入与查询）以及您需要排序的数据量。

Answer 2

暂时忽略特定于应用程序的信息，考虑排序插入在最坏的情况下需要对每个元素进行 O(n) 操作。对于 n 个元素，这当然给了我们 O(n^2)。如果这听起来很熟悉，那是因为您正在做的是（正如另一位评论者指出的）插入排序。相反，对整个列表执行一次快速排序将花费更糟糕的情况，O(n log n) 时间。

那么，这是否意味着您一定要等到最后才能排序？不。要记住的重要一点是 O(n log n) 是我们在一般情况下可以做的最好的排序。您对数据的特定应用知识可以影响工作的最佳算法。例如，如果您知道您的数据已经几乎排序，那么插入排序将为您提供线性时间复杂度。

您的里程可能会有所不同，但我认为算法观点在检查“我应该什么时候排序？”的一般问题时很有用。