Bubble用Java手动排序链接列表 [英] Bubble Sort Manually a Linked List in Java
问题描述
这是我的第一个问题。
我试图在Java中手动对整数的链表进行排序，但我无法弄清楚我的代码有什么问题。有什么建议？我没有收到任何错误，但是我的输出仍然没有排序。我尝试了几种不同的方法，但是没有任何效果。如果有人可以帮助我，我将不胜感激。
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.
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
推荐答案
问题出乎意料，出现在方法 sort（）中：
The problem, as expected, comes in method 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较小的问题是始终执行n * n次冒泡排序。实际上，最好检查一下列表中的任何一对之间是否有变化。如果是这样，则有必要在整个列表中再次运行；如果没有，那就没有。想想边际情况，其中调用 sort（）时已经排序了100个元素的列表。这意味着即使实际上无事可做，列表中的节点也将运行10000次！
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!
不过，主要的问题是，您正在交换
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;
}
如果您将 currentNode 转换为 v [i] 和 next 乘 v [i-1] ，就像对数组进行排序一样，那样就可以了。但是，您只是更改了用于在列表上运行的指针，而对列表本身没有影响。最好的解决方案（当然，如果要使用 BubbleSort ，它总是最糟糕的解决方案）将是交换节点内部的数据。
If you translate currentNode by v[i] and next by 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.
if (currentNode.data > next.data) {
int temp = currentNode.data;
currentNode.data = next.data;
next.data = temp;
}
但是，为了说明这个概念，我要建议更改节点之间的链接。这些指针实际上是在列表中标记排序的指针。我说的是 Node 类中的 nextNode 属性。
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 nextNode attribute in the Node class.
足够的聊天，在这里它是：
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 );
}
}
双重代码管理节点的解释交换是，由于您必须更改节点之间的链接，而这仅仅是一个链接列表，因此您必须跟踪第一次的前一个节点（也没有头节点）是 head 。
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.
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;
}
您可以在IdeOne中找到以下代码： http://ideone.com/HW5zw7
You can find the code in IdeOne, here: http://ideone.com/HW5zw7
希望这会有所帮助。
这篇关于Bubble用Java手动排序链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
