将元素插入到已排序的列表中

Question

使用Java，我有一个类称为TestClass，它有一个名为Name的成员，即一个字符串。我还有一个此类型的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#缺少它，则必须完全重写。

编辑第二部分：发现自己做错了。我应该设置和更改我正在检查的区域的边界，并基于此创建新的支点。

- user2423158

---

为什么不直接插入所有元素，然后使用 Collections.sort() 呢？ - fge

也许我没有正确地看待这个问题，但是如果您确定该值在所选（测试）点之后，那么您会检查数组的第二半部分吗？ - lurker

@fge，每次插入后重新排序可能是最慢的方法，尽管速度不是我的最大关注点，因为不太可能有许多对象被快速地移进和移出。 - user2423158

@mbratch，这就是我想做的事情，但很可能我的尝试完全错误，这也是我遇到问题的地方。 - user2423158

@user2423158 这取决于这个排序列表被访问的频率。如果不是很频繁，您可以在需要时重新构建该列表。 - fge

Answer 1

对于这种情况，使用SortedSet（例如TreeSet）可能不是一个好主意，因为Set不允许重复的元素。如果您有重复的元素（即具有相同名称的TestClass实例），则应该使用List。将元素插入到已排序的列表中就像这样简单：

void insert(List<TestClass> list, TestClass element) {
    int index = Collections.binarySearch(list, element, Comparator.comparing(TestClass::getName));
    if (index < 0) {
        index = -index - 1;
    }
    list.add(index, element);
}

这段代码需要Java 8或更高版本，但也可以重写以适用于旧版Java。

- Daniel Beer

---

这与树无关。集合不允许重复元素。 - Ravjit Singh

谢谢您指出这一点。我已经相应地更改了措辞。 - Daniel Beer

Answer 2

正如已经指出的那样，没有理由自己实现这个功能，以下是简单的代码示例：

    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();

(基于如何在TreeSet中找到元素的索引？)

- mrak

---

我也认为我们应该使用可排序列表。在答案中，我们使用Comparable。另一个选项是使用Comparator。 - Stony

Answer 3

我认为问题出在这段代码中：

我认为问题出在这段代码中：

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;
}

您正在执行相同的操作，无论是测试 < 还是测试 > entry。当您要查找的项位于数组开头时，这将导致线性搜索。

我更喜欢使用 (low 和 high) 像：

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

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

- Bruce Martin

---

为什么那不是被接受的答案（如果@user2423158想要接受一个答案...）？它具有在数组上以O(log(n))工作的关键。谢谢！ - Matthieu

@Matthieu 谢谢你的点赞，我猜这位用户只是想得到他的问题的答案，之后就不再关心了。 - Bruce Martin

Answer 4

你应该使用类似于PriorityQueue这样已经有序的集合。将元素插入到具有顺序感的集合中，会自动将元素放置在正确的位置上，时间最短（通常为log(n)或更少）。

如果您想进行任意插入而不需要这个功能，则建议使用LinkedList，它不必重新排序或完全复制以插入像ArrayList一样的单个项目。虽然在LinkedList中查找正确的插入位置最多需要O(n)的时间，但在实践中，它仍然比在ArrayList中使用log(n)搜索正确位置，然后需要复制或排序要快得多。

此外，在LinkedList中查找插入位置的代码要简单得多。

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

- greedybuddha

---

我不确定PriorityQueue或LinkedList是否最适合我在使用它时的情况（这是我在原始帖子中应该提到的，现在已经修复了）。 - user2423158

我必须说，你不想使用LinkedList的原因是因为它更容易将ArrayList翻译成C#并不正确。两者同样容易翻译（我甚至会说LinkedList更容易）。但最重要的是，如果你在ArrayList中间插入一个元素，就需要移动其后面的所有元素。这涉及到复制ArrayList的那一部分，比LinkedList插入慢得多。基本上，如果你想要效率，你正在使用错误的数据结构。 - greedybuddha

ArrayList在容量达到一定阈值或负载因子增加时会调整大小，否则添加操作为O(1)。 - Mohsin Ejaz

即使 ArrayList 在 O(1) 时间内调整大小，为了插入一个元素并保持排序列表，您需要“移动”大于该元素的所有内容，然后将元素插入到正确位置。 移动的时间复杂度为 O(N)。 - greedybuddha

Answer 5

除了列表之外，还可以使用其他数据结构，如树、优先队列等。

- Ayodeji

---

我选择了ArrayList，因为我对它很熟悉，并且可以轻松访问任何给定的元素。然而，另一种数据结构可能也是一个好主意，尽管我需要先进行一些研究。 - user2423158

Answer 6

自己实现一个列表，并在添加方法中加入以下代码：

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

- hd1