0

我在java中为一个双向链表编写了以下插入排序例程，它将节点中的数据交换为排序&它工作正常。但是，我试图弄清楚如何实际交换节点链接以实现插入排序。我尝试了许多选项，但都失败了，因为它是节点所引用的对象引用，因此更改它们会弄乱并破坏列表。任何指针将不胜感激。

节点类（内部类）：

   private class Node {
    T data;
    Node next;
    Node prev;
}

排序例程

   public void sort() {
    if(isEmpty()) {
        throw new RuntimeException("List is empty");
    }
    Node current = head;
    while(current != null) {
        for(Node prev=current; prev.prev != null; prev = prev.prev) {
            if(prev.data.compareTo(prev.prev.data) <= 0) {
                T tmp = prev.data;
                prev.data = prev.prev.data;
                prev.prev.data = tmp;
            }
        }
        current = current.next;
    }
}

编辑1：

感谢 lhuang 提供交换节点的方法。有用。实际答案在于 Java 按值复制和传递引用，而不是对象（请参阅http://www.javaworld.com/javaqa/2000-05/03-qa-0526-pass.html）。因此，您应该将节点交换传递给其他方法，而不是在同一个地方尝试，因此它不会影响除要交换的两个节点之外的其余节点。

我将例程修改为以下

public void sort() {
    if(isEmpty()) {
        throw new RuntimeException("List is empty");
    }
    Node current = top;
    while(current != null) {
        for(Node prev=current; prev != null && prev.prev != null; prev = prev.prev) {
            if(prev.data.compareTo(prev.prev.data) <= 0) {
                swap(prev,prev.prev);
            }
        }
        current = current.next;
    }
}

具有此逻辑的最后一个问题是，在交换时电流总是落后，并且在此逻辑中处理了两次相同的两个节点。有没有办法减轻这种情况，即交换后将电流恢复到原来的位置？

4

2 回答 2

2

您需要相应地更新 node1 和 node2 的前一个和下一个节点。

1，如果一个节点是头，更新头。

2，如果node1在node2之前，你不能只更新node1.prev = node2.prev。它将在列表中引入一个通告。

public void swap(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        throw new IllegalArgumentException(
                "The nodes couldn't be null");
    }

    if (node1 == node2) {
        return;
    }

    // make sure node1 is before node2
    if (node1.getPrev() == node2) {
        Node temp = node2;
        node2 = node1;
        node1 = temp;
    }

    Node node1Prev = node1.getPrev();
    Node node1Next = node1.getNext();
    Node node2Prev = node2.getPrev();
    Node node2Next = node2.getNext();

    node1.setNext(node2Next);
    if (node2Next != null) {
        node2Next.setPrev(node1);
    }

    node2.setPrev(node1Prev);
    if (node1Prev != null) {
        node1Prev.setNext(node2);
    }

    if (node1 == node2Prev) {
        node1.setPrev(node2);
        node2.setNext(node1);
    } else {
        node1.setPrev(node2Prev);
        if (node2Prev != null) {
            node2Prev.setNext(node1);
        }

        node2.setNext(node1Next);
        if (node1Next != null) {
            node1Next.setPrev(node2);
        }
    }

    if (node1 == head) {
        head = node2;
    } else if (node2 == head) {
        head = node1;
    }
}

对于问题 2，您可以在交换之前检查 prev。如果是当前的，则将 current 设置为 prev.prev。

while(current != null) {
    for(Node prev=current; prev != null && prev.prev != null; prev = prev.prev) {
        if(prev.data.compareTo(prev.prev.data) <= 0) {
            if (prev==current) {
                current=prev.prev;
            }
            swap(prev,prev.prev);
        }
    }
    current = current.next;
}

顺便说一句，您也可以尝试减少交换操作。由于您正在对链表进行排序，因此删除和插入元素非常容易。因此，只需找出适合电流的位置即可；从原来的地方删除它并插入那里。当然，你需要注意一些细节。

于 2013-03-11T04:49:29.607 回答
0

分配节点引用而不仅仅是数据。确保更新两个交换节点左右两侧的节点的“下一个”和“上一个”，以及交换的节点本身。最后，确保您的迭代在交换后继续使用正确的节点。

于 2013-03-11T03:47:45.910 回答