使用鏈接列表快速排序

Question

我需要此代碼的幫助。我需要在main方法中沒有任何參數的情況下調用quicksort方法。但是這個程序有一個參數。如何在主方法中調用它時使其工作並沒有任何參數？

請幫忙。

Employee類

public class Employee 
{ 
    private String firstname; 
    private int idNumber; 
    private String lastname; 


    Employee(String lname,String fname, int id) 
    { 
     lastname = lname; 
     firstname = fname; 
     idNumber = id; 
     } 

public void setLastName(String lname) 
    {lastname = lname;} 
public String getLastName() 
    {return lastname;} 

public void setFirstName(String fname) 
    {firstname = fname;} 
public String getFirstName() 
    {return firstname;} 

public void setidNumber(int id) 
    {idNumber = id;} 
public int getidNumber() 
    {return idNumber;} 



public String toString() 
{ 
    String str = "\nName: " + lastname + " " + firstname 
       + "\nID: " + idNumber; 

    return str; 
} 
public int compareTo(Employee Employee2) 
{ 
    int diff = lastname.compareToIgnoreCase(Employee2.getLastName()); 
    if(diff != 0) 
     return diff; 
    else 
      return -1; 

     } 
    } 

鏈表類，而不是參數

public class DoublyLinkedList 
{ 
public class DoublyLinkedListLink 
{ 
     public Employee info; 
      public DoublyLinkedListLink next; 
     public DoublyLinkedListLink back; 
//Default Constructor 
//Postcondition: info = 0; 
// next = null; back = null; 
public DoublyLinkedListLink() 
{ 
    info = null; 
next = null; 
back = null; 
} 

public DoublyLinkedListLink(Employee item) 
{ 
info = item; 
next = null; 
back = null; 
} 

public void displayInfo() 
{ 
System.out.print(info + " "); 
} 

} 


protected int count; 
protected DoublyLinkedListLink first; 
protected DoublyLinkedListLink last; 

public DoublyLinkedList() 
{ 
     first = null; 
    last = null; 
    count = 0; 
    } 

public void initializeList() 
{ 
     first = null; 
    last = null; 
    count = 0; 
    } 

public boolean isEmpty() 
{ 
return (first == null); 
     } 

public int length() 
{ 
    return count; 
    } 

public void print() 
{ 
DoublyLinkedListLink current = first; 
while (current != null) 
{ 
    current.displayInfo(); 
    current = current.next; 
    }//end while 
}//end print 

public void insert(Employee insertItem) 
{ 
    DoublyLinkedListLink newNode = new DoublyLinkedListLink(insertItem); 
     if (isEmpty()) 
    { 
       first = newNode; 
      last = newNode; 
      count++; 
       } 
     else 
     { 
       last.next = newNode; 
       newNode.back = last; 
     } 
      last = newNode; 
    } 

public DoublyLinkedListLink partition(DoublyLinkedList list, DoublyLinkedListLink first, DoublyLinkedListLink last) 
{ 
    DoublyLinkedListLink smallIndex = first; 
    DoublyLinkedListLink index = smallIndex.next; 
    DoublyLinkedListLink temp = new DoublyLinkedListLink(); 
     Employee pivot = first.info; 

     while (index != last.next) 
     { 
     if((index.info).compareTo(pivot) <= 0) 
     { 
      smallIndex = smallIndex.next; 
      temp.info = index.info; 
      index.info = smallIndex.info; 
      smallIndex.info = temp.info; 
       } 

     index = index.next; 
     } 

     temp.info = first.info; 
     first.info = smallIndex.info; 
     smallIndex.info = temp.info; 
     System.out.print("The list in partition is: "); list.print(); 
     System.out.print("\n"); 
     return smallIndex; 
     } 


private void recQuickSort(DoublyLinkedList list, DoublyLinkedListLink first, DoublyLinkedListLink last) 
{ 
     while(first != last) 
    { 
     DoublyLinkedListLink pivotLocation = partition(list, first, last); 
     recQuickSort(list, first, pivotLocation.back); 
     recQuickSort(list, pivotLocation.next, last); 
      } 
} 

public void quickSort(DoublyLinkedList list) 
{ 
    recQuickSort(list, list.first, list.last); 
    } 

} 

主要方法

class MergeSortDriver 
    { 
    public static void main (String [] args) 
    { 
    Employee e1 = new Employee("Grey","Bob",5239);  
    Employee e2 = new Employee("Smith","Maggie", 9845); 
    Employee e3 = new Employee("Ocasio","John", 8502); 
    Employee e4 = new Employee("Yang", "Christina", 4656); 
    Employee e5 = new Employee("Carpenter","Kimberely", 6798); 
    Employee e6 = new Employee("Aguilar","Charlie", 5986); 

    DoublyLinkedList a = new DoublyLinkedList(); 

    Employee A[] = {e1,e2,e3,e4,e5,e6}; 

    a.insert(e1); 
    a.insert(e2); 
    a.insert(e3); 
    a.insert(e4); 
    a.insert(e5); 
    a.insert(e6); 

    a.print(); 

    a.quickSort(); 

    a.print(); 
     } 
    } 

Answer 1

使用this。相反的：

public void quickSort(DoublyLinkedList list) 
{ 
    recQuickSort(list, list.first, list.last); 
} 

你可以做

public void quickSort() 
{ 
    recQuickSort(this, this.first, this.last); 
} 

這樣，你正在使用你在調用quickSort實例，而不是一個傳入quickSort方法。

---

編輯 - 關於在評論中提到的錯誤：

的NullPointerException沒有任何與您是否使用this，而不是一個參數。相反，我懷疑它與遞歸調用周圍的while循環有關。

while(first != last) 
{ 
    DoublyLinkedListLink pivotLocation = partition(list, first, last); 
    recQuickSort(list, first, pivotLocation.back); 
    recQuickSort(list, pivotLocation.next, last); 
} 

在遞歸解決方案中通常不需要這樣的while循環。你可以（有點）把你的遞歸看作你的循環。因此，您應該使用if s來限制呼叫，而不是循環。它可能看起來像這樣：

DoublyLinkedListLink pivot = partition(list, first, last); 
if(first != pivot && first != pivot.back) { 
    recQuickSort(list, first, pivot.back); 
} 
if(last != pivot && last != pivot.next) { 
    recQuickSort(list, pivot.next, last); 
} 

此外，您應該處理列表爲空時的情況。在這種情況下，partition將拋出NullPointerException，因爲first和last都將爲空。

我認爲解決這兩件事情會使它工作。不過，我還沒有測試過它。

---

此外，請儘量保持代碼格式良好。沒有一致格式的代碼（例如縮進）是一個痛苦的工作和看看。