插入已排序的列表 [英] Insert into an already-sorted list

问题描述

在 Java 中，我有一个名为 TestClass 的类，它有一个名为 Name 的成员，它是一个字符串.我还有一个这种类型的 ArrayList，它已经按名称的字母顺序排序.我想要做的是找到最好的索引来放置一个新的 TestClass 实例.到目前为止，我能想到的最好方法是:

With Java, I have a class, known as TestClass, which has a member named Name, which is a string. I also have an ArrayList of this type, which is already sorted alphabetically by Name. What I want to do is find the best index in which to put a new instance of TestClass. The best approach I could come up with so far is this:

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

本质上，将数组分成两半，检查您的值是在那个点之前、之后还是那个点.如果在后面，请检查数组的前半部分.否则，请检查下半场.然后，重复.我知道此方法仅通过第一个字符进行测试，但这很容易修复，并且与我的主要问题无关.对于某些场景，这种方法效果很好.对于大多数人来说，它的效果非常糟糕.我认为它没有正确找到新的枢轴点，如果是这种情况，我该如何解决?

Essentially, Break the array in half, check to see if your value goes before, after, or at that point. If it's after, check the first half of the array. Other wise, check the second half. Then, repeat. I understand that this method only tests by the first character, but that's easily fixed, and not relevant to my main problem. For some scenarios, this approach works well enough. For most, it works horribly. I assume that it isn't finding the new pivot point properly, and if that's the case, how would I fix it?

为了澄清起见，我将其用于库存系统，因此我不确定 LinkedList 是否合适.我正在使用 ArrayList 是因为它们对我来说更熟悉，因此如果需要，将更容易翻译成另一种语言(目前可能会转移到 C#).由于这个原因，我试图避免使用 Comparable 之类的东西，因为如果 C# 缺少它，我将不得不完全重新编写.

For clarification, I'm using this for an inventory system, so I'm not sure a LinkedList would be appropriate. I'm using an ArrayList because they are more familiar to me, and thus would be easier to translate into another language, if needed (which is likely, at the moment, might be moving over to C#). I'm trying to avoid things like Comparable for that reason, as I'd have to completely re-write if C# lacks it.

Edit part Duex:找出我做错了什么.我应该设置和更改我正在检查的区域的边界，并在此基础上创建新的轴心点，而不是使用之前的轴心点.

Edit part Duex: Figured out what I was doing wrong. Instead of using the previous pivot point, I should have been setting and changing the boundaries of the area I was checking, and creating the new pivot based on that.

推荐答案

为此使用 SortedSet(例如 TreeSet)可能不是一个好主意，因为 Set 不允许重复元素.如果您有重复的元素(即具有相同名称的 TestClass 实例)，则应使用 List.将元素插入到已经排序的列表中就像这样简单:

It might not be a good idea to use a SortedSet (e.g. a TreeSet) for this, because Set‘s don't allow duplicate elements. If you have duplicate elements (i.e. TestClass instances with the same name), then a List should be used. To insert an element into an already sorted list is as simple as this:

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 版本中工作.

This code requires Java 8 or later, but can be rewritten to work in older Java versions as well.

这篇关于插入已排序的列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！