在 Java 中手动冒泡排序链接列表 [英] Bubble Sort Manually a Linked List in Java

查看:22
本文介绍了在 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;                   
                } 
            }
        }
    }

一个小问题就是总是执行冒泡排序 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;
} 

如果你用 v[i] 翻译 currentNodev[i - 1] 翻译 next,就好像您在对数组进行排序一样,就可以了.但是,您只是更改用于在列表上运行的指针,而不会对列表本身产生影响.最好的解决方案(好吧,前提是您要使用 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.

聊够了,这里是:

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

希望这会有所帮助.

这篇关于在 Java 中手动冒泡排序链接列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆