只考虑冒泡排序和归并排序。对于冒泡排序，时间复杂度为 O(n)，最坏情况为 O(n^2)，空间复杂度为 O(1)。对于归并排序，时间复杂度为 O(nlogn)，空间复杂度为 O(n)。如果输入的大小小于 1000，您会选择哪种排序？为什么？超过 1000 个呢？
这是我遇到的一道面试题。只是想知道你们会如何回答。
最佳答案
Consider only the bubble sort and merge sort.
小于 1000，这可能意味着 RAM 足以满足任何没有外部存储的排序算法。这也意味着在这种情况下，时间复杂度的理论界限并不重要。您可以选择任何您喜欢的排序算法，而不会产生任何时间损失。例如，您可以进行冒泡排序，因为它可能易于实现且直观。归并排序同样好。
当输入大小大于 1000 时，可能假设时间复杂度很重要，甚至 RAM 在没有外部存储的情况下可能不够大。在这种情况下，如果您必须在两者之间做出选择，归并排序是安全的选择。这是因为合并排序在最坏情况下的性能优于冒泡排序，合并排序是 external sort 的一个很好的候选者。 (当输入大小大于 RAM 时)。
关于performance - 排序算法的内存速度权衡，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15345118/