插入已排序的列表中 [英] 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.

编辑零件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实例)，则应使用列表.要将元素插入到已排序的列表中很简单:

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屋！