仅考虑冒泡排序和合并排序 . 对于冒泡排序，时间复杂度将是O（n）到最差情况O（n ^ 2）和空间复杂度O（1） . 对于合并排序，时间复杂度为O（nlogn），空间复杂度为O（n） . 如果输入的大小小于1000，你会选择哪种？为什么？超过1000怎么样？
这是我的面试问题 . 只是想知道你们会怎么回答它 .
仅考虑冒泡排序和合并排序 .
小于1000，这可能意味着RAM足以用于没有外部存储的任何排序算法 . 这也意味着在这种情况下，时间复杂度的理论界限无关紧要 . 您可以选择任何您喜欢的排序算法，而不会产生任何时间损失 . 例如，您可以进行冒泡排序，因为它可能很容易实现 . 合并排序同样好 .
当输入大小大于1000时，可能假设时间复杂度很重要，甚至在没有外部存储的情况下RAM可能不够大 . 在这种情况下，如果你必须在两者之间进行选择，那么合并排序是一个安全的选择 . 这是因为合并排序具有比冒泡排序更好的最坏情况性能，并且合并排序是external sort的良好候选（当输入大小大于RAM时） .
1 回答
小于1000，这可能意味着RAM足以用于没有外部存储的任何排序算法 . 这也意味着在这种情况下，时间复杂度的理论界限无关紧要 . 您可以选择任何您喜欢的排序算法，而不会产生任何时间损失 . 例如，您可以进行冒泡排序，因为它可能很容易实现 . 合并排序同样好 .
当输入大小大于1000时，可能假设时间复杂度很重要，甚至在没有外部存储的情况下RAM可能不够大 . 在这种情况下，如果你必须在两者之间进行选择，那么合并排序是一个安全的选择 . 这是因为合并排序具有比冒泡排序更好的最坏情况性能，并且合并排序是external sort的良好候选（当输入大小大于RAM时） .