插入排序的 LinkedList Java
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/18144820/
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
Inserting into Sorted LinkedList Java
提问by cloudviz
I have this code below where I am inserting a new integer into a sorted LinkedList of ints but I do not think it is the "correct" way of doing things as I know there are singly linkedlist with pointer to the next value and doubly linkedlist with pointers to the next and previous value. I tried to use Nodes to implement the below case but Java is importing this import org.w3c.dom.Node (document object model) so got stuck.
我在下面有这段代码，我将一个新整数插入到一个排序的整数 LinkedList 中，但我认为这不是“正确”的做事方式，因为我知道有指向下一个值的单链表和双链表指向下一个和上一个值的指针。我尝试使用 Nodes 来实现以下案例，但 Java 正在导入这个 import org.w3c.dom.Node（文档对象模型），所以卡住了。
Insertion Cases
插入案例
- Insert into Empty Array
- If value to be inserted less than everything, insert in the beginning.
- If value to be inserted greater than everything, insert in the last.
Could be in between if value less than/greater than certain values in LL.
import java.util.*; public class MainLinkedList { public static void main(String[] args) { LinkedList<Integer> llist = new LinkedList<Integer>(); llist.add(10); llist.add(30); llist.add(50); llist.add(60); llist.add(90); llist.add(1000); System.out.println("Old LinkedList " + llist); //WHat if you want to insert 70 in a sorted LinkedList LinkedList<Integer> newllist = insertSortedLL(llist, 70); System.out.println("New LinkedList " + newllist); } public static LinkedList<Integer> insertSortedLL(LinkedList<Integer> llist, int value){ llist.add(value); Collections.sort(llist); return llist; }}
- 插入空数组
- 如果要插入的值小于所有值，则在开头插入。
- 如果要插入的值大于所有值，则插入最后一个。
如果值小于/大于 LL 中的某些值，则可能介于两者之间。
import java.util.*; public class MainLinkedList { public static void main(String[] args) { LinkedList<Integer> llist = new LinkedList<Integer>(); llist.add(10); llist.add(30); llist.add(50); llist.add(60); llist.add(90); llist.add(1000); System.out.println("Old LinkedList " + llist); //WHat if you want to insert 70 in a sorted LinkedList LinkedList<Integer> newllist = insertSortedLL(llist, 70); System.out.println("New LinkedList " + newllist); } public static LinkedList<Integer> insertSortedLL(LinkedList<Integer> llist, int value){ llist.add(value); Collections.sort(llist); return llist; }}
采纳答案by Master
This might serve your purpose perfectly:
这可能完全符合您的目的：
Use this code:
使用此代码：
import java.util.*;
public class MainLinkedList {
private static LinkedList<Integer> llist;
public static void main(String[] args) {
llist = new LinkedList<Integer>();
addValue(60);
addValue(30);
addValue(10);
addValue(-5);
addValue(1000);
addValue(50);
addValue(60);
addValue(90);
addValue(1000);
addValue(0);
addValue(100);
addValue(-1000);
System.out.println("Linked List is: " + llist);
}
private static void addValue(int val) {
if (llist.size() == 0) {
llist.add(val);
} else if (llist.get(0) > val) {
llist.add(0, val);
} else if (llist.get(llist.size() - 1) < val) {
llist.add(llist.size(), val);
} else {
int i = 0;
while (llist.get(i) < val) {
i++;
}
llist.add(i, val);
}
}
}
This one method will manage insertion in the List in sorted manner without using Collections.sort(list)
这一种方法将以排序方式管理列表中的插入，而无需使用 Collections.sort(list)
回答by Christophe Roussy
You have to find where to insert the data by knowing the order criteria.
您必须通过了解订单条件来找到插入数据的位置。
The simple method is to brute force search the insert position (go through the list, binary search...).
简单的方法是蛮力搜索插入位置（遍历列表，二进制搜索......）。
Another method, if you know the nature of your data, is to estimate an insertion position to cut down the number of checks. For example if you insert 'Zorro' and the list is alphabetically ordered you should start from the back of the list... or estimate where your letter may be (probably towards the end). This can also work for numbers if you know where they come from and how they are distributed. This is called interpolation search: http://en.wikipedia.org/wiki/Interpolation_search
如果您知道数据的性质，另一种方法是估计插入位置以减少检查次数。例如，如果您插入“Zorro”并且列表按字母顺序排列，您应该从列表的后面开始……或者估计您的信件可能在哪里（可能在最后）。如果您知道数字的来源和分布方式，这也适用于数字。这称为插值搜索：http: //en.wikipedia.org/wiki/Interpolation_search
Also think about batch insert: If you insert a lot of data quickly you may consider doing many insertions in one go and only sort once afterwards.
还要考虑批量插入：如果您快速插入大量数据，您可能会考虑一次性进行多次插入，然后只排序一次。
回答by Atrakeur
Linked list isn't the better implementation for a SortedList
链表不是 SortedList 的更好实现
Also, sorting all the list each time you add a new element isn't efficient. The best way is to insert the element directly where it has to be (at his correct position). For this, you can loop all the positions to find where this number belong to, then insert it, or use Collections.binarySearch to let this highly optimised search algorithm do this job for you.
此外，每次添加新元素时对所有列表进行排序效率不高。最好的方法是将元素直接插入它必须在的地方（在他正确的位置）。为此，您可以循环所有位置以找到该数字所属的位置，然后插入它，或使用 Collections.binarySearch 让这个高度优化的搜索算法为您完成这项工作。
BinarySearch return the index of the object if the object is found in the list (you can check for duplicates here if needed) or (-(insertion point) - 1) if the object isn't allready in the list (and insertion point is the index where the object need to be placed to maintains order)
如果在列表中找到对象（如果需要，您可以在此处检查重复项）或 (-(insertion point) - 1) 如果对象不在列表中（并且插入点是需要放置对象以保持顺序的索引）
回答by Greg Brown
@Atrakeur
@Arakeur
"sorting all the list each time you add a new element isn't efficient"
“每次添加新元素时对所有列表进行排序效率不高”
That's true, but if you need the list to always be in a sorted state, it is really the only option.
确实如此，但如果您需要列表始终处于排序状态，那么它确实是唯一的选择。
"The best way is to insert the element directly where it has to be (at his correct position). For this, you can loop all the positions to find where this number belong to"
“最好的方法是将元素直接插入它必须在的位置（在他正确的位置）。为此，您可以循环所有位置以找到该数字所属的位置”
This is exactly what the example code does.
这正是示例代码所做的。
"or use Collections.binarySearch to let this highly optimised search algorithm do this job for you"
“或使用 Collections.binarySearch 让这个高度优化的搜索算法为您完成这项工作”
Binary search is efficient, but only for random-access lists. So you could use an array list instead of a linked list, but then you have to deal with memory copies as the list grows. You're also going to consume more memory than you need if the capacity of the list is higher than the actual number of elements (which is pretty common).
二进制搜索是有效的，但仅适用于随机访问列表。因此，您可以使用数组列表而不是链接列表，但是随着列表的增长，您必须处理内存副本。如果列表的容量高于元素的实际数量（这很常见），您也会消耗比所需更多的内存。
So which data structure/approach to take is going to depend a lot on your storage and access requirements.
因此，采用哪种数据结构/方法将在很大程度上取决于您的存储和访问要求。
[edit] Actually, there is one problem with the sample code: it results in multiple scans of the list when looping.
[编辑] 实际上，示例代码存在一个问题：循环时会导致多次扫描列表。
int i = 0;
while (llist.get(i) < val) {
i++;
}
llist.add(i, val);
The call to get(i) is going to traverse the list once to get to the ith position. Then the call to add(i, val) traverses it again. So this will be very slow.
对 get(i) 的调用将遍历列表一次以到达第 i 个位置。然后调用 add(i, val) 再次遍历它。所以这会很慢。
A better approach would be to use a ListIterator to traverse the list and perform insertion. This interface defines an add() method that can be used to insert the element at the current position.
更好的方法是使用 ListIterator 遍历列表并执行插入。该接口定义了一个 add() 方法，可用于在当前位置插入元素。
回答by Amruth
If we use listIterator the complexity for doing get will be O(1).
如果我们使用 listIterator，执行 get 的复杂度将是 O(1)。
public class OrderedList<T extends Comparable<T>> extends LinkedList<T> {
private static final long serialVersionUID = 1L;
public boolean orderedAdd(T element) {
ListIterator<T> itr = listIterator();
while(true) {
if (itr.hasNext() == false) {
itr.add(element);
return(true);
}
T elementInList = itr.next();
if (elementInList.compareTo(element) > 0) {
itr.previous();
itr.add(element);
System.out.println("Adding");
return(true);
}
}
}
}
回答by DanJ
Have a look at com.google.common.collect.TreeMultiset.
看看com.google.common.collect.TreeMultiset。
This is effectively a sorted set that allows multiple instances of the same value.
这实际上是一个排序集，允许相同值的多个实例。
It is a nice compromise for what you are trying to do. Insertion is cheaper than ArrayList, but you still get search benefits of binary/tree searches.
对于您正在尝试做的事情，这是一个很好的妥协。插入比 ArrayList 便宜，但您仍然可以获得二叉/树搜索的搜索优势。
回答by NIKUNJ KHOKHAR
You can do it in log (N) time Complexity simply. No need to iterate through all the values. you can use binary search to add value to sorted linked list.just add the value at the position of upper bound of that function. Check code... you may understand better.
您可以简单地在 log (N) 时间复杂度中完成。无需遍历所有值。您可以使用二分搜索将值添加到已排序的链表中。只需在该函数的上界位置添加值即可。检查代码......你可能会更好地理解。
public static int ubound(LinkedList<Integer> ln, int x) {
int l = 0;
int h = ln.size();
while (l < h) {
int mid = (l + h) / 2;
if (ln.get(mid) <= x) l = mid + 1;
else h = mid;
}
return l;
}
public void solve()
{
LinkedList<Integer> ln = new LinkedList<>();
ln.add(4);
ln.add(6);
ln.add(ubound(ln, 5), 5);
out.println(ln);
}
Output : [4, 5, 6]
输出：[4, 5, 6]
you can learn about binary search more at : https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search/
您可以在以下位置了解更多二分搜索：https: //www.topcoder.com/community/data-science/data-science-tutorials/binary-search/
