java 插入已排序的列表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16764007/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Insert into an already-sorted list
提问by user2423158
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:
在 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;
}
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?
本质上，将数组分成两半，检查您的值是在那个点之前、之后还是那个点。如果在后面，请检查数组的前半部分。否则，请检查下半场。然后，重复。我知道此方法仅通过第一个字符进行测试，但这很容易修复，并且与我的主要问题无关。对于某些场景，这种方法效果很好。对于大多数人来说，它的效果非常糟糕。我认为它没有正确找到新的枢轴点，如果是这种情况，我该如何解决？
Edit: 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.
编辑：为了澄清起见，我将它用于库存系统，所以我不确定 LinkedList 是否合适。我正在使用 ArrayList 是因为它们对我来说更熟悉，因此如果需要，将更容易翻译成另一种语言（目前可能会转移到 C#）。由于这个原因，我试图避免使用 Comparable 之类的东西，因为如果 C# 缺少它，我将不得不完全重新编写。
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.
编辑部分 Duex：找出我做错了什么。我应该设置和更改我正在检查的区域的边界，并在此基础上创建新的枢轴点，而不是使用以前的枢轴点。
回答by Daniel Beer
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:
为此使用 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);
}
This code requires Java 8 or later, but can be rewritten to work in older Java versions as well.
此代码需要 Java 8 或更高版本，但也可以重写以在较旧的 Java 版本中工作。
回答by mrak
As already pointed out, there is no reason to implement this by yourself, simple code example:
正如已经指出的，没有理由自己实现这一点，简单的代码示例：
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();
(Based on How to find the index of an element in a TreeSet?)
回答by Bruce Martin
I think the problem is in this bit of the code:
我认为问题出在这段代码中：
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;
}
You are peforming the same actions wether test < entry or wether test > entry. This will lead to a linear search when the item you are searching for is at the start of the array.
您正在执行相同的操作，无论是 test < entry 还是 wether test > entry。当您要搜索的项目位于数组的开头时，这将导致线性搜索。
I prefer to use (low and high) like
我更喜欢使用（低和高）
high = list.size();
low = 0;
do {
pivot = (high + low) / 2;
if (test < entry) {
low = pivot;
} else if (test > entry) {
high = pivot
} else {
....
}
} while ...;
回答by greedybuddha
You should use something like a PriorityQueue that already has a sense of order. Inserting into a collection with a sense of order will automatically place the element in the correct place with minimal time(usually log(n) or less).
你应该使用像 PriorityQueue 这样已经有秩序感的东西。以有序的方式插入到集合中将自动将元素以最少的时间（通常为 log(n) 或更少）放置在正确的位置。
If you want to do arbitrary inserts without this, then I would suggest using a LinkedList that won't have to be resorted or completely copied over to insert a single item like the ArrayList you currently have. While finding the correct insert location for a LinkedList will take up to O(n) time, in practice it will still be faster than using a log(n) search for the correct location in an ArrayList, but then needing to copy or sort it afterwards.
如果你想在没有这个的情况下进行任意插入，那么我建议使用一个 LinkedList ，它不必重新使用或完全复制来插入单个项目，比如你目前拥有的 ArrayList 。虽然为 LinkedList 找到正确的插入位置将花费 O(n) 时间，但实际上它仍然比使用 log(n) 搜索 ArrayList 中的正确位置要快，但随后需要对其进行复制或排序然后。
Also the code for finding the insert location in a linked list is much simpler.
此外，在链表中查找插入位置的代码要简单得多。
if (next != null && next.compareTo(insertElement) > 0){
// You have the right location
}
回答by Ayodeji
There are other data structures used could use instead of list like a tree, priority queue etc.
还可以使用其他数据结构来代替列表，例如树、优先级队列等。
回答by hd1
Make a list implementation of your own, and in your add method have these lines:
制作您自己的列表实现，并在您的 add 方法中有以下几行：
wrappedList.add(object);
Collections.sort(wrappedList);
