performance - 排序算法的内存速度权衡

Question

只考虑冒泡排序和归并排序。对于冒泡排序，时间复杂度为 O(n)，最坏情况为 O(n^2)，空间复杂度为 O(1)。对于归并排序，时间复杂度为 O(nlogn)，空间复杂度为 O(n)。如果输入的大小小于 1000，您会选择哪种类型，为什么？超过1000个呢？

这是我遇到的一个面试问题。就是想知道大家怎么回答。

Answer 1

只考虑冒泡排序和归并排序。

少于 1000，这可能意味着 RAM 对于任何没有外部存储的排序算法都足够了。这也意味着在这种情况下，时间复杂度的理论界限并不重要。您可以选择任何您喜欢的排序算法，而不会产生任何时间损失。例如，您可以进行冒泡排序，因为它可能易于实现且直观。合并排序同样好。

当输入大小大于 1000 时，可能会假设时间复杂度很重要，甚至如果没有外部存储，RAM 可能不够大。在这种情况下，如果您必须在两者之间进行选择，归并排序是最安全的选择。这是因为合并排序比冒泡排序具有更好的最坏情况性能，并且合并排序是外部排序的良好候选者（当输入大小大于 RAM 时）。