插入排序-交换节点

Question

我为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;
    }
}

EDIT1:

感谢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;
    }
}

使用这种逻辑的最后一个问题是，当交换时电流总是落后&相同的两个节点在此逻辑中被处理两次。是否有一种方法可以减轻这种情况，即在交换后恢复其原始位置的电流?

Answer 1

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

1，如果一个节点是head，则更新head

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，您可以在swap之前查看prev。如果是当前，则将当前设置为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;
}

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

Answer 2

分配节点引用而不仅仅是数据。确保将节点的"next"one_answers"prev"更新到交换节点的左侧和右侧，以及交换节点本身。最后，确保在交换后继续使用正确的节点进行迭代。