最有效的方法排序爲X/N數組中的元素 - .NET

我有全都有時間戳標記的上次更新對象的數組。我想獲得只包含最近更新項目的數組的子集。我將僅從50到100的數組中檢索5個元素，並且性能是我的首要任務，所以我同意使用其中一個類方法對整個數組進行排序。這樣做的最好方法是什麼？最有效的方法排序爲X/N數組中的元素 - .NET

是固定大小的數組？還是有一些物體被推到頂部？你爲什麼反對排序數組？ –

陣列將被固定在通過它進行排序時的大小，但我不知道這將是多大的前手。我反對排序整個事物，而不是整理它。我只是想讓它排序五個元素，然後再打破。沒有必要對其餘的元素進行排序，因爲它們不會被使用，數組也不會持久化，所以我不會看到未來的性能增益。 – evanmcdonnal

我會用一個insertion sort，打破了一旦你選擇了所需數量的元素。該解決方案具有O（k * n）複雜度，其中k是要提取的元素的數量。

還有一些算法，找到一個排序的數組的第k最大元素爲O（n）

一旦你找到了第K個最大元素X，你可以遍歷數組，並挑選所有這比十，你都保證有完全相同的K-1元優於X.

2012-06-02 04:32:54

這看起來不錯。如果沒有人在接下來的幾個小時內發佈更好的答案，我會接受。 – evanmcdonnal

如果你只有100個元素更大的元素，那麼我會簡單地對它們進行排序。否則，我會使用基於堆的優先級隊列實現。 O（n）來創建，每一次插入/刪除都有一個與它相關的O（logn）成本。

2012-06-02 05:40:44 Kakira

回答