插入排序 - 交换节点 [英] Insertion sort - swapping nodes

问题描述

我写了下面的程序在Java中插入排序的双向链表而从交换节点中的数据进行排序和放大器;它工作正常。不过，我想弄清楚如何实际交换节点链路，实现了插入排序。我试过无数的选择，但因为它的哪些节点引用的对象引用的所有都因为失败，改变它们弄乱向上和断列表。任何指针将AP preciated。

I wrote following routine for the insertion sort in java for a doubly linked list which swap the data from the nodes to sort & it works fine. However, I am trying to figure out how to actually swap the node links to achieve the insertion sort. I tried numerous options but all are failed because since its the object reference which nodes are referencing to, changing them messes up & breaks the list. Any pointers would be appreciated.

Node类（内部类）：

Node class (inner class):

   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 ）。所以，你应该传递节点交换到其他的方法，而不是试图在同一个地方和放大器;因此它不影响比两个节点这是要交换的其他节点的其余部分。

Thanks for lhuang for providing the method to swap the node. It works. The actual answer lies in the fact that Java copies and passes the reference by value, not object (refer http://www.javaworld.com/javaqa/2000-05/03-qa-0526-pass.html). So you should be passing the node swapping to other method rather than trying in the same place & hence it does not affect the rest of the nodes other than the two nodes which are to be swapped.

我修改了我的日常以下

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

在具有这种逻辑的最后一个问题是，目前的始终是越来越落后交换和放大器时;相同的两个节点都在这样的逻辑处理两次。有没有一种方法来减轻，即恢复电流在其原来的地方掉后？

One last issue in having this logic is that the current is always getting behind when swapped & same two nodes are processed twice in this logic. Is there a way to mitigate that i.e. to restore current in its original place after swap?

推荐答案

您需要更新previous和下一个节点的节点1和节点2相应。

You need to update the previous and next nodes for node1 and node2 accordingly.

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

1, If one node is head, update head.

2，如果节点1是节点2之前正确的，你不能只是更新节点1。preV =节点2 preV。据介绍，在列表中的循环。

2, If node1 is right before node2, you couldn't just update node1.prev = node2.prev. It will introduce a circular in the list.

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。如果它是最新的，设置为preV。$ P $光伏电流。

For question 2, you can check prev before swap. If it is current, set current to 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;
}

顺便说一句，你也可以尝试减少交换操作。既然你选一个链表，这是很容易删除和插入的元素。因此，只要找出当前的适当位置;从原来的地方删除，并插入它。当然，你需要小心的一些细节。

By the way, you can also try to reduce swap operations. Since you are sorting a linked list and it is very easy to delete and insert an element. So just find out the proper place for current; delete it from original place and insert it there. Of course, you need to be careful of some details.

这篇关于插入排序 - 交换节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！