冒泡手动排序Java中的链接列表

这是我的第一个问题。 我试图手动排序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  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 

Answer 1

正如预期的那样，问题出在方法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; } } } } 

一个小问题就是总是执行冒泡排序n * n次。 实际上，最好检查列表中的任何一对之间是否有变化。 如果是，则需要在整个列表中再次运行; 如果没有，就没有。 考虑边缘情况，其中在调用sort()时已经对100个元素的列表进行了排序。 这意味着列表中的节点将运行10000次，即使实际上没有任何事情要做！

但是，主要问题是您正在交换指向列表中节点的指针。

 if (currentNode.data > next.data) { Node temp = currentNode; currentNode = next; next = temp; } 

如果你用v[i]翻译currentNode ， 然后用v[i - 1] ，就好像你正在排序一个数组那样。 但是，您只是更改用于在列表上运行的指针，而不会在列表本身中生效。 最好的解决方案（如果您将使用BubbleSort ，这始终是最糟糕的解决方案）将是在节点内交换数据。

 if (currentNode.data > next.data) { int temp = currentNode.data; currentNode.data = next.data; next.data = temp; } 

但是，为了说明这个概念，我打算建议改变节点之间的链接。 这些指针实际标记列表中的排序。 我在谈论Node类中的nextNode属性。

足够的聊天，这里是：

 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 。

 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中找到代码，url为： http ：//ideone.com/HW5zw7

希望这可以帮助。

Answer 2

您需要交换数据而不仅仅是节点。

  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; } } } }