關於排序的問題

Question

氣泡排序最多爲O（n），最差爲O（n^2），其內存使用量爲O（1）。合併排序總是O（n log n），但其內存使用量爲O（n）。

我們將使用哪種算法來實現一個函數，該函數接受一個整數數組並返回集合中的最大整數，假定數組長度小於1000.如果數組長度大於1000，該怎麼辦？

Answer 1

對於O（1）內存使用情況，可以在O（n）時間內完成對數據集的連續掃描，尋找最大值。

您只需將當前最大值設置爲第一個元素，然後再遍歷所有其他元素，並將當前最大值設置爲該值（如果該值較大）。僞代碼：

max = list[first_index] 
for index = first_index+1 to last_index: 
    if list[index] > max: 
     max = list[index] 

的複雜也不會因元素的數量列表中的改變，因此也無所謂有多少。

---

的運行時間但是會改變（因爲算法是O（n）的時間），如果它發現的最大快是很重要的，有許多的可能性。當列表更改時，這些都取決於做工作，而不是每次您需要這些信息時，因此它們更適合於閱讀次數多於書面次數的列表，因此可以攤銷成本。

選項1是保持列表排序，以便您可以抓住最後一個元素。這是可能是矯枉過正只是保持了最大值的記錄。

選項2是在您插入或從列表中刪除時重新計算最大值（以及保存它的元素的數量）。對於空列表，最初將max設置爲0並將maxcount設置爲0。

對於插入件：

• 如果maxcount是0（該列表是空的），設置max該數值和maxcount爲1
• 否則，如果該值大於max，設置max並將maxcount設置爲1.
• 否則，如果此值等於max，請將1加到maxcount。

對於缺失：

• 如果這個值等於max，從maxcount減去1。
• 然後，如果maxcount爲0，重新掃描列表以獲得新的max和maxcount。

這樣，在任何時候，你有最大的價值（計數只是一個額外的「技巧」，以加快算法，其中有超過一個元素保持最大值）。我之前在數據分析應用程序中使用過這種方法，結果比重新排序要快得多 - 在這種情況下，我必須存儲最小值和最大值，但它們是相同的想法。

Answer 2

除非預分類，否則最大值始終爲O（n）。如果預先分類，則較少。在搜索之前進行排序總是比O（n）更差...因此，一般來說，1,000個元素需要進行1,000次比較......只是比較字面意思。如果使用分類結構，它便宜。如果不是，它很昂貴。用分類結構插入更昂貴。 ...這就是爲什麼這是一個問題。