数组排序

Question

我想知道这是更好的排序的数组元素的。

它是更好，当我填完它来获得良好的业绩在年底数组排序？或者每次向它添加元素时最好对它进行排序？

Answer 1

忽略了一会儿应用特定的信息，考虑排序插入要求，最坏的情况下，O（n）的每个元素的操作。对于n个元素，这当然会给我们O（n^2）。如果这听起来很熟悉，那是因为你在做什么（正如另一位评论者指出的那样）是一种插入排序。相比之下，在整个列表中执行一个快速排序将会花费更长的时间O（n log n）时间。

那么，这是否意味着你一定要等到最后才能排序？不可以。要记住的重要一点是O（n log n）是我们可以在一般情况下进行排序的最佳选择。您对应用程序特定的数据知识会影响工作的最佳算法。例如，如果你知道你的数据已经基本排序了，那么插入排序会给你线性时间复杂度。

您的里程可能会有所不同，但我认为研究的一般问题时，算法的观点是有用的：“当我要排序？”

Answer 2

这取决于什么对你至关重要。你需要能够插入非常快（很多条目，但很少的查询），或者你需要能够非常快速地查询并插入缓慢（很多查询但不是很多条目）？

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

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