Comparator 之于排序

java里面常用的排序接口时Arrays.sort(T[], Comparator)接口，该方法在java7及android上采用的是TimSort, 一个号称比快排更快，时间复杂度介于o(n)到o(nlogn)之间。排序算法一个很重要的方面就是排序稳定性：相等元素在排序之后仍然要保持排序前的顺序。TimSort是一个稳定的算法，但这依赖与Comparator的写法。先看下Comparator的声明:

public interface {
     * @param o1 the first object to be compared.
     * @param o2 the second object to be compared.
     * @return a negative integer, zero, or a positive integer as the
     * first argument is less than, equal to, or greater than the second.
     */
    int compare(T o1, T o2);
}

返回值说的很清楚，当第一个元素小于第二个元素时返回负数，相等时返回0，否则返回整数。
如果按照以上描述实现compare方法，则会按升序排序，如果正好反过来则是降序排序。
有一点很重当就是，如果要保证算法稳定性，则当两个比较数相同时一定要按要求返回0.
以下是两种常用当写法:

Comparator c1 = new Comparator {
  @Override
  public void compare(int o1, int o2) {
    if (o1 == o2) return 0;
    else if (o1 < o2) return -1;
    else return 1;
  }
}

Comparator c2 = new Comparator {
  @Override
  public void compare(int o1, int o2) {
    return o2 - o1;
  }
｝

Comparator c3 = new Comparator {
  @Override
  public void compare(int o1, int o2) {
    return o1 < o2 ? -1 : 1;
  }
}

以上三种Comparator均实现了升序排序，c1，c2是稳定的，c3不是稳定的。

public static void main(String[] args) {
        Model[] arr = new Model[3];
        arr[0] = new Model(2, "c");
        arr[1] = new Model(1, "a");
        arr[2] = new Model(1, "b");
        Arrays.sort(arr,
                new Comparator<Model>() {
                    @Override
                    public int compare(Model o1, Model o2) {
                        if (o1.priority < o2.priority) {
                            return 1;
                        }
                        else {
                            return -1;
                        }
                    }
                });
        for (Model m : arr) {
            System.out.println(m.desc);
        }
    }

static class Model {
        int priority;
        String desc;

        public Model(int priority, String desc) {
            this.priority = priority;
            this.desc = desc;
        }
    }

以上代码输出是[c, b, a], 可以看出c3是不稳定算法。