双链表上的冒泡排序

Question

已经做了几个小时了，试图让bubble排序的实现在双链表上工作。我的代码似乎只运行了一次，但没有完成排序就提前完成了。任何指导都将不胜感激。

public void bubbleSort()
{
    Node cur = head.getNext();
    boolean done = false;
    while (!done)
    {
        done = true;
        while(cur != tail)
        {
            if (cur.getNext().getCount()>cur.getCount())
            {
                swap(cur.getNext(),cur);
                done=false;
            }
            cur = cur.getNext();
        }
    }
} 

我使用的交换方法似乎破坏了节点的放置，直到它成为两个节点之间的循环。

private void swap(Node n1, Node n2)
{
    Node b1, b2, a1, a2;
    System.out.println("Swapping n1: " + n1 + " with n2: " + n2);
    b1 = n2.getPrev();
    if (b1 == n1) // handle adjacent nodes
        b1 = n2;
    a1 = n2.getNext();
    b2 = n1.getPrev();
    if (b2 == n2) // handle adjacent nodes
        b2 = n1;
    a2 = n1.getNext();
    // swap
    n1.setPrev(b1);
    n1.setNext(a1);
    n2.setPrev(b2);
    n2.setNext(a2);
    b1.setNext(n1);
    a1.setPrev(n1);
    b2.setNext(n2);
    a2.setPrev(n2);
}

感谢

Answer 1

我在您的代码中看到的问题：

• 您应该从head开始，而不是从head.getNext()开始
• 您应该在每次while(!done)迭代中重新启动Node cur

有了这些更改，您的代码应该是

public void bubbleSort() {
    boolean done = false;
    while (!done) {
        Node cur = head;
        done = true;
        while(cur != tail) {
            if (cur.getNext().getCount()>cur.getCount()) {
                swap(cur.getNext(),cur);
                done=false;
            }
            cur = cur.getNext();
        }
    }
}

此代码假定swap方法可以正常工作。使用int count作为Node类中的数据进行测试，在列表中分配10000个int值。

---

编辑：根据您的问题编辑，我制作了Node类和swap函数，如下所示：

private static class Node {
    int count;
    Node next;
    //getters and setters...
}
//this function just swaps data, no need to swap the nodes prev and next
//(note that yours is an algorithm design issue)
private void swap(Node node1, Node node2) {
    int aux = node1.getCount();
    node1.setCount(node2.getCount());
    node2.setCount(aux);
}

无需执行您在swap实现中完成的所有样板代码。

Answer 2

在外循环的开头添加cur = head.getNext();对于我的链表实现来说效果很好。因此，问题来自swap方法或列表的实现。

根据bubbleSort方法，swap方法只交换节点的数据，而不交换节点本身的数据。我的意思是，它只是交换count的值。如果不是这样，swap方法就是问题所在。否则，您的双链表实现就会出现问题。

Answer 3

您肯定需要将cur = head.getNext();保留在外部while循环的末尾，否则在第二次传递时，内部while循环将被完全跳过，并且完成将为true。

你有没有考虑过你的冒泡排序的运行时间？我在你对MD.Unincorn的回答中注意到，它对列表很有效<100，但不适用于1000的列表。1000的预期运行时间列表至少比小于100的列表慢100倍。你可能没有给它足够的时间来完成。

对100个列表进行排序需要多长时间？