使用冒泡排序对对象的LinkedList进行排序

Question

我有一个LinkedList，里面装满了存储在节点中的Book对象，其中包含出版年份和书名。我正在尝试对列表进行排序，使其从最古老的年份排列到最近的年份，然而，在第一本书之后，我的其他书籍现在都有相同的标题和出版年份。我相信这与我使用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;
}
}
}
}

你仍然可以做的事情

如果你能让你的Node类具有可比性，它会变得更好。这样一来，if语句可以变得更通用，并且与书籍相关的实现联系更少。