这是我最近在网上找到的一个面试问题：
如果你要实现一个以整数数组作为输入并返回最大值的函数，你会使用冒泡排序还是归并排序来实现这个函数？如果数组大小小于 1000 怎么办？如果大于 1000 怎么办？
这就是我的想法：
首先，用排序来实现上面的功能真的很奇怪。您只需遍历数组一次并找到最大值。其次，如果必须在两者之间做出选择，那么冒泡排序会更好——您不必执行整个冒泡排序过程，而只需要执行第一遍。它在时间和空间上都优于归并排序。
我的回答有错误吗？我错过了什么吗？
问问题
24282 次
6 回答
16
这是一个技巧问题。如果您只想要最大值（或者实际上是任何 k 的第 k个值，包括找到中位数），那么有一个非常好的O(n)算法。排序是浪费时间。这就是他们想听到的。
正如你所说，最大值算法真的很简单。要解决这样的问题，您应该准备好快速选择算法，并且还可以建议堆数据结构，以防您需要能够改变值列表并始终能够快速产生最大值。
于 2013-03-08T04:30:35.760 回答
4
我刚刚搜索了算法。冒泡排序在这两种情况下都会获胜，因为最大的好处是只需运行一次。归并排序因为只需要计算最大的数而不能减少任何捷径。Merge 取列表的长度，找到中间，然后中间下面的所有数字都比较左边，上面的所有数字都比较右边；反对创建独特的配对进行比较。这意味着对于数组中剩下的每个数字，需要进行相同数量的比较。除此之外，每个数字都会被比较两次，因此数组中的最低数字很可能会在两次比较中被淘汰。意味着在许多情况下进行两次比较后，数组中的数字只减少了一个。泡沫将占主导地位
于 2013-03-08T03:57:01.473 回答
2
首先，我同意您所说的一切，但也许它是在询问了解算法的时间复杂度以及输入大小如何成为最快的一个重要因素。
冒泡排序是，归并排序是。所以，在一个小集合上它不会有那么不同，但在很多数据上，冒泡排序会慢得多。O(n2)O(nlogn)
于 2013-03-08T03:45:38.827 回答
1
除非最大部分，冒泡排序渐进地变慢，但它对小型有很大的优势，n因为它不需要合并/创建新数组。在某些实现中，这可能会使其实时更快。
于 2013-03-08T04:55:39.957 回答
1
只需要一次通过，在最坏的情况下，找到最大值你只需要遍历整个数组，所以气泡会更好..
于 2014-08-13T01:50:43.967 回答
1
归并排序对于计算机来说很容易对元素进行排序，而且排序时间比冒泡排序要少。合并排序的最佳情况是n*log2n，最坏情况是n*log2n。对于冒泡排序，最好的情况是O(n)，最坏的情况是O(n2)。
于 2015-11-29T09:27:03.387 回答