为什么使用冒泡排序来排序链接列表时，此代码无法正常工作？

-3

我使用LinkedList实现了气泡排序，如下所示。我无法为这个问题找到正确和有效的解决方案。在这个代码中需要做出什么样的改变，才能提高工作效率。如果有人在链接列表上有更好更高效的气泡排序实现，请提供它。为什么使用冒泡排序来排序链接列表时，此代码无法正常工作？

class SortList { 
    int size; 
    Node head; 
    class Node{ 
    int data; 

    Node next; 
    Node(int data){ 
     this.data = data; 
     this.next = null; 
     } 
    Node(){ 
     this.data = 0; 
     this.next = null; 
    } 
    } 

    public void push(int d) { 
     Node newNode = new Node(); 

     newNode.data = d; 

     newNode.next = head; 

     head = newNode; 
     size++; 
    } 
    public void display(){ 
    Node n = head; 
    while(n!=null){ 
     System.out.print(n.data +" "); 

     n = n.next; 
     } 
    } 
    public int getLength(){ 
     int count=0; 
     Node n = head; 
     while(n!=null){ 
      count++; 
      n = n.next; 
      } 
      return count; 
    } 
    public int getLengthR(Node n){ 

      if(n==null) return 0; 
      return 1+getLengthR(n.next); 

    } 
    public int getL(){ 
    return getLengthR(head); 
    } 
    public static void main(String[] args) { 
     SortList ls = new SortList(); 
    int[]arrList = {5,2,7,3,1,2}; 
    for(int i=0;i<arrList.length;i++){ 
     ls.push(arrList[i]); 
     } 
     ls.display(); 

     ls.sortList(); 

     ls.display(); 
    } 

    public void sortList(){ 
    if(size > 1){ 
     Node node = head; 
     Node nextNode = head.next; 
      for(int i=0;i<size;i++){ 

      for(int j=0;j<size - i - 1;j++){ 
       while(node.data > nextNode.data){ 
        Node temp =node; 
        node = nextNode; 
        nextNode = temp; 
       } 
       node = nextNode; 
       nextNode = nextNode.next; 
      } 
     } 

     } 
    } 
}

来源

2017-02-20 Nitish Sati

_“我没有得到排序列表”_ - 这不是一个足够的问题描述。你是否已经在IDE调试器中查看了代码？你能确定哪里出了问题？显示一些示例输入，预期输出和实际输出。 –

您可以使用简单的[google搜索]（https://www.google.co.in/?q=sort+linked+list+in+java#safe=active&q=sort+linked+list+in+ JAVA）。 –

检查此： http://stackoverflow.com/questions/16033800/bubble-sort-implementation-on-linked-lists – blu3

-2

您应该看看评论中建议的StackOverFlow答案。我使用稍微不同的策略修改了排序方法。我交换了节点中的值，而不是交换节点。这可能并不总是适用的，因为可能有其他数据与您没有用于排序目的的节点相关联，这些数据可能也需要交换。

基本上下面的方法是每次通过后减少一个列表的大小。这是通过使用变量terminal跟踪刚放入其正确位置的节点完成的。

public void sortList(){ 
    if(size > 1){ 
     Node terminal = null; 
     while (head.next != terminal) { 
      Node node = head; 
      Node nextNode = head.next; 

      while (nextNode != terminal) { 
       if(node.data > nextNode.data){ 
        int temp =node.data; 
        node.data = nextNode.data; 
        nextNode.data = temp; 
       } 
       node = nextNode; 
       nextNode = nextNode.next; 
      } 
      terminal = node; 
     } 
    } 
}

来源

2017-02-20 06:24:29

为什么使用冒泡排序来排序链接列表时，此代码无法正常工作？

回答

相关问题