arrays - 我们是否应该在对数组执行操作之前对数组进行排序？

Question

所以在很多情况下，当对数组执行操作时，比如二分查找或集合操作，排序数组总是更快。例如，合并两个已排序的数组需要 O(m+n) 或 O(n) 作为一个变量，而两个未排序的数组需要 O(n^2)。凭借其优势，我们是否应该在对数组执行操作之前始终对数组进行排序？

标签： arraysperformancesortingtime-complexity

Answer 1

始终主动排序通常会使后续操作更快，但您仍然会花费时间和资源对初始数组进行排序。

如果您的逻辑涉及可能受益于排序的下游计算，那么您应该尝试在逻辑流的早期对输入数组进行一次排序，以便所有函数重新使用相同的排序实例。

如果排序然后执行函数所花费的时间明显少于使用未排序数组执行函数的时间，那么您可能会争辩说强制函数首先排序是有好处的。

问题是，如果您的函数不断地对已经排序的同一个数组实例进行排序，那么通过消除所有排序可以获得一些性能提升。

如果您的函数涉及对排序数组执行得更好的操作，那么您应该指定输入参数是一个排序数组，（在 c# 中您可能使用 a SortedList）然后您已向调用者声明它们需要处理排序提前。