使用带有排序的比较器

Question

我正在尝试创建一个小程序来获取输入 1-3 并根据用户的选择使用不同的排序算法对联系人列表进行排序。我已经编写了所有代码，但是当我尝试使用我的排序时遇到问题。如果我使用集合排序，程序运行良好，但我需要使用这三种算法。

public class  {

public static void main(String[] args) {

    Contact[] contacts = {

    };


    int input;
    do{
    Scanner in = new Scanner(System.in);
    System.out.println("Sort by last name:     [0]");
    System.out.println("Sort by first name:    [1]");
    System.out.println("Sort by age:           [2]");
    System.out.println("Enter an option or 0 to end input: ");
    input = in.nextInt();

        if(input == 0)
        {
            System.out.println("Exiting...");
            System.exit(input);
        }

        else if(input == 1)
        {
            Merge.sort(contacts, new LastNameComparator());

            for(Contact contact : contacts)
            {
                System.out.println(contact);
            }
        }

        else if(input == 2)
        {
            Quick.sort(contacts, new FirstNameComparator());

            for(Contact contact : contacts)
            {   
                System.out.println(contact);
            }
        }

        else if(input == 3)
        {
            Heap.sort(contacts, new AgeComparator());

            for(Contact contact : contacts)
            {
                System.out.println(contact);
            }
        }

        else if(input > 3 || input < 0)
        {
            System.out.println("Invalid entry");
        }

    } while (input != 0);
}

}

    public class Contact implements Comparable{
    import java.util.Comparator;

    String lastName;
    String firstName;
    String homeState;
    Integer age;

    Contact(String lastName, String firstName, String homeState, Integer age)
    {
        this.lastName = lastName;
        this.firstName = firstName;
        this.homeState = homeState;
        this.age = 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 String getHomeState() {
        return homeState;
    }

    public void setHomeState(String homeState) {
        this.homeState = homeState;
    }

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return String.format("%8s %8s %7s, %7d", this.lastName, this.firstName, this.homeState, this.age);
    }

    class FirstNameComparator implements Comparator<Contact> {
        public int compare(Contact a, Contact b) {
            return a.firstName.compareToIgnoreCase(b.firstName);
            }

    class LastNameComparator implements Comparator<Contact>{
         public int compare(Contact a, Contact b) {
            return a.lastName.compareToIgnoreCase(b.lastName);
            }

    class AgeComparator implements Comparator<Contact> {
         public int compare(Contact a, Contact b) {
            return a.age < b.age ? -1 : a.age == b.age ? 0 : 1;
            }

        }
    }
}

}

非常感谢任何提示。谢谢！

Answer 1

@Mark，这是我所做的更改。

使用Comparator和Comparable有些歧义，你可以阅读这个post看看区别：What is the difference between compare() and compareTo()?
你的索引是错误的，比如 0 到 'Sort by last name' 和 'exit'
导入始终在 class 语句之前
缺少一些括号

4.5 Heap 中有一个主要方法和 Assignment1 中的其他选项，我只是为了编译而删除了

我建议你使用泛型来实现这个 class，你可以在这里阅读更多内容：https://docs.oracle.com/javase/tutorial/java/generics/。在您的 Head.sort 方法中，您将其定义为接收一个 Comparable，并且您正在传递一个 Comparable 和一个 Comparator，就像我说的，它是不明确的。最好传递一个通用数组（如任何东西-> String[]、int[]、yourOwnClass[]）并提供第二个参数：比较器！所以，让我们回去，改为使用泛型并提供您的比较器！现在你正在调用方法 sort 并告诉它要比较的参数是什么 (Comparator)。你可以在这里看到最终结果：

进口java.util.Scanner； public class 作业 1 {

public static void main(String[] args) {

Contact[] contacts = {
        new Contact("Collins", "Kelly", "Illinois", 26),
        new Contact("Smith", "Brandon", "Michigan", 32),
        new Contact("Jones", "Mark", "California", 29),
        new Contact("McDowell", "Ryan", "Texas", 30),
        new Contact("Thompson", "April", "New York", 35)
};


int input;
do {
    Scanner in = new Scanner(System.in);
    System.out.println("Sort by last name:     [1]");
    System.out.println("Sort by first name:    [2]");
    System.out.println("Sort by age:           [3]");
    System.out.println("Enter an option or 0 to end input: ");
    input = in.nextInt();

    if (input == 0) {
        System.out.println("Exiting...");
        System.exit(input);
    } else if (input == 3) {
        Heap.sort(contacts, new Contact.AgeComparator());


        for (Contact contact : contacts) {
            System.out.println(contact);
        }
    } else if (input > 3 || input < 0) {
        System.out.println("Invalid entry");
    }

} while (input != 0);

} }

联系人class：

import java.util.Comparator;

public class 联系{

String lastName;
String firstName;
String homeState;
Integer age;

Contact(String lastName, String firstName, String homeState, Integer age) {
    this.lastName = lastName;
    this.firstName = firstName;
    this.homeState = homeState;
    this.age = 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 String getHomeState() {
    return homeState;
}

public void setHomeState(String homeState) {
    this.homeState = homeState;
}

public Integer getAge() {
    return age;
}

public void setAge(Integer age) {
    this.age = age;
}

@Override
public String toString() {
    return String.format("%8s %8s %7s, %7d", this.lastName, this.firstName, this.homeState, this.age);
}

static class FirstNameComparator implements Comparator<Contact> {
    public int compare(Contact a, Contact b) {
        return a.firstName.compareToIgnoreCase(b.firstName);
    }
}

static class LastNameComparator implements Comparator<Contact> {
    public int compare(Contact a, Contact b) {
        return a.lastName.compareToIgnoreCase(b.lastName);
    }
}

static  class AgeComparator implements Comparator<Contact> {
    public int compare(Contact a, Contact b) {
        return a.age < b.age ? -1 : a.age == b.age ? 0 : 1;
    }

}
}

堆class

import java.util.Comparator;

public class堆{

// This class should not be instantiated.
private Heap() { }

/**
 * Rearranges the array in ascending order, using the natural order.
 * @param pq the array to be sorted
 */
public static <T> void sort(T[] pq, Comparator<T> comparator) {
    int n = pq.length;
    for (int k = n/2; k >= 1; k--)
        sink(pq, k, n, comparator);
    while (n > 1) {
        exch(pq, 1, n--);
        sink(pq, 1, n, comparator);
    }
}

private static <T> void sink(T[] pq, int k, int n, Comparator<T> comparator) {
    while (2*k <= n) {
        int j = 2*k;
        if (j < n && less(pq, j, j+1, comparator)) j++;
        if (!less(pq, k, j, comparator)) break;
        exch(pq, k, j);
        k = j;
    }
}


private static <T> boolean less(T[] pq, int i, int j, Comparator<T> comparator) {
    return comparator.compare(pq[i-1],pq[j-1]) < 0;
}

private static void exch(Object[] pq, int i, int j) {
    Object swap = pq[i-1];
    pq[i-1] = pq[j-1];
    pq[j-1] = swap;
}

}

合并

    import java.util.Comparator;

public class Merge {

    // This class should not be instantiated.
    private Merge() {
    }

    // stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
    private static <T> void merge(T[] a, T[] aux, int lo, int mid, int hi, Comparator<T> comparator) {
        // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
        assert isSorted(a, lo, mid, comparator);
        assert isSorted(a, mid + 1, hi, comparator);

        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        // merge back to a[]
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (less(aux[j], aux[i], comparator)) a[k] = aux[j++];
            else a[k] = aux[i++];
        }

        // postcondition: a[lo .. hi] is sorted
        assert isSorted(a, lo, hi, comparator);
    }

    // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
    private static <T> void sort(T[] a, T[] aux, int lo, int hi, Comparator<T> comparator) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid, comparator);
        sort(a, aux, mid + 1, hi, comparator);
        merge(a, aux, lo, mid, hi, comparator);
    }

    /**
     * Rearranges the array in ascending order, using the natural order.
     *
     * @param a the array to be sorted
     */
    public static <T> void sort(T[] a, Comparator<T> comparator) {
        T[] aux = (T[])new Object[a.length];
        sort(a, aux, 0, a.length - 1, comparator);
        assert isSorted(a, comparator);
    }

    // is v < w ?
    private static <T> boolean less(T v, T w, Comparator<T> comparator) {
        return comparator.compare(v,w) < 0;
    }


    private static <T> boolean isSorted(T[] a, Comparator<T> comparator) {
        return isSorted(a, 0, a.length - 1, comparator);
    }

    private static <T> boolean isSorted(T[] a, int lo, int hi, Comparator<T> comparator) {
        for (int i = lo + 1; i <= hi; i++)
            if (less(a[i], a[i - 1], comparator)) return false;
        return true;
    }
}

快速

    import java.util.Comparator;

public class Quick {
    // This class should not be instantiated.
    private Quick() {
    }

    /**
     * Rearranges the array in ascending order, using the natural order.
     *
     * @param a the array to be sorted
     */
    public static <T> void sort(T[] a, Comparator<T> comparator) {
        sort(a, 0, a.length - 1, comparator);
        assert isSorted(a, comparator);
    }

    // quicksort the subarray from a[lo] to a[hi]
    private static <T> void sort(T[] a, int lo, int hi, Comparator<T> comparator) {
        if (hi <= lo) return;
        int j = partition(a, lo, hi, comparator);
        sort(a, lo, j - 1, comparator);
        sort(a, j + 1, hi, comparator);
        assert isSorted(a, lo, hi, comparator);
    }

    // partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
// and return the index j.
    private static <T> int partition(T[] a, int lo, int hi, Comparator<T> comparator) {
        int i = lo;
        int j = hi + 1;
        T v = a[lo];
        while (true) {

            // find item on lo to swap
            while (less(a[++i], v, comparator))
                if (i == hi) break;

            // find item on hi to swap
            while (less(v, a[--j], comparator))
                if (j == lo) break;      // redundant since a[lo] acts as sentinel

            // check if pointers cross
            if (i >= j) break;

            exch(a, i, j);
        }

        // put partitioning item v at a[j]
        exch(a, lo, j);

        // now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
        return j;
    }

    /**
     * Rearranges the array so that {@code a[k]} contains the kth smallest key;
     * {@code a[0]} through {@code a[k-1]} are less than (or equal to) {@code a[k]}; and
     * {@code a[k+1]} through {@code a[n-1]} are greater than (or equal to) {@code a[k]}.
     *
     * @param a the array
     * @param k the rank of the key
     * @return the key of rank {@code k}
     */
    public static <T> T select(T[] a, int k, Comparator<T> comparator) {
        if (k < 0 || k >= a.length) {
            throw new IndexOutOfBoundsException("Selected element out of bounds");
        }
        int lo = 0, hi = a.length - 1;
        while (hi > lo) {
            int i = partition(a, lo, hi, comparator);
            if (i > k) hi = i - 1;
            else if (i < k) lo = i + 1;
            else return a[i];
        }
        return a[lo];
    }


    // is v < w ?
    private static <T> boolean less(T v, T w, Comparator<T> comparator) {
        return comparator.compare(v, w) < 0;
    }

    // exchange a[i] and a[j]
    private static  void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }


    private static <T>  boolean isSorted(T[] a, Comparator<T> comparator) {
        return isSorted(a, 0, a.length - 1, comparator);
    }

    private static <T> boolean isSorted(T[] a, int lo, int hi, Comparator<T> comparator) {
        for (int i = lo + 1; i <= hi; i++)
            if (less(a[i], a[i - 1], comparator)) return false;
        return true;
    }
}

Answer 2

看到你在

中传递了两个参数

 Heap.sort(contacts, new AgeComparator());

现在如果你看到堆的排序方法class

public static void sort(Comparable[] pq) {
int n = pq.length;
for (int k = n/2; k >= 1; k--)
    sink(pq, k, n);
while (n > 1) {
    exch(pq, 1, n--);
    sink(pq, 1, n);
}

它只接受一个参数，所以你需要为两个参数修改它。如果您需要，请参考：http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/Collections.java#Collections.sort%28java.util.List%2Cjava.util.Comparator%29

使用带有排序的比较器

Using a Comparator with sorts

sorting

comparator