使用冒泡排序对 objects 的链表进行排序

Question

我有一个包含书籍 objects 的链表，它存储在节点中，其中包含出版年份和书名。我正在尝试对列表进行排序，以便从最早的年份到最近的年份排列，但是，在第一本书之后，我的其余书籍现在具有相同的标题和出版年份。我相信这与我使用 setBook 方法进行交换时有关。

public void sortByYear(){
    Node current = head;
    Node next = null;

    if(isEmpty()){ //if the head is null
        return;
    }

    while(current != null){
        next = current.getNext();

        while(next != null){
            if(current.getBook().getYear() > next.getBook().getYear()){
                Book temp = current.getBook();
                current.setBook(next.getBook().getYear(), next.getBook().getTitle());
                next.setBook(temp.getYear(), temp.getTitle());
                // current.getBook() = next;
                // next.getBook() = temp;
            }

            next = next.getNext();
        }

        current = current.getNext();
    }

}

Answer 1

几个问题：

您的 setBook 方法——采用年份和标题——似乎改变了分配给节点的书。这不是真正正确的方法。您应该定义一个方法，使书籍保持不变，但将另一本书（全部）分配给一个节点。
冒泡排序总是从列表中的第一项开始内循环。外循环仅用于计算内循环必须启动的次数。这不是您实现它的方式。如果最小节点不在第一位或第二位，你的算法将永远不会将它一直移动回第一位。

我建议采取不同的方法，仅改变列表中的next引用，这样你就可以作为一个整体交换节点，而不必触及数据。为此，您需要一个 prev 引用在当前节点“后面”移动，以便您可以将前面的节点重新连接到与当前节点交换的节点。

这是一个实现：

    public void sortByYear(){
        if (head == null || head.getNext() == null) {
            return;
        }

        for (Node iter = head; iter != null; iter = iter.getNext()) {
            Node prev = null;
            Node current = head;
            for (Node next = current.getNext(); next != null; next = current.getNext()) {
                if (current.getBook().getYear() > next.getBook().getYear()) {
                    if (prev == null) {
                        head = next;
                    } else {
                        prev.setNext(next);
                    }
                    current.setNext(next.getNext());
                    next.setNext(current);
                    prev = next;
                } else {
                    prev = current;
                    current = next;
                }
            }
        }
    }

您仍然可以继续努力的事情

如果你能Nodeclasscomparable就更好了。这样 if 语句可以变得更通用并且与您的 book-related 实现的联系更少。

使用冒泡排序对 objects 的链表进行排序

Sorting a LinkedList of objects using bubble sort

java

linked-list

bubble-sort

您仍然可以继续努力的事情