保持一個數組排序 - 在設置，遲早？

Question

作爲學習目標c/oop的輔助手段，我設計了一個iOS應用程序來存儲和顯示週期性體重測量。我有一個單例，它返回測量對象共享存儲的可變陣列。每次測量至少有一個日期和體重，我希望能夠添加歷史測量。

我想按日期順序顯示測量結果。什麼是最好的方法來做到這一點？就我看到的選項如下：1）添加度量時 - 我重寫addobject以在每次添加度量後對共享存儲進行排序，2）檢索可變陣列時對其進行排序，或者3）檢索以任何順序存在於共享存儲中的可變陣列，然後在顯示錶格/圖表時進行排序。

很可能數據將被更頻繁地檢索而不是添加新的數據，因此選項1將減少共享存儲的冗餘排序 - 所以這是最好的方法，是的？

Answer 1

您可以使用（1）的修改版本。每次插入新對象時，不要每次對整個數組進行排序，而應使用此處描述的方法：https://stackoverflow.com/a/8180369/1187415將新對象插入到正確位置的數組中。

然後，對於每個插入，只有二進制搜索才能找到新對象的正確索引，並且該數組始終處於正確的順序。

既然你說過數據檢索比新數據更加頻繁，這似乎更有效率。

Answer 2

如果我忘記了你的特殊情況，這個問題不容易回答。有兩個基本的解決方案：

1. 保持數組未排序，當您嘗試訪問元素和數組未排序，然後對其進行排序。我們稱之爲「懶排序」。

2. 插入元素時保持數組排序。注意這不是關於在最後追加新元素，然後對整個數組進行排序。這是關於找到元素應該在哪裏（二進制搜索）並將其放置在那裏。我們稱之爲「分類插入」。

這兩種技術都是正確和有用的，並決定哪一種更好取決於您的使用情況。

例子：

1. 要插入數百元素融入到陣列，然後訪問的元素，然後再插入數百個元素，然後訪問。總之，您將以大塊插入值。在這種情況下，懶排序會更好。

2. 你會經常插入單個元素，你會經常訪問元素。然後排序插入將有更好的表現。

3. 中間的東西（插入1和插入數十個元素之間）。您可能不在乎使用哪一種方法。

（請注意，您還可以使用特殊結構，以保持數組排序，不是基於NSArray，例如基於平衡樹結構，同時保持在樹元素的個數）。