排序ADT队列

Question

我的任务是创建一个Person类，保存他们的名字和年龄，创建一个Queue类，可以保存对象数组，然后使用quicksort算法按字母顺序和年龄排序。

当我尝试在Driver类中调用Sort.quickSort时，我得到一个编译器错误。我不知道该改什么，希望你能帮助我。

import java.util.EmptyStackException;
public class Queue<T> {
private T[] queue;
private int frontIndex;
private int backIndex;
private static final int DEFAULT_INTIIAL_CAPACITY = 50;
public Queue() {
this(DEFAULT_INTIIAL_CAPACITY);
}
public Queue(int initialCapacity) {
@SuppressWarnings("unchecked")
T[] tempQueue = (T[]) new Object[initialCapacity + 1];
queue = tempQueue;
backIndex = initialCapacity;
frontIndex = 0;
}
public int getLength() {
return queue.length;
}
public T[] getQueue() {
return queue;
}
Boolean isEmpty() {
return frontIndex == ((backIndex + 1) % queue.length);
}
void enqueue(T newEntry) {
ensureCapacity();
backIndex = (backIndex + 1) % queue.length;
queue[backIndex] = newEntry;
}
private void ensureCapacity() {
if (frontIndex == ((backIndex + 2) % queue.length)) {
T[] oldQueue = queue;
int oldSize = oldQueue.length;
@SuppressWarnings("unchecked")
T[] tempQueue = (T[]) new Object[2 * oldSize];
queue = tempQueue;
for (int index = 0; index < oldSize - 1; index++) {
queue[index] = oldQueue[frontIndex];
frontIndex = (frontIndex + 1) % oldSize;
}
frontIndex = 0;
backIndex = oldSize % 2;
}
}
T dequeue() {
T front = null;
if (!isEmpty()) {
front = queue[frontIndex];
queue[frontIndex] = null;
frontIndex = (frontIndex + 1) % queue.length;
}
return front;
}
T getFront() {
if (isEmpty())
throw new EmptyStackException();
else
return queue[frontIndex];

}
public T[] toArray() {
@SuppressWarnings("unchecked")
T[] result = (T[]) new Object[DEFAULT_INTIIAL_CAPACITY];
for (int i = 0; i < queue.length; i++) {
result[i] = queue[i];
}
return result;
}
}

public class Person {
private String lastName, firstName;
private int age;
Person(String firstName, String lastName, int age) {
this.setFirstName(firstName);
this.setLastName(lastName);
this.setAge(age);
}
public String getLastName() {
return lastName;
}
public void setLastName(String lastName) {
this.lastName = lastName;
}
public String getFirstName() {
return firstName;
}
public void setFirstName(String firstName) {
this.firstName = firstName;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String toString() {
return getLastName() + ", " + getFirstName() + " - " + getAge();
}
}

public class Sort {
private static final int MIN_SIZE = 4;

private static <T extends Comparable<? super T>> void sortFirstMiddleLast(T[] a, int first, int mid, int last) {
if (a[first].compareTo(a[mid]) > 0)
swap(a, first, mid);
if (a[mid].compareTo(a[last]) > 0) {
swap(a, mid, last);
if (a[first].compareTo(a[mid]) > 0) {
swap(a, first, mid);
}
}
}
private static void swap(Object[] array, int i, int j) {
Object temp = array[i];
array[i] = array[j];
array[j] = temp;
}
private static <T extends Comparable<? super T>> int partition(T[] a, int first, int last) {
int mid = (first + last) / 2;
sortFirstMiddleLast(a, first, mid, last);
swap(a, mid, last - 1);
int pivotIndex = last - 1;
T pivot = a[pivotIndex];
int indexFromLeft = first + 1;
int indexFromRight = last - 2;
boolean done = false;
while (!done) {
while (a[indexFromLeft].compareTo(pivot) < 0)
indexFromLeft++;
while (a[indexFromRight].compareTo(pivot) > 0)
indexFromRight--;
if (indexFromLeft < indexFromRight) {
swap(a, indexFromLeft, indexFromRight);
indexFromLeft++;
indexFromRight--;
} else
done = true;
}
swap(a, pivotIndex, indexFromLeft);
return pivotIndex;
}
public static <T extends Comparable<? super T>> void quickSort(T[] a, int first, int last) {
if (last - first + 1 < MIN_SIZE)
selectionSort(a);
else {
int pivotIndex = partition(a, first, last);
quickSort(a, first, pivotIndex - 1);
quickSort(a, pivotIndex + 1, last);
}
}
public static <T extends Comparable<? super T>> void selectionSort(T[] a) {
int last = a.length - 1;
for (int index = 0; index < last; index++) {
int indexNextSmallest = getIndexOfSmallest(a, index, last);
swap(a, index, indexNextSmallest);
}
}
public static <T extends Comparable<? super T>> int getIndexOfSmallest(T[] a, int first, int last) {
T min = a[first];
int indexOfMin = first;
for (int index = first + 1; index <= last; index++) {
if (a[index].compareTo(min) < 0) {
min = a[index];
indexOfMin = index;
}
}
return indexOfMin;
}
}

public class driver {
public static <T> void main(String[] args) {
Person one = new Person("Tyler", "Well", 19);
Person two = new Person("Roy", "Ted", 19);
Person three = new Person("Jerry", "Dots", 19);
Person four = new Person("Something", "Test", 19);
Person five = new Person("PlaceHolder", "Matt", 19);
Queue<Person> persons = new Queue<Person>(5);
persons.enqueue(one);
persons.enqueue(two);
persons.enqueue(three);
persons.enqueue(four);
persons.enqueue(five);
Sort.quickSort(persons.getQueue(), 0, persons.getLength()); //error here
}
}

Answer 1

您忘记在Person类中实现Comparable接口了。

你的quickSort方法要求一个限定在Comparable的类型参数T，这是Person没有实现的;因此会出现编译错误。

public static <T extends Comparable<? super T>> void quickSort(T[] a , int first, int last)

假设您想先按姓氏，然后按名字，最后按年龄对Person实例进行排序，您的类Person应该是这样的:

class Person implements Comparable<Person> {

/* ... your implementation ... */
@Override
public int compareTo(Person o) {
return Comparator.comparing(Person::getLastName)
.thenComparing(Person::getFirstName)
.thenComparingInt(Person::getAge)
.compare(this, o);
}
}