在 Java 中手动冒泡排序链接列表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/29869094/
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
Bubble Sort Manually a Linked List in Java
提问by Caico
This is my first question here. I am trying to manually sort a linked list of integers in java and I can not figure out what is wrong with my code. Any suggestions? I don't get any error, however I still have my output unordered. I tried a few different ways, but nothing worked. I appreciate if anyone can help me with that.
这是我在这里的第一个问题。我正在尝试手动对 java 中的整数链表进行排序，但我无法弄清楚我的代码有什么问题。有什么建议？我没有收到任何错误，但是我的输出仍然是无序的。我尝试了几种不同的方法，但没有任何效果。如果有人可以帮助我，我很感激。
public class Node {
int data;
Node nextNode;
public Node(int data) {
this.data = data;
this.nextNode = null;
}
public int getData() {
return this.data;
}
} // Node class
public class DataLinkedList implements DataInterface {
private Node head;
private int size;
public DataLinkedList(){
this.head = null;
this.size = 0;
}
public void add(int data) {
Node node = new Node(data);
if (head == null) {
head = node;
} else {
Node currentNode = head;
while(currentNode.nextNode != null) {
currentNode = currentNode.nextNode;
}
currentNode.nextNode = node;
}
size++;
}
public void sort() {
if (size > 1) {
for (int i = 0; i < size; i++ ) {
Node currentNode = head;
Node next = head.nextNode;
for (int j = 0; j < size - 1; j++) {
if (currentNode.data > next.data) {
Node temp = currentNode;
currentNode = next;
next = temp;
}
currentNode = next;
next = next.nextNode;
}
}
}
}
public int listSize() {
return size;
}
public void printData() {
Node currentNode = head;
while(currentNode != null) {
int data = currentNode.getData();
System.out.println(data);
currentNode = currentNode.nextNode;
}
}
public boolean isEmpty() {
return size == 0;
}
} // DataInterface class
public class DataApp {
public static void main (String[]args) {
DataLinkedList dll = new DataLinkedList();
dll.add(8);
dll.add(7);
dll.add(6);
dll.add(4);
dll.add(3);
dll.add(1);
dll.sort();
dll.printData();
System.out.println(dll.listSize());
}
} // DataApp class
回答by Baltasarq
The problem, as expected, comes in method sort():
正如预期的那样，问题出现在方法中sort()：
public void sort() {
if (size > 1) {
for (int i = 0; i < size; i++ ) {
Node currentNode = head;
Node next = head.nextNode;
for (int j = 0; j < size - 1; j++) {
if (currentNode.data > next.data) {
Node temp = currentNode;
currentNode = next;
next = temp;
}
currentNode = next;
next = next.nextNode;
}
}
}
}
A minor problem is just do always execute the bubble sort n*n times. It is actually better check whether there was a change between any pair in the list. If it was, then there is the need to run again all over the list; if not, there isn't. Think of the marginal case in which a list of 100 elements is already sorted when sort()is called. This means that nodes in the list would be run over for 10000 times, even when there is actually nothing to do!
一个小问题是总是执行冒泡排序 n*n 次。实际上最好检查列表中的任何对之间是否有变化。如果是，则需要在整个列表中再次运行；如果没有，就没有。考虑在sort()调用时已经对 100 个元素的列表进行排序的边缘情况。这意味着列表中的节点将被运行 10000 次，即使实际上无事可做！
The main problem, though, is that you are exchanging pointers to the nodes in your list.
但是，主要问题是您正在交换指向列表中节点的指针。
if (currentNode.data > next.data) {
Node temp = currentNode;
currentNode = next;
next = temp;
}
If you translate currentNodeby v[i]and nextby v[i - 1], as if you were sorting an array, that would do. However, you are just changing pointers that you use to run over the list, without effect in the list itself. The best solution (well, provided you are going to use BubbleSort, which is always the worst solution) would be to exchange the data inside the nodes.
如果您将currentNodebyv[i]和nextby翻译v[i - 1]，就像您在对数组进行排序一样，那就可以了。但是，您只是更改用于在列表上运行的指针，而不会对列表本身产生影响。最好的解决方案（好吧，前提是您要使用BubbleSort，这始终是最差的解决方案）是在节点内交换数据。
if (currentNode.data > next.data) {
int temp = currentNode.data;
currentNode.data = next.data;
next.data = temp;
}
However, for a matter of illustration of the concept, I'm going to propose changing the links among nodes. These pointers are the ones which actually mark the sorting in the list. I'm talking about the nextNodeattribute in the Nodeclass.
但是，为了说明这个概念，我将建议更改节点之间的链接。这些指针实际上是在列表中标记排序的指针。我说的nextNode是Node类中的属性。
Enough chat, here it is:
聊够了，这里是：
public void sort() {
if (size > 1) {
boolean wasChanged;
do {
Node current = head;
Node previous = null;
Node next = head.nextNode;
wasChanged = false;
while ( next != null ) {
if (current.data > next.data) {
/*
// This is just a literal translation
// of bubble sort in an array
Node temp = currentNode;
currentNode = next;
next = temp;*/
wasChanged = true;
if ( previous != null ) {
Node sig = next.nextNode;
previous.nextNode = next;
next.nextNode = current;
current.nextNode = sig;
} else {
Node sig = next.nextNode;
head = next;
next.nextNode = current;
current.nextNode = sig;
}
previous = next;
next = current.nextNode;
} else {
previous = current;
current = next;
next = next.nextNode;
}
}
} while( wasChanged );
}
}
The explanation for a "double" code managing the node exchange is that, since you have to change the links among nodes, and this is just a single linked list, then you have to keep track of the previous node (you don't have a header node, either), which the first time is head.
管理节点交换的“双重”代码的解释是，由于您必须更改节点之间的链接，而这只是一个单链表，那么您必须跟踪前一个节点（您没有一个头节点，或者），第一次是head。
if ( previous != null ) {
Node sig = next.nextNode;
previous.nextNode = next;
next.nextNode = current;
current.nextNode = sig;
} else {
Node sig = next.nextNode;
head = next;
next.nextNode = current;
current.nextNode = sig;
}
You can find the code in IdeOne, here: http://ideone.com/HW5zw7
您可以在 IdeOne 中找到该代码：http://ideone.com/HW5zw7
Hope this helps.
希望这可以帮助。
回答by Saicharan S M
You need to swap the data not just the nodes.
您需要交换数据而不仅仅是节点。
public void sort() {
if (size > 1) {
for (int i = 0; i < size; i++ ) {
Node currentNode = head;
Node next = head.nextNode;
for (int j = 0; j < size - 1; j++) {
if (currentNode.data > next.data) {
int temp = currentNode.data;
currentNode.data = next.data;
next.data = temp;
}
currentNode = next;
next = next.nextNode;
}
}
}
}
回答by VICTOR
you can write this methode like this:
你可以这样写这个方法：
class Node {
int data = 0;
Node next;
public Node(int data) {
this.data = data;
}
}
public void sort() {
Node current = head;
while (current != null) {
Node second = current.next;
while (second != null) {
if (current.data > second.data) {
int tmp = current.data;
current.data = second.data;
second.data = tmp;
}
second = second.next;
}
current = current.next;
}
}
