[数据结构与算法]关于Java中数组或集合排序的方法

刷算法的过程中，或者平常工作中，免不了对集合或者数组排序，如果自己去写快排或者归并排序，既费时费力，又没有直接采用Java方便优雅。网上关于排序的文章很多，但我觉得出现了太多无关紧要的东西，我只关心怎么用，长时间不用回来的时候，又要看半天才能找到，随记录一个关于集合数组排序的文章。

数组集合排序方法

直接采用Java API

• 对于数组（int[] short[] T[]）Arrays.sort()

Arrays.sort();
// 使用方法
int[] arr = new int[]{1, 3, 7, 9, 3, 0, 2, -1};
Arrays.sort(arr);
// 排序前
[1, 3, 7, 9, 3, 0, 2, -1]
// 排序后
[-1, 0, 1, 2, 3, 3, 7, 9]

升序排序

• 对于集合（实现Collection<E>接口） Collections.sort()

Collections.sort();
// 使用方法
List<Integer> list = new ArrayList<>();
Collections.sort(list);
// 排序前
[1, 3, 2, 7, 9, -1]
// 排序后
[-1, 1, 2, 3, 7, 9]

于是我们得出结论，上述两个办法可以对集合进行排序，但都是升序，自定义排序则需要实现Comparator翻译过来就是比较器

// Arrays.sort()
public static <T> void sort(T[] a, Comparator<? super T> c)

// Collections.sort()
public static <T> void sort(List<T> list, Comparator<? super T> c)

自定义排序规则

此种方法支持对象，不支持基本类型

1. 直接使用 Collections.reverseOrder()

Integer[] arr = {1, 3, 7, 9, 3, 0, 2, -1};
Arrays.sort(arr, Collections.reverseOrder());
// 排序前
[1, 3, 7, 9, 3, 0, 2, -1]
// 排序后
[9, 7, 3, 3, 2, 1, 0, -1]

List<Integer> list = new ArrayList<>();
Collections.sort(list, Collections.reverseOrder());
// 排序前
[1, 3, 2, 7, 9, -1]
// 排序后
[9, 7, 3, 2, 1, -1]

此种方法比较简单，但是很局限，比如对int[][]之类的就无法排序

2. 实现Comparator<T>重写compare方法

基本适用所有对象排序

compare(a, b)方法上有这样一句话Compares its two arguments for order. Returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.,意思是第一个参数大就返回正数， 第一个参数小就返回负数，相等时0。所有如果我们想要逆序那就反其道而行之。

a > b 时返回 负数，a < b时返回正数。

Collections.sort(list, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                if  (a > b) {
                    return -1;
                }
                if (a < b) {
                    return 1;
                }
                return 0;
            }
        });
// 排序前
[1, 3, 2, 7, 9, -1]
// 排序后
[9, 7, 3, 2, 1, -1]        

我们来排序下二位数组，按照a[][0] 降序，a[][1] 升序，算法中也经常需要这么处理

int[][] arr = {{1, 9}, {3, 1}, {5, 3}, {7, 0}, {7, 1}, {3, 0}, {3, 4}};
Arrays.sort(arr, new Comparator<int[]>() {
    @Override
    public int compare(int[] a, int[] b) {
        if (a[0] > b[0]) {
            return -1;
        }

        if (a[0] < b[0]) {
            return 1;
        }

        if (a[0] == b[0]) {
            if (a[1] > b[1]) {
                return 1;
            } else {
                return -1;
            }
        }
        return 0;
    }
});

// 排序前
[1, 9]
[3, 1]
[5, 3]
[7, 0]
[7, 1]
[3, 0]
[3, 4]
// 排序后
[7, 0]
[7, 1]
[5, 3]
[3, 0]
[3, 1]
[3, 4]
[1, 9]

简单的总结下，对于compare(a, b) 如果a 比 b 大返回正数，就是升序， 返回负数就是降序。
既然理解了原理，就来简化上面的compare这样写实在太笨了，哈哈

    Arrays.sort(arr, new Comparator<int[]>() {
        @Override
        public int compare(int[] a, int[] b) {
            if (a[0] == b[0])
                return a[1] - b[1];
            return b[0] - a[0];
        }
    });

是不是优美了许多，测试下来也是一样的结果。只要记住原则，那么其他的就了然于心了~