插入排序 - 交換節點

Question

我寫了下面的例程，在Java中插入排序雙向鏈接列表交換數據從節點排序&它工作正常。但是，我試圖找出如何實際交換節點鏈接來實現插入排序。我嘗試了很多選項，但都失敗了，因爲自從它引用了節點引用的對象引用之後，將它們改變了起來&打破了列表。任何指針將不勝感激。

Node類（內部類）：

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，如果一個節點是頭部，則更新頭部。

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。如果它是最新的，請將當前設置爲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

分配節點引用而不僅僅是數據。確保將節點的「下一個」和「前一個」更新到兩個交換節點的左側和右側，以及交換節點本身。最後，確保在交換之後，您的迭代繼續使用正確的節點。