用Java手動排序鏈表（詞法）

Question

我正在用Java實現我自己的鏈表。節點類只有一個名爲「name」的字符串字段和一個名爲「link」的節點。現在我有一個測試驅動程序類，它只能順序插入幾個名字。現在，我正在嘗試編寫一個排序方法來按字母順序排列節點，但是我遇到了一些麻煩。我從別人的帖子中發現了這個冒泡的僞代碼，並試圖實現它，但是它沒有完全分類條目。我不太清楚爲什麼。任何建議表示讚賞！

private void sort() 
    { 
     //Enter loop only if there are elements in list 
     boolean swapped = (head != null); 

     // Only continue loop if a swap is made 
     while (swapped) 
     { 
      swapped = false; 

      // Maintain pointers 
      Node curr = head; 
      Node next = curr.link; 
      Node prev = null; 

      // Cannot swap last element with its next 
      while (next != null) 
      { 
       // swap if items in wrong order 
       if (curr.name.compareTo(next.name) < 0) 
       { 
        // notify loop to do one more pass 
        swapped = true; 

        // swap elements (swapping head in special case 
        if (curr == head) 
        { 
         head = next; 
         Node temp = next.link; 
         next.link = curr; 
         curr.link = temp; 
         curr = head; 
        } 
        else 
        { 
         prev.link = curr.link; 
         curr.link = next.link; 
         next.link = curr; 
         curr = next; 
        } 
       } 

       // move to next element 
       prev = curr; 
       curr = curr.link; 
       next = curr.link; 
      } 
     } 
    } 

Answer 1

我花了幾分鐘時間查看錯誤代碼，但沒有發現任何錯誤。

我會說，直到有人更聰明或更辛苦的工作出現，你應該嘗試自己調試。如果你有像Eclipse這樣的IDE，你可以單步執行代碼，同時觀察變量的值;如果沒有，您可以在幾個地方插入打印語句，並用您的預期手工檢查您看到的內容。

---

更新我

我複製你的代碼，並進行了測試。除了它按降序排列（這可能不是你想要的），它對於0,1和10個隨機節點的樣本來說是完美的。那麼問題在哪裏？

UPDATE II

還在猜測什麼可以通過以下方式指的是「它沒有完全排序的條目。」您可能期望進行詞典排序（即'B'之前的'a'），並且不會按照計劃混合使用大寫/小寫字詞。這種情況下的解決方案是使用String方法compareToIgnoreCase(String str)。

Answer 2

這可能不是您正在尋找的解決方案，但它很好，很簡單。也許你像我一樣懶惰。

由於您的節點只包含單個數據項，您並不需要重新洗牌您的節點;您可以簡單地交換節點上的值，同時保持列表結構本身不受干擾。

這樣，你可以自由地實現泡泡分類很簡單。

Answer 3

您應該使用該語言提供的排序過程。

try this tutorial.

基本上，你需要你的元類來實現java.lang.Comparable的，其中你只是委託給obj.name.compareTo(other.name)

那麼你可以使用Collections.sort(yourCollection)

或者你可以創建一個知道如何比較對象的java.util.Comparator

Answer 4

要獲得良好性能，您可以使用Merge Sort。 它的時間複雜度是O（n * log（n）），並且可以在沒有列表內存開銷的情況下實現。

泡沫排序不好的排序方法。你可以閱讀What is a bubble sort good for?瞭解詳情。

Answer 5

這可能有點太晚了。我將通過插入所有內容來開始構建列表，因爲對鏈表進行排序並不好玩。

我很積極，你的老師或教授不希望你使用java的本地庫。不過，據說，目前還沒有真正的快速方法來解決這個清單。

您可能按照它們所在的順序讀取所有節點並將它們存儲到數組中。對陣列進行排序，然後重新鏈接節點。我認爲這個大哦的複雜性是O（n^2），所以實際上用鏈表進行冒泡排序就足夠了

Answer 6

我已經完成了單鏈表上的合併排序，下面是代碼。

public class SortLinkedList { 

public static Node sortLinkedList(Node node) { 

    if (node == null || node.next == null) { 
     return node; 
    } 
    Node fast = node; 
    Node mid = node; 
    Node midPrev = node; 
    while (fast != null && fast.next != null) { 
     fast = fast.next.next; 
     midPrev = mid; 
     mid = mid.next; 
    } 
    midPrev.next = null; 
    Node node1 = sortLinkedList(node); 
    Node node2 = sortLinkedList(mid); 
    Node result = mergeTwoSortedLinkedLists(node1, node2); 
    return result; 
} 

public static Node mergeTwoSortedLinkedLists(Node node1, Node node2) { 
    if (null == node1 && node2 != null) { 
     return node2; 
    } else if (null == node2 && node1 != null) { 
     return node1; 
    } else if (null == node1 && null == node2) { 
     return null; 
    } else { 

     Node result = node1.data <= node2.data ? node1 : node2; 
     Node prev1 = null; 
     while (node1 != null && node2 != null) { 
      if (node1.data <= node2.data) { 
       prev1 = node1; 
       node1 = node1.next; 
      } else { 
       Node next2 = node2.next; 
       node2.next = node1; 
       if (prev1 != null) { 
        prev1.next = node2; 
       } 
       node1 = node2; 
       node2 = next2; 
      } 
     } 
     if (node1 == null && node2 != null) { 
      prev1.next = node2; 
     } 
     return result; 
    } 
} 

public static void traverseNode(Node node) { 
    while (node != null) { 
     System.out.print(node + " "); 
     node = node.next; 
    } 
    System.out.println(); 

} 

public static void main(String[] args) { 
    MyLinkedList ll1 = new MyLinkedList(); 

    ll1.insertAtEnd(10); 
    ll1.insertAtEnd(2); 
    ll1.insertAtEnd(20); 
    ll1.insertAtEnd(4); 
    ll1.insertAtEnd(9); 
    ll1.insertAtEnd(7); 
    ll1.insertAtEnd(15); 
    ll1.insertAtEnd(-3); 
    System.out.print("list: "); 
    ll1.traverse(); 
    System.out.println(); 
    traverseNode(sortLinkedList(ll1.start)); 

} 

}

Node類：

public class Node { 
int data; 
Node next; 

public Node() { 
    data = 0; 
    next = null; 
} 

public Node(int data) { 
    this.data = data; 
} 

public int getData() { 
    return this.data; 
} 

public Node getNext() { 
    return this.next; 
} 

public void setData(int data) { 
    this.data = data; 
} 

public void setNext(Node next) { 
    this.next = next; 
} 

@Override 
public String toString() { 
    return "[ " + data + " ]"; 
} 

}

的MyLinkedList類：

public class MyLinkedList { 
Node start; 

public void insertAtEnd(int data) { 
    Node newNode = new Node(data); 
    if (start == null) { 
     start = newNode; 
     return; 
    } 
    Node traverse = start; 
    while (traverse.getNext() != null) { 
     traverse = traverse.getNext(); 
    } 
    traverse.setNext(newNode); 
} 

public void traverse() { 
    if (start == null) 
     System.out.println("List is empty"); 
    else { 
     Node tempNode = start; 
     do { 
      System.out.print(tempNode.getData() + " "); 
      tempNode = tempNode.getNext(); 
     } while (tempNode != null); 
     System.out.println(); 
    } 
} 

}