關於冒泡排序VS合併排序

Question

這是我在互聯網上最近發現一個面試問題：

如果你要實現一個函數，它接受一個整數數組作爲輸入並返回最大，你會用冒泡排序或合併排序來實現此功能？如果數組大小小於1000，該怎麼辦？如果它大於1000呢？

這是我如何看待它：

首先，這是很奇怪的使用排序來實現上述功能。你可以通過一次數組來找到最大值。其次，如果必須在兩者之間作出選擇，那麼冒泡排序更好 - 您不必執行整個冒泡排序過程，而只需要執行第一遍。這比在時間和空間上合併排序要好。

我的答案中是否有錯誤？我錯過了什麼嗎？

Answer 1

這是一個詭計的問題。如果你只想要最大值（或者任何k的值，包括找到中值），那麼就有一個非常好的算法。分揀是浪費時間。這就是他們想聽到的。

正如你所說，最大化算法是微不足道的。爲了解決這個問題，您應該準備好快速選擇算法，並且能夠建議堆數據結構，以防需要能夠更改值列表並且始終能夠快速生成最大值。

Answer 2

首先，我同意你所說的一切，但也許它是在詢問有關算法的時間複雜性，以及輸入大小如何是最快的一個重要因素。

泡泡分類爲O(n2)，合併排序爲O(nlogn)。所以，在一個小的集合上它不會是那麼不同，但是對於大量的數據來說，Bubble排序會慢得多。

Answer 3

我剛剛搜索了算法。在兩種情況下，冒泡排序都是勝利的，因爲只需運行一次就能獲得最大的好處。合併排序不能削減任何捷徑，只需計算最大數量即可。合併需要列表的長度，找到中間，然後所有中間以下的數字與左邊相比，以上全部與右邊相比;反對創造獨特的配對來比較。對陣列中剩下的每個數字的含義都需要進行相同數量的比較。除此之外，每個數字都會進行兩次比較，因此在兩次比較中，陣列的最低數字很可能會被消除。在許多情況下進行兩次比較後，數組中只含有少一個數字。泡沫將主宰

Answer 4

除了最大的部分之外，冒泡排序漸近地慢一些，但是它對於小的n有很大的好處，因爲它不需要合併/創建新的數組。在某些實現中，這可能會使其實時更快。

Answer 5

只需要一個傳球，爲最壞的情況下，找到最大ü只需要遍歷整個數組，因此泡沫將破越好..

Answer 6

合併排序是便於計算機的元素，它排序比冒泡排序花費的時間更少。合併排序的最好情況是n*log2n，最壞的情況是n*log2n。隨着冒泡排序最好的情況是O(n)，最壞的情況是O(n2)。