在鏈表上使用遞歸進行快速排序

我必須對鏈表進行快速排序......到目前爲止，我一直都沒問題，但是遇到了一個我看不到的小問題弄清楚爲什麼它不能正常工作。在鏈表上使用遞歸進行快速排序

這裏是對象節點：

public class Node 
    { 
     String name; 
     Node next; 
    }

下面是該程序的代碼：

public class QuickSortRecusionLinkedList 
    { 
     public static void quickS(int start, int finish, Node head, Node tail) 
     { 
     int left = start; 
     int right = finish; 
     Node pivot = head; 
     for(int i = 0; i < ((left+right)/2); i++) 
     { 
      pivot = pivot.next; 
     } 
     Node temp = new Node(); 
     Node leftN = head; 
     Node rightN = head; 

     while(right > left) 
     { 
      leftN = head; 
      for(int i = 0; i < left; i++) 
      { 
      leftN = leftN.next; 
      } 
      while ((leftN.name).compareToIgnoreCase((pivot.name))<0) 
      { 
      left = left + 1; 
      leftN = leftN.next; 
      } 
      rightN = head; 
      for(int i = 0; i < right; i++) 
      { 
      rightN = rightN.next; 
      } 
      while ((pivot.name).compareToIgnoreCase((rightN.name))<0) 
      { 
      right = right - 1; 
      rightN = head; 
      for(int i = 0; i < right; i++) 
      { 
       rightN = rightN.next; 
      } 
      } 

      if (left <= right 
      ) 
      { 
      temp.name = leftN.name; 
      leftN.name = rightN.name; 
      rightN.name = temp.name; 

      left = left +1; 
      leftN = leftN.next; 

      right = right -1; 
      rightN = head; 
      for(int i = 0; i < right; i++) 
      { 
       rightN = rightN.next; 
      } 

      int size = 1; 
      temp = head; 
      while (temp!=tail) 
      { 
       temp = temp.next; 
       size++; 
      } 
      temp = head; 
      while(temp != tail) 
      { 
       System.out.print(temp.name + ", "); 
       temp = temp.next; 
      } 
      System.out.println(tail.name + "."); 
      } 
     } 

     if(start < right) 
      quickS(start, right, head, tail); 
     if(left < finish) 
      quickS(left, finish, head, tail); 
     } 

     public static void main(String[] args) 
     { 
     Node head = new Node(); 
     Node tail = new Node(); 
     Node a = new Node(); 
     Node b = new Node(); 
     Node c = new Node(); 

     head.name = "R"; 
     tail.name = "D"; 
     a.name = "Z"; 
     b.name = "C"; 
     c.name = "P"; 

     head.next = a; 
     a.next = b; 
     b.next = c; 
     c.next = tail; 

     int size = 0; 
     Node temp = head; 
     while (temp!= tail) 
     { 
      temp = temp.next; 
      size++; 
     } 

     quickS(0,size,head,tail); 
     } 

    }

這裏是打印輸出：

C, Z, R, P, D. 
C, Z, R, P, D. 
C, D, R, P, Z. 
C, D, P, R, R. 
C, D, P, R, R. 
C, D, P, R, R.

最終的結果應該是C, D, P, R, Z。但由於某種原因該程序正在用Z代替另一個R。代碼有什麼問題？

來源

2011-02-23 S.Pedro

重新格式化代碼或pastebin它。 – asgs 2011-02-23 12:56:04

當您使用調試器時，您會看到什麼？ – 2011-02-23 13:01:09

首先，我不知道如何編輯代碼，以便它是正常的，而不是所有奇怪的，因爲我現在擁有它...這是最好的，我可以管理抱歉。 – 2011-02-23 13:07:44

可能的提示：小心temp變量在您使用它來交換名稱時指向的內容。

來源

2011-02-23 14:10:47 johusman

謝謝johusman！它完美后，我把temp = new Node（）;在交換之前...謝謝 – 2011-02-23 14:18:01

仍然覺得幫助人們做作業有點髒，但它本身並不真正與quicksort算法有關，只是一個愚蠢的疏忽:) – johusman 2011-02-23 14:20:08

你很難爲他做他的功課！你只是指出了一個[小]的邏輯錯誤 – prelic 2011-02-23 20:52:00

尊重這似乎是一個傻瓜的差事。鏈接列表上的Quiksort將是任何東西，但是很快。它的整個想法是使用數組。這裏的目標是什麼？

來源

2011-02-24 01:40:13 EJP

在鏈表上使用遞歸進行快速排序

回答

相關問題