數組排序

我想知道這是更好的排序的數組元素的。數組排序

它是更好，當我填完它來獲得良好的業績在年底數組排序？或者每次向它添加元素時最好對它進行排序？

2013-04-23 I3i0

我們在談什麼樣的陣列，10個項目，100萬個項目？ – 2013-04-23 00:42:39

「或者每次向它添加元素時最好對它進行排序？」 - 聽起來有點像插入排序不？ – Mysticial 2013-04-23 00:42:41

這是什麼語言？ PHP，HTML，Javascript？ – Max 2013-04-23 00:42:43

忽略了一會兒應用特定的信息，考慮排序插入要求，最壞的情況下，O（n）的每個元素的操作。對於n個元素，這當然會給我們O（n^2）。如果這聽起來很熟悉，那是因爲你在做什麼（正如另一位評論者指出的那樣）是一種插入排序。相比之下，在整個列表中執行一個快速排序將會花費更長的時間O（n log n）時間。

那麼，這是否意味着你一定要等到最後才能排序？不可以。要記住的重要一點是O（n log n）是我們可以在一般情況下進行排序的最佳選擇。您對應用程序特定的數據知識會影響工作的最佳算法。例如，如果你知道你的數據已經基本排序了，那麼插入排序會給你線性時間複雜度。

您的里程可能會有所不同，但我認爲研究的一般問題時，算法的觀點是有用的：「當我要排序？」

2013-04-23 01:17:59

感謝大衛。由於數據幾乎是隨機的，我想我會在最後對數組進行排序。 – I3i0 2013-04-23 01:31:53

這取決於什麼對你至關重要。你需要能夠插入非常快（很多條目，但很少的查詢），或者你需要能夠非常快速地查詢並插入緩慢（很多查詢但不是很多條目）？

這基本上是你要解決的問題。當你知道這一點時，你可以選擇一個適當的排序算法並應用它。

編輯：這是假設任何選擇實際上很重要。這很大程度上取決於您的活動（插入vs查詢）以及您需要排序的數據量。

2013-04-23 00:45:46 ApplePie

請解釋downvote。我會根據需要刪除或更正我的答案。 – ApplePie 2013-04-23 00:47:34

我需要處理csv文件（10k到100K），然後爲csv文件中的每一列創建一個數組。然後計算每個數組中的值並在稍後使用這些計數。 – I3i0 2013-04-23 00:56:39

回答