使用 java 比较器对字符数组进行排序

Question

按字典顺序对字符数组进行排序，附加条件是所有 c 在所有 b 之前。这可以手动完成，但我想通过使用比较器的内置排序对其进行编码。我写的代码-

static class Sort implements Comparator<Character> {
    @Override
    public int compare(Character x, Character y) {
        if(x == 'c' && y == 'b') {
            return y - x;
        }
        return x - y;
    }
}

public static void main(String[] args) {
    String s = "abracadabra";
    int n = s.length();
    Character[] res = new Character[n];
    for (int i = 0; i < n; i++) {
        res[i] = s.charAt(i);
    }
    Arrays.sort(res, new Sort());
    System.out.println(Arrays.toString(res));
}

给出输出：[a, a, a, a, a, b, c, b, d, r, r]。 c 仅出现在 b 之一之前。如果我将比较器更改为以下内容，那么它会给出正确的输出。

public int compare(Character x, Character y) {
        if(x == 'c' && y == 'b' || x == 'b' && y == 'c') {
            return y - x;
        }
        return x - y;
    }

我的问题是为什么在这两种情况下返回“y-x”都能给出正确答案？如果在一种情况下返回“y-x”是正确的，那么在另一种情况下返回“x-y”不应该是正确的吗？而不是“y-x”，返回 -1 或 +1 也不起作用。 PL。解释内部发生的事情。谢谢！

Answer 1

问题是如果传递'c'和'b'使比较return为负值，那么传递'b'和'c'应该return 是正数（在这种情况下，您的第一个版本 return 是负数）。如果无论参数的顺序如何，函数都不会 return 一致的结果，则排序算法将产生垃圾顺序。

考虑这个版本：

    public int compare(Character x, Character y) {
        if (x == 'c' && y == 'b') {
            return -1;
        } else if (x == 'b' && y == 'c') {
            return 1;
        } else {
            return x.compareTo(y);
        }
    }

Answer 2

您可以添加 System.out.println() 以了解其工作原理：

代码

import java.util.Arrays;
import java.util.Comparator;

public class Main {

    public static void main(String[] args) {
        String s = "abracadabra";
        int n = s.length();
        
        System.out.println("X Y\tX Y\t[if] VALUE");
        System.out.println();
        
        Character[] res = new Character[n];
        for (int i = 0; i < n; i++) {
            res[i] = s.charAt(i);
        }
        
        int min = 'a';
        
        Arrays.sort(res, new Comparator<Character>() {

            @Override
            public int compare(Character x, Character y) {
                System.out.print(y + " " + x + "\t" + (x-min) + " " + (y-min) + "\t");
                if(x == 'c' && y == 'b') {
                    System.out.println("true " + (y - x));
                    return y - x;
                }
                System.out.println("     " + (x - y));
                return x - y;
            }
        });
        System.out.println("#################################\nResult:\n" + Arrays.toString(res));
    }
}

控制台：

X Y X Y   [if] VALUE

a b 1 0        1
b r 17 1       16
r a 0 17       -17
b a 0 1        -1
a a 0 0        0
b c 2 1   true -1
a c 2 0        2
c a 0 2        -2
a a 0 0        0
c d 3 2        1
r d 3 17       -14
b d 3 1        2
c a 0 2        -2
a a 0 0        0
a a 0 0        0
c b 1 2        -1
a b 1 0        1
a b 1 0        1
b r 17 1       16
d r 17 3       14
r r 17 17      0
c a 0 2        -2
a a 0 0        0
b a 0 1        -1
a a 0 0        0
#################################
Result:
[a, a, a, a, a, b, c, b, d, r, r]

Answer 3

见Javadoc for java.util.Comparator。它说方法 compare():

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.

对于您的情况，这意味着 compare( 'b', 'c' ) 应该 return 大于零，compare( 'c', 'b' ) 应该小于零，而自然顺序则相反。

但是您的第一个实现（那个错误的实现）仅涵盖了 compare( 'c', 'b' ) 的情况，而不是 compare( 'b', 'c' )，因此该方法将 return 成为默认值。

您的第二个正确的实施解决了这个问题。

使用 java 比较器对字符数组进行排序

Sort character array using java comparator

java

sorting

comparator

代码

控制台：