插入一个已排序列表

使用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

插入一个已排序列表

回答

相关问题