在1000個整數中查找max int，使用冒泡排序還是合併排序？

-6

氣泡排序最多爲O（n），最差爲O（n^2），其內存使用量爲O（1）。合併排序總是O（n log n），但其內存使用量爲O（n）。說明如果假定數組的長度小於1000，你將使用哪種算法來實現一個採用整數數組的函數並返回最大整數。如果數組長度大於1000，該怎麼辦？在1000個整數中查找max int，使用冒泡排序還是合併排序？

來源

2013-10-04 user2847832

查找或排序？它不是一回事...... – Alvaro

沒有人會爲你做作業，你必須付出努力 –

如果這是某種學校的練習，我會建議退出，因爲它非常愚蠢。你不需要全部排序來找到最大值。只需遍歷所有內容並記住最高價值。時間O（n），內存O（1） – escitalopram

最簡單的可能是遍歷數組並跟蹤移動時最大的一個。這需要O(N)時間。所以你也不需要使用任何排序算法。

來源

2013-10-04 19:08:01

都沒有。

只是循環遍歷項目並跟蹤您找到的最大值。這是一個O（n）解決方案。

來源

2013-10-04 19:08:31 Guffa

泡沫分類是O(n²)平均，即使用它很少，如果有的話，是一個好主意。

合併排序總是O(n log n)。

因此，在這兩種選擇之間，合併排序是可取的。

也有plenty of other choices for sorting。和some dedicated to numeric data。

但是，要找到最大元素，不需要排序，只需遍歷整數並跟蹤最大值即可。

來源

2013-10-04 19:08:31 Dukeling

1000個元素的價值數據是沒有什麼。除非你使用80年代的計算機，否則「O（n log n）」與「O（n^2）」無關。 – 2013-10-04 19:10:28

@ H2CO3誠然，如果這是作業或面試，建議使用bubble-sort可能不是一個好主意，除非我們談論的是10個元素之類的東西（而且，因爲大多數（如果不是全部的話）庫類型使用O （n log n）排序，爲什麼使用一個（大概是自我實現的）O（n^2））。 – Dukeling

當然，我並不是說「讓我們繼續，並建議使用泡沫排序生產代碼」。我不喜歡無故浪費資源。然而，這是一個不同的場景 - 如果我是一位編程老師教授初級課程，我不會將泡沫排序的使用歸類爲「錯誤」，**甚至不是「低效」** - 我們應該教初學者在現實生活中發生了什麼。也就是說，我們不要做過早的優化，而是在必要時做好優化工作。 – 2013-10-04 19:17:24

在1000個整數中查找max int，使用冒泡排序還是合併排序？

回答

相關問題