插入一個已排序列表

使用Java，我有一個類，被稱爲TestClass中，其中有一個名爲名成員，這是一個字符串。我也有一個這種類型的ArrayList，它已經按名稱按字母順序排序。我想要做的是找到放置TestClass的新實例的最佳索引。我能想出迄今最好的辦法是這樣的：插入一個已排序列表

public static int findBestIndex(char entry, ArrayList<TestClass> list){ 
    int desiredIndex = -1; 
    int oldPivot = list.size(); 
    int pivot = list.size()/2; 
    do 
    { 
     char test = list.get(pivot).Name.charAt(0); 
     if (test == entry) 
     { 
      desiredIndex = pivot; 
     } 
     else if (Math.abs(oldPivot - pivot) <= 1) 
     { 
      if (test < entry) 
      { 
       desiredIndex = pivot + 1; 
      } 
      else 
      { 
       desiredIndex = pivot - 1; 
      } 
     } 
     else if (test < entry) 
     { 
      int tempPiv = pivot; 
      pivot = oldPivot - (oldPivot - pivot)/2; 
      oldPivot = tempPiv; 
     } 
     else 
     { 
      int tempPiv = pivot; 
      pivot = pivot - (oldPivot - pivot)/2; 
      oldPivot = tempPiv; 
     } 

    } while (desiredIndex < 0); 

    return desiredIndex; 
}

從本質上講，打破陣列中的一半，請檢查你的價值去之前，之後，或在該點。如果是，請檢查數組的前半部分。另外，請檢查下半場。然後，重複。我明白，這種方法只能通過第一個字符進行測試，但這很容易修復，並且與我的主要問題無關。對於某些場景，這種方法運作良好。對於大多數人來說，它的工作非常可怕。我認爲它沒有正確地找到新的支點，如果是這樣的話，我會如何解決它？

編輯：爲了澄清，我用這對庫存系統，所以我不知道一個LinkedList是適當的。我使用的是ArrayList，因爲它們對我來說比較熟悉，所以如果需要的話，它可能更容易翻譯成另一種語言（目前可能會轉向C＃）。我試圖避免像Comparable這樣的事情，因爲如果C＃缺乏它，我必須完全重寫。

編輯部分Duex：想通了我在做什麼錯。我應該設置並更改我檢查區域的邊界，並基於此創建新的支點，而不是使用之前的支點。

來源

2013-05-26 user2423158

你爲什麼不只是插入所有元素，然後使用'Collections.sort（）'？ – fge

也許我沒有看這個權利，但是如果您確定該值在選定（測試）點之後__ _ _ _ _ _ _ _ _ _ _ _，_ _ _ _ _ _ _ _ _ _ _ _ _ _ – lurker

@fge，儘管速度並不是我最關心的問題，但每次插入之後都會採用最慢的方法，因爲不會有很多對象快速移入和移出。 – user2423158

您應該使用這樣的事情已經有秩序感的PriorityQueue。插入一個有秩序感的集合會自動將元素放在正確的地方，時間最少（通常是log（n）或更少）。

如果你想要做的任意插入不這樣做，那麼我會建議使用，將不必使出或完全複製到插入喜歡你目前擁有的ArrayList的一個項目一個LinkedList。雖然爲鏈表找到正確的插入位置將花費O（n）時間，但實際上，它仍然比使用log（n）搜索ArrayList中的正確位置更快，但需要複製或排序它之後。

而且在鏈接的列表中找到插入位置的代碼要簡單得多。

if (next != null && next.compareTo(insertElement) > 0){ 
    // You have the right location 
}

來源

2013-05-26 22:07:05 greedybuddha

我不確定PriorityQueue或LinkedList是最適合我使用的（我真的應該在原始文章中提到，現在已經修復）。 – user2423158

那麼，我不得不說你不想使用LinkedList b/c的原因，那麼將ArrayList轉換爲C＃會更容易。兩者同樣易於翻譯（我甚至會說LinkedList更容易）。但最重要的是你不能在ArrayList的中間插入一個元素而不移動它之後的所有元素。這涉及複製ArrayList的那部分，比LinkedList插入要慢得多。基本上，如果你正在尋找效率，你正在使用錯誤的數據結構。 – greedybuddha

有使用可以使用的，而不是名單就像一棵樹其他數據結構，優先級隊列等

來源

2013-05-26 22:26:10 Ayodeji

由於熟悉並且易於訪問任何給定的元素，我與Arraylist一起去了。然而，另一個數據結構可能是一個好主意，但我必須先做一些研究。 – user2423158

前面已經指出的那樣，沒有理由自己去實現這一點，簡單的代碼示例：

 


    class FooBar implements Comparable<FooBar> { 

     String name; 

     @Override 
     public int compareTo(FooBar other) { 
      return name.compareTo(other.name); 
     } 
    } 

    TreeSet<FooBar> foobarSet = new TreeSet<>(); 
    FooBar f1; 
    foobarSet.add(new FooBar("2")); 
    foobarSet.add(f1 = new FooBar("1")); 

    int index = foobarSet.headSet(f1).size();

（基於How to find the index of an element in a TreeSet?）

來源

2013-05-26 22:49:58 mrak

我也認爲我們應該使用可排序的列表。在答案中，我們使用了Comparable。另一個選擇是使用比較器。 – Stony

我認爲這個問題是在此位的代碼：

else if (test < entry) 
{ 
    int tempPiv = pivot; 
    pivot = oldPivot - (oldPivot - pivot)/2; 
    oldPivot = tempPiv; 
} 
else 
{ 
    int tempPiv = pivot; 
    pivot = pivot - (oldPivot - pivot)/2; 
    oldPivot = tempPiv; 
}

您正在執行相同的操作，其中進入或進入測試>進入或進入測試> <。當您正在搜索的項目位於數組的開頭時，這將導致線性搜索。

我更喜歡使用（高）像

high = list.size(); 
low = 0; 

do { 
    pivot = (high + low)/2; 
    if (test < entry) { 
     low = pivot; 
    } else if (test > entry) { 
     high = pivot 
    } else { 
     .... 
    } 
} while ...;

來源

2013-05-27 01:37:35

爲什麼不是接受的答案（如果@ user2423158想接受一個...）？它具有在數組O（log（n））中工作的關鍵。謝謝！ – Matthieu

@Matthieu感謝你的投票，我懷疑用戶希望他的問題得到解答，並在此之後沒有興趣 –

使自己的列表實現，並在你的add方法有如下幾行：

wrappedList.add(object); 
Collections.sort(wrappedList);

來源

2013-05-27 01:40:14 hd1

插入一個已排序列表

回答

相關問題