双链表上的冒泡排序

Question

public Node get(int i) {  
    if (!isEmpty()) {  
        int j = 0;  
        Node element = head;  
        while (j++ < i) {  
            element = element.getNext();  
            if (element == null)  
                return null;  
        }  
        return element;  
    }  
    return null;  
}  



private void bubbleSort() {  
    for (int i = 0; i < size - 1; i++) {  
        boolean changed = false;  
        for (int j = 0; j < size - i - 1; j++) {  
            if (get(j + 1) != null) {  
                if (get(j).getValue() > get(j + 1).getValue()) {  
                    //System.out.println("Swapping: " + get(j).getValue() + " : " + get(j + 1).getValue());  
                    swap(get(j), get(j + 1));  
                    changed = true;  
                }  
            }  
        }  
        if (!changed)  
            return;  
    }  
}  

public void swap(Node first, Node mid) {  
    if (first == head)  
        head = mid;  
    if (mid == tail) {  
        tail = first;  
    }  
    first.setNext(mid.getNext());  
    mid.setPrev(first.getPrev());  
    first.setPrev(mid);  
    mid.setNext(first);  
}

我不知道缺少什么...

列表，值：
6
2
4
5
7

排序后：
2
6
7

辅助输出：
交换：6<> 2
交换：6<> 4
交换：6<> 5

请帮助我，我不知道对双链表进行排序......

public void swap(Node first, Node mid) {  
    if (first == head)  
        head = mid;  
    if (mid == tail) {  
        tail = first;  
    }  
    first.setNext(mid.getNext());  
    mid.setPrev(first.getPrev());  
    first.setPrev(mid);  
    mid.setNext(first);  
}

请参阅以下代码：交换函数。

Answer 1

由于这似乎是一个家庭作业问题，我不会给你完整的答案。我相当肯定问题出在你的交换函数上。考虑在纸上绘制节点并检查交换函数，看看哪些节点指向哪里会发生什么。考虑您要交换的节点的上一个和下一个节点，并且您还必须更新它们的上一个/下一个！当然，除非您的 setNext 和 setPrev 函数已经这样做了。

如果您需要其他帮助，请随时发表评论。

编辑 1：

此外，作为旁注，不要使用索引（i 和 j）来跟踪您正在使用的节点，而是考虑仅使用节点本身。然后，当您调用 i++ 或 j++ 时，请改为调用 node = node.getNext() 。这样，您就不会在运行时中添加额外的 n 因子，并且可以完全消除交换函数。

编辑2：

我所说的将其绘制在纸上的意思是将每个值按顺序水平地写在纸上。然后在每个圆圈周围画一个圆圈，并在每种情况下画一个指向下一个圆圈和上一个圆圈的箭头。用铅笔画出箭头！然后在逐步执行交换函数时相应地更新箭头。您甚至不必移动/擦除圆圈，只需擦除箭头并查看它们接下来指向的位置即可。

编辑 3：

好的，您有两个要交换的圆圈。这些圆圈都有向外的箭头，它们的邻居都有向内的箭头。每圈有 4 个箭头（2 个进，2 个出，除非你处理的是头/尾）。由于您要移动 2 个圆圈，这意味着您必须总共更改 8 个箭头（除非处理头/尾） - 每圈 4 个。您可能只更改每个 setPrev/setNext 的一个箭头。这意味着这些通常应该在交换函数中调用 8 次。您只给他们打了 4 次电话。

编辑 4：

您正在更新交换节点的上一个/下一个，但不更新其邻居的上一个/下一个。您将需要执行诸如first.getNext().setPrev(second)等操作来更新邻居的引用/上一个/下一个/箭头。

编辑 5：

请记住 null 检查（您不能在 null 上调用 setPrev 或 setNext，因此请确保当您设置邻居的 prev/next 时邻居实际上存在（因为 head 的 prev 不存在，而 next 不存在）尾巴不存在））。

编辑6：

我猜如果你说你没有做作业......；）

void swap(Node first, Node second) {
    Node firstPrev = first.getPrev();
    Node firstNext = first.getNext();
    Node secondPrev = second.getPrev();
    Node secondNext = second.getNext();

    if (firstPrev) {
        firstPrev.setNext(second);
    }
    if (firstNext) {
        firstNext.setPrev(second);
    }
    if (secondPrev) {
        secondPrev.setNext(first);
    }
    if (secondNext) {
        secondNext.setPrev(first);
    }

    second.setPrev(firstPrev);
    second.setNext(firstNext);
    first.setPrev(secondPrev);
    first.setNext(secondNext);
}