在 Java 中手动排序链表（按词法）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1854870/
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
Manually sorting a linked list in Java (lexically)
提问by Aaron
I am implementing my own linked list in Java. The node class merely has a string field called "name" and a node called "link". Right now I have a test driver class that only inserts several names sequentially. Now, I am trying to write a sorting method to order the nodes alphabetically, but am having a bit of trouble with it. I found this pseudocode of a bubblesort from someone else's post and tried to implement it, but it doesn't fully sort the entries. I'm not really quite sure why. Any suggestions are appreciated!
我正在用 Java 实现我自己的链表。节点类只有一个名为“name”的字符串字段和一个名为“link”的节点。现在我有一个测试驱动程序类，它只按顺序插入几个名称。现在，我正在尝试编写一种排序方法来按字母顺序对节点进行排序，但是遇到了一些麻烦。我从其他人的帖子中找到了这个冒泡排序的伪代码并试图实现它，但它没有完全对条目进行排序。我不太确定为什么。任何建议表示赞赏！
private void sort()
{
//Enter loop only if there are elements in list
boolean swapped = (head != null);
// Only continue loop if a swap is made
while (swapped)
{
swapped = false;
// Maintain pointers
Node curr = head;
Node next = curr.link;
Node prev = null;
// Cannot swap last element with its next
while (next != null)
{
// swap if items in wrong order
if (curr.name.compareTo(next.name) < 0)
{
// notify loop to do one more pass
swapped = true;
// swap elements (swapping head in special case
if (curr == head)
{
head = next;
Node temp = next.link;
next.link = curr;
curr.link = temp;
curr = head;
}
else
{
prev.link = curr.link;
curr.link = next.link;
next.link = curr;
curr = next;
}
}
// move to next element
prev = curr;
curr = curr.link;
next = curr.link;
}
}
}
回答by Carl Smotricz
I spent some minutes eyeballing your code for errors but found none.
我花了几分钟观察你的代码是否有错误，但没有发现。
I'd say until someone smarter or more hard working comes along you should try debugging this on your own. If you have an IDE like Eclipse you can single-step through the code while watching the variables' values; if not, you can insert print statements in a few places and hand-check what you see with what you expected.
我会说，直到有人更聪明或更努力工作出现之前，您应该尝试自己调试。如果您有像 Eclipse 这样的 IDE，您可以在查看变量值的同时单步执行代码；如果没有，您可以在几个地方插入打印语句，并根据您的预期手动检查您所看到的内容。
UPDATE I
更新我
I copied your code and tested it. Apart from the fact that it sorts in descending order (which may not be what you intended) it worked perfectly for a sample of 0, 1 and 10 random nodes. So where's the problem?
我复制了您的代码并对其进行了测试。除了它按降序排序（这可能不是您想要的）这一事实之外，它还非常适合 0、1 和 10 个随机节点的样本。那么问题出在哪里呢？
UPDATE II
更新二
Still guessing what could be meant by "it doesn't fully sort the entries." It's possible that you're expecting lexicographic sorting (i.e. 'a' before 'B'), and that's not coming out as planned for words with mixed upper/lower case. The solution in this case is to use the Stringmethod compareToIgnoreCase(String str).
仍在猜测“它没有对条目进行完全排序”的含义。您可能期望按字典排序（即在 'B' 之前的 'a'），而对于混合大写/小写的单词，这并没有按计划出现。这种情况下的解决方案是使用String方法compareToIgnoreCase(String str)。
回答by Carl Smotricz
This may not be the solution you're looking for, but it's nice and simple. Maybe you're lazy like I am.
这可能不是您正在寻找的解决方案，但它很好而且很简单。可能你和我一样懒。
Since your nodes contain only a single item of data, you don't really need to re-shuffle your nodes; you could simply exchange the values on the nodes while leaving the list's structure itself undisturbed.
由于您的节点仅包含一项数据，因此您实际上不需要重新洗牌您的节点；您可以简单地交换节点上的值，同时保持列表结构本身不受干扰。
That way, you're free to implement Bubble Sort quite simply.
这样，您就可以非常简单地实现冒泡排序。
回答by pstanton
you should use the sorting procedures supplied by the language.
您应该使用该语言提供的排序程序。
Basically, you need your element class to implement java.lang.Comparable, in which you will just delegate to obj.name.compareTo(other.name)
基本上，您需要您的元素类来实现 java.lang.Comparable，您只需委托给 obj.name.compareTo(other.name)
you can then use Collections.sort(yourCollection)
然后你可以使用 Collections.sort(yourCollection)
alternatively you can create a java.util.Comparator that knows how to compare your objects
或者，您可以创建一个知道如何比较对象的 java.util.Comparator
回答by sergtk
To obtain good performance you can use Merge Sort. Its time complexity is O(n*log(n)) and can be implemented without memory overhead for lists.
为了获得良好的性能，您可以使用Merge Sort。它的时间复杂度是 O(n*log(n)) 并且可以在没有内存开销的情况下实现列表。
Bubble sort is not good sorting approach. You can read the What is a bubble sort good for?for details.
冒泡排序不是好的排序方法。您可以阅读什么是冒泡排序的好处？详情。
回答by WarmWaffles
This may be a little too late. I would build the list by inserting everything in order to begin with because sorting a linked list is not fun.
这可能有点太晚了。我会通过插入所有内容来构建列表，因为排序链接列表并不有趣。
I'm positive your teacher or professor doesn't want you using java's native library. However that being said, there is no real fast way to resort this list.
我很确定你的老师或教授不希望你使用 java 的本地库。尽管如此，没有真正快速的方法来使用这个列表。
You couldread all the nodes in the order that they are in and store them into an array. Sort the array and then relink the nodes back up. I think the Big-Oh complexity of this would be O(n^2) so in reality a bubble sort with a linked list is sufficient
您可以按照它们所在的顺序读取所有节点并将它们存储到一个数组中。对数组进行排序，然后重新链接节点。我认为这个的 Big-Oh 复杂度是 O(n^2) 所以实际上带有链表的冒泡排序就足够了
回答by Bhumik Thakkar
I have done merge sort on the singly linked list and below is the code.
我已经对单向链表进行了归并排序，下面是代码。
public class SortLinkedList {
public static Node sortLinkedList(Node node) {
if (node == null || node.next == null) {
return node;
}
Node fast = node;
Node mid = node;
Node midPrev = node;
while (fast != null && fast.next != null) {
fast = fast.next.next;
midPrev = mid;
mid = mid.next;
}
midPrev.next = null;
Node node1 = sortLinkedList(node);
Node node2 = sortLinkedList(mid);
Node result = mergeTwoSortedLinkedLists(node1, node2);
return result;
}
public static Node mergeTwoSortedLinkedLists(Node node1, Node node2) {
if (null == node1 && node2 != null) {
return node2;
} else if (null == node2 && node1 != null) {
return node1;
} else if (null == node1 && null == node2) {
return null;
} else {
Node result = node1.data <= node2.data ? node1 : node2;
Node prev1 = null;
while (node1 != null && node2 != null) {
if (node1.data <= node2.data) {
prev1 = node1;
node1 = node1.next;
} else {
Node next2 = node2.next;
node2.next = node1;
if (prev1 != null) {
prev1.next = node2;
}
node1 = node2;
node2 = next2;
}
}
if (node1 == null && node2 != null) {
prev1.next = node2;
}
return result;
}
}
public static void traverseNode(Node node) {
while (node != null) {
System.out.print(node + " ");
node = node.next;
}
System.out.println();
}
public static void main(String[] args) {
MyLinkedList ll1 = new MyLinkedList();
ll1.insertAtEnd(10);
ll1.insertAtEnd(2);
ll1.insertAtEnd(20);
ll1.insertAtEnd(4);
ll1.insertAtEnd(9);
ll1.insertAtEnd(7);
ll1.insertAtEnd(15);
ll1.insertAtEnd(-3);
System.out.print("list: ");
ll1.traverse();
System.out.println();
traverseNode(sortLinkedList(ll1.start));
}
}
}
The Node class:
节点类：
public class Node {
int data;
Node next;
public Node() {
data = 0;
next = null;
}
public Node(int data) {
this.data = data;
}
public int getData() {
return this.data;
}
public Node getNext() {
return this.next;
}
public void setData(int data) {
this.data = data;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public String toString() {
return "[ " + data + " ]";
}
}
}
The MyLinkedList class:
MyLinkedList 类：
public class MyLinkedList {
Node start;
public void insertAtEnd(int data) {
Node newNode = new Node(data);
if (start == null) {
start = newNode;
return;
}
Node traverse = start;
while (traverse.getNext() != null) {
traverse = traverse.getNext();
}
traverse.setNext(newNode);
}
public void traverse() {
if (start == null)
System.out.println("List is empty");
else {
Node tempNode = start;
do {
System.out.print(tempNode.getData() + " ");
tempNode = tempNode.getNext();
} while (tempNode != null);
System.out.println();
}
}
}
}
