手动对 Java 中的链表进行冒泡排序

Question

这是我的第一个问题。我正在尝试手动对 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

Answer 1

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

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

Answer 2

不出所料，问题出在方法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;
}

如果您将 currentNode 翻译成 v[i]，将 next 翻译成 v[i - 1]，就好像您在排序一个数组，就可以了。但是，您只是在列表上更改用于运行的指针，而对列表本身没有影响。最好的解决方案（好吧，假设您要使用 BubbleSort，这始终是最差的解决方案）是在节点内交换数据。

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

但是，为了说明这个概念，我将建议更改节点之间的链接。这些指针实际上是在列表中标记排序的指针。我说的是 Node class.

中的 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 );
        }
    }

一个管理节点交换的代码"double"的解释是，因为你必须改变节点之间的链接，而且这只是一个单链表，所以你必须跟踪之前的节点（你也没有头节点），第一次是 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

希望这对您有所帮助。

Answer 3

你可以这样写这个方法：

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

手动对 Java 中的链表进行冒泡排序

Bubble Sort Manually a Linked List in Java

java

linked-list

bubble-sort