QuickSort使用链接列表 [英] QuickSort using Linked List
问题描述
我需要帮助这个代码。我需要在main方法中调用quicksort方法，没有任何参数。但是这个程序有一个参数。在主要方法中调用它时，如何使其工作？没有参数？
I need help with this code. I need to call the quicksort method without any parameters in the main method. But this program has a parameter. How can I make it work and not have any parameter when calling it in the main method?
请帮助。
员工类
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();
}
}
推荐答案
使用这个而不是参数。而不是：
Use this instead of the parameter. Instead of:
public void quickSort(DoublyLinkedList list)
{
recQuickSort(list, list.first, list.last);
}
您可以执行
public void quickSort()
{
recQuickSort(this, this.first, this.last);
}
这样你正在使用您正在调用的实例 quickSort ，而不是传入 quickSort 方法。
This way you are using the instance you are invoking quickSort on, instead of one passed into the quickSort method.
编辑 - 关于评论中提到的错误：
EDIT - Regarding the error mentioned in comments:
NullPointerException 与您是否使用而不是参数无关。相反，我怀疑它与你的有关，而环绕递归调用循环。
The NullPointerException does not have anything to do with whether you use this instead of a parameter. Instead I suspect it has something to do with your while loop around the recursive calls.
while(first != last)
{
DoublyLinkedListLink pivotLocation = partition(list, first, last);
recQuickSort(list, first, pivotLocation.back);
recQuickSort(list, pivotLocation.next, last);
}
递归解决方案通常不需要这样的while循环。你可以（有点）认为你的递归是你的循环。所以，而不是一个循环，你应该用限制呼叫，如果 s。它可能看起来像：
Such a while-loop is usually not needed in a recursive solution. You can (kinda) think of your recursion as your loop. So instead of a loop, you should restrict the calls with ifs. It could look something like:
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);
}
此外，您应该处理列表为空的情况。在这种情况下，分区将抛出 NullPointerException ，因为第一而最后一个将为null。
Furthermore, you should handle the case when the list is empty. In this case partition will throw a NullPointerException because both first and last would be null.
我会认为修复这两件事情会使它工作。但是，我还没有测试过。
I would think that fixing these two things would make it work. However, I have not tested it.
此外，尝试保持代码格式很好。没有一致的格式（如缩进）的代码是一个痛苦的工作和看待。
Also, try to keep code nicely formatted. Code without consistent formatting (such as indentation) is a pain to work with and look at.
这篇关于QuickSort使用链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
