Collections.sort 里相减怎么判断正/逆序？

[jadelike]

今天在做 leetcode 的每日一题（ 1636. 按照频率将数组升序排序） java 题解有这么一部分

class Solution {
    public int[] frequencySort(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        for (int num : nums) {
            cnt.put(num, cnt.getOrDefault(num, 0) + 1);
        }
        List<Integer> list = new ArrayList<Integer>();
        for (int num : nums) {
            list.add(num);
        }
        Collections.sort(list, (a, b) -> {
            int cnt1 = cnt.get(a), cnt2 = cnt.get(b);
            return cnt1 != cnt2 ? cnt1 - cnt2 : b - a;
        });
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            nums[i] = list.get(i);
        }
        return nums;
    }
}

作者：LeetCode-Solution
链接： https://leetcode.cn/problems/sort-array-by-increasing-frequency/solution/an-zhao-pin-lu-jiang-shu-zu-sheng-xu-pai-z2db/
来源：力扣（ LeetCode ）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我自己用

Collections.sort(list, (a, b) -> {
            int cnt1 = cnt.get(a), cnt2 = cnt.get(b);
            return cnt1 != cnt2 ? -1 : 1;
        });

代替，结果错了，请问为什么，我只知道 1 ，-1 判断正序还是逆序，不清楚相减怎么判断逆序还是正序

[Jooooooooo]

sort 里如果相等一定要返回 0.

[hidemyself]

Comparator 要满足自反性，传递性，对称性
1 ） 自反性：x ，y 的比较结果和 y ，x 的比较结果相反。
2 ） 传递性：x>y,y>z,则 x>z 。
3 ） 对称性：x=y,则 x,z 比较结果和 y ，z 比较结果相同。

[AoEiuV020CN]

一直觉得这个很不直观，可以记个典型，
123456 从小到大排列，
sort return a - b 代表从小到大排序，
也就是返回负数的话 a 会排到左边，

返回-1 还是-2 没差的，更小的两个还得再比一次，
另外相等必须 return 0,

[wolfie]

> cnt1 != cnt2

问号脸.jpg

[beimengyeyu]

cnt1 - cnt2 可能返回两种结果 正的负的都可能返回的

[dcsuibian]

其实可以这么记：
a < b 返回负数，因为 a - b < 0
a > b 返回正数，因为 a - b > 0
默认按从小到大排，要聪达到小就反过来减

更好的方案是 Interget.compare(a,b)，避免减法时的移除问题，但算法题不是很需要

[dcsuibian]

聪达到小 --> 从大到小
移除问题 --> 溢出

[jadelike]

@dcsuibian
那就以题目为例子，我要 cnt1 != cnt2 的时候返回的是升序，为什么就一定是 cnt1 - cnt2 ，他怎么知道 cnt1 和 cnt2 的大小的？

[dcsuibian]

@jadelike 1 和-1 并不对应“升序”或“降序”。而且还有个 0 呢。

代码里的 (a,b)->{ ... } 这段其实是你对排序方式的定义

返回值<0 （比如-1 ），指明元素 a 在数组中应该在元素 b 的前面
返回值>0 （比如 1 ），指明元素 b 在数组中应该在元素 a 的前面

返回值 0 ，则这两个元素一样，a 前 b 后或 b 前 a 后都可

[dcsuibian]

@jadelike sort()方法其实永远都是升序排序，也就是小的在前，大的在后

“小”和“大”的概念很模糊，比如对于一个 Student ，怎么定义小？可以按成绩、姓名、学号等等，因此 (a,b) -> { ... }这段也可以说是定义大小关系，如果返回值<0 ，就认为 a 比 b 小，应该排在前面。如果是数字的话 a-b 正好就<0 。

降序的功能其实是不存在的，但你可以把返回值的正负号颠倒。这样就实现了降序的效果。

[darkengine]

这个 sort 的实现就很诡异啊，你用是否相等来返回-1 和 1 ，那么 list = [3,4]和 list = [4,3]得到的排序结果是不一样的。

[qyc027]

结果 > 0 就 swap 。b - a > 0 => b > a ，右边大于左边的时候就交换位置，所以最后左边的都大于右边的。