在O（n）中查找排序數組中的插入點？

Question

這是遊戲編程。可以說我有一個可以跟蹤範圍內10個敵人的單位。每個敵人的優先級在0-100之間。所以陣列目前看起來是這樣的（數字代表優先級）：

Enemy - 96 
Enemy - 78 
Enemy - 77 
Enemy - 73 
Enemy - 61 
Enemy - 49 
Enemy - 42 
Enemy - 36 
Enemy - 22 
Enemy - 17 

說範圍內的一個新的敵人徘徊，並有69優先級，這將73和61之間插入，並17將予以除名數組（好吧，在插入之前將刪除17個，我相信）。

有什麼方法可以找出它需要插入73和61之間沒有O（n）操作？

Answer 1

我覺得你在這裏問錯了問題。您必須先找到要插入的位置，然後插入該元素。這兩個操作都是連在一起的，我覺得你不應該問如何找到更快的地方，而不需要另一個。這將是有道理的，爲什麼在問題結束時。但我正在解決實際插入速度更快的問題。

答案很簡單：沒有

答案，你會從別人那太聰明爲自己獲得：

來完成，這是不使用數組的唯一途徑。在數組中，除非插入第一個或最後一個權限，否則插入將是O（n）。這是因爲數組由佔據內存中連續空間的元素組成。這就是你如何能夠在O（1）時間引用特定元素，你確切知道元素在哪裏。成本是插入中間你需要移動數組中的一半元素。因此，儘管您可以在log（n）時間內使用二分查找來查找，但在那段時間內無法插入。

所以如果你要做任何事情，你需要一個不同的數據結構。一個簡單的二叉樹可能是它在log（n）時間插入的解決方案。另一方面，如果你給它一個排序數組，你不得不擔心樹的平衡，所以不需要一棵紅黑樹。或者，如果你總是彈出最接近或最遠的元素，那麼你可以使用堆排序。堆排序是優先隊列的最佳算法。它有一個額外的優點，即在一個數組中安排一個樹結構，因此它具有更好的空間局部性（稍後會介紹更多）。

真相：

你最有可能有一打，也許幾十個敵人在附近最多。在那個水平上，漸近表現並不重要，因爲它是專門爲'n'的大值設計的。你在看的是宗教堅持你CS 201教授關於Big Oh的電話。線性搜索和插入將是最快的方法，它將擴展的答案是，誰在關心。如果你試圖實現一個複雜的算法來擴展它，你幾乎總是會比較慢，因爲什麼決定你的速度不是軟件，它是硬件，你最好堅持做硬件知道如何處理得好：「線性下降記憶」。實際上，在預取者完成它們的事情之後，即使有幾千個元素，但是實現紅黑樹，線性遍歷每個元素的速度也會更快。因爲像樹這樣的數據結構會在整個地方分配內存，而不考慮空間局部性。而爲節點分配更多內存的調用本身比讀取上千個元素花費的時間要貴。這就是爲什麼顯卡使用插入排序的原因。

堆排序

堆排序實際上可能會更快取決於輸入數據，因爲它使用線性陣列雖然它可能會混淆預取，所以很難說。唯一的限制是你只能彈出最高優先級的元素。顯然，您可以將最高優先級定義爲最低或最大元素。對我來說，堆排序太過於樂觀，只能在Google上描述它。它確實將插入和刪除分爲兩個O（log（n））操作。堆排序的最大缺點是會嚴重降低代碼的可調試性。堆不是一個有序的數組，它有一個順序，但堆排序是一個複雜的不直觀的算法，如果一個堆設置正確，它對人類來說顯然是不可見的。所以你會在最好的情況下引入更多的bug。地獄，最後一次我必須做堆排序，我複製了它的代碼，並有錯誤。

插入排序二進制搜索

原來這就是好像你正在試圖做的。事實是這是一個非常糟糕的主意。平均插入排序需要O（n）。而且我們知道這是將隨機元素插入到排序數組中的硬限制。是的，我們可以通過使用二分查找來找到想要插入的元素。但是平均插入仍然需要O（n）。或者，在最好的情況下，如果您插入並且元素進入最後一個位置，插入排序需要O（1）次，因爲插入時它已經位於正確的位置。但是，如果您執行二進制搜索來查找插入位置，那麼發現您應該插入最後一個位置需要O（log（n））時間。插入本身需要O（1）次。因此，在試圖優化它時，你會嚴重降低最佳性能。看看你的用例，這個隊列將敵人與他們的優先級保持一致。敵人的優先級可能是他們的力量和距離的函數。這意味着當一個敵人進入優先隊列時，它可能會有一個非常低的優先級。這在插入O（1）性能的最佳情況下起到了很好的作用。如果你減少最好的案例表現，你會做得更多的傷害，而不是好的，因爲它也是你最常見的情況。

Preoptimization是一切罪惡的根源 - 高德納

Answer 2

由於您始終在維護排序的搜索池，因此可以使用二分搜索。首先檢查中間元素，然後檢查中間元素和陣列中哪一端更靠近中間的元素，依此類推，直至找到位置。這會給你O（日誌 n）時間。

Answer 3

當然，假設你使用一個數組類型來容納這個名單很容易。

我會假設Enemy是您的班級名稱，並且該文件名爲Priority以執行排序。我們需要一個IComparer<Enemy>，看起來像下面這樣：

public class EnemyComparer : IComparer<Enemy> 
{ 
    int IComparer<Enemy>.Compare(Enemy x, Enemy y) 
    { 
     return y.Priority.CompareTo(x.Priority); // reverse operand to invert ordering 
    } 
} 

然後，我們可以如下編寫一個簡單的InsertEnemy例行：

public static bool InsertEnemy(Enemy[] enemies, Enemy newEnemy) 
{ 
    // binary search in O(logN) 
    var ix = Array.BinarySearch(enemies, newEnemy, new EnemyComparer()); 
    // If not found, the bit-wise compliment is the insertion index 
    if (ix < 0) 
     ix = ~ix; 
    // If the insertion index is after the list we bail out... 
    if (ix >= enemies.Length) 
     return false;// Insert is after last item... 
    //Move enemies down the list to make room for the insertion... 
    if (ix + 1 < enemies.Length) 
     Array.ConstrainedCopy(enemies, ix, enemies, ix + 1, enemies.Length - (ix + 1)); 
    //Now insert the newEnemy into the position 
    enemies[ix] = newEnemy; 
    return true; 
} 

還有其他的數據結構，這將使這個有點快，但這應該證明是足夠有效的。如果列表變大，B樹或二叉樹就沒有問題，但對於10個項目來說，它可能會更快。

了與上述增加以下的測試方法：

public class Enemy 
{ 
    public int Priority; 
} 

public static void Main() 
{ 
    var rand = new Random(); 
    // Start with a sorted list of 10 
    var enemies = Enumerable.Range(0, 10).Select(i => new Enemy() {Priority = rand.Next(0, 100)}).OrderBy(e => e.Priority).ToArray(); 
    // Insert random entries 
    for (int i = 0; i < 100; i++) 
     InsertEnemy(enemies, new Enemy() {Priority = rand.Next(100)}); 
}