冒泡手动排序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

正如预期的那样,问题在于方法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次.实际上,最好检查列表中的任何一对之间是否有变化.如果是,则需要在整个列表中再次运行; 如果没有,就没有.想想边缘情况,其中100个元素的列表在sort()被调用时已经被排序.这意味着列表中的节点将运行10000次,即使实际上没有任何事情要做!

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

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

如果你翻译currentNode通过v[i]和未来的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中找到代码,网址为:http://ideone.com/HW5zw7

希望这可以帮助.