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是不稳定算法。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 前言 本篇文章基本是从常用排序算法总结(一)快速排序引申而来,其中大部分代码和描述都来自这两篇文章。 时间复杂度 ...
    王三的猫阿德阅读 1,122评论 0 1
  • 本文首发于我的个人博客:尾尾部落 排序算法是最经典的算法知识。因为其实现代码短,应该广,在面试中经常会问到排序算法...
    繁著阅读 4,585评论 3 119
  • 1 初级排序算法 排序算法关注的主要是重新排列数组元素,其中每个元素都有一个主键。排序算法是将所有元素主键按某种方...
    深度沉迷学习阅读 1,431评论 0 1
  • java笔记第一天 == 和 equals ==比较的比较的是两个变量的值是否相等,对于引用型变量表示的是两个变量...
    jmychou阅读 1,516评论 0 3
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好...
    依依玖玥阅读 1,271评论 0 2