首页 > 代码库 > 普林斯顿大学算法课 Algorithm Part I Week 3 比较器 Comparators

普林斯顿大学算法课 Algorithm Part I Week 3 比较器 Comparators

比较器接口(Comparator interface):用可选顺序(alternate order)进行排序

public interface Comparator<key>            int compare(Key v, Key w)          //比较元素v和w

 

示例:

Java系统排序(java system sort)

  • 创建Comparator对象(Create Comparator object)
  • 向Array.sort()传递第二参数
String[] a;  ...  Arrays.sort();              //自然顺序(natural order)...  Arrays.sort(a, String.CASE_INSENSITIVE_ORDER);  Arrays.sort(a, Collator.getInstance(new Locale("es"));  Arrays.sort(a, new BritishPhoneBookOrder());                   //这三个顺序参数都是被Comparato<String>对象所定义的

 

使用Comparator接口进行选择排序(Insertion sort)

public static void sort(Object[] a, Comparator comparator){    int N = a.length;    for (int i = 0; i < N;i++)        for(int j =  i; j > 0 && less(comparator, a[j], a[j-1]); j--)            exch(a, j, j-1);        }private static boolean less(Comparator c, Object v, Object w){    return c.compare(v, w) < 0;    }private static void exch(Object[] a, int i, int j){    Object swap = a[i]; a[i] = a[j]; a[j] = swap;    }

实现Comparator接口

  • 定义实现 Comparator 接口的类
  • 实现 compare() 方法
public class Student {      public static final Comparator<Student> BY_NAME = new ByName();      public static final Comparator<Student> BY_SECTION = new BySection();      private final String name;      private final int section;      ...    private static class ByName implements Comparator<Student>                        //ByName类实现了Comparator接口    {        public int compare(Student v, Student w)          {  return v.name.compareTo(w.name);  }      }         private static class BySection implements Comparator<Student>                     //BySection实现了Comparator接口    {          public int compare(Student v, Student w)        {  return v.section - w.section;  }      }  }      

真正的比较在compare的重载方法中。

Comparator接口是一层壳,是把compare()方法包装起来的包装纸。

普林斯顿大学算法课 Algorithm Part I Week 3 比较器 Comparators