-1

实现 Java 比较器以使用自定义排序对集合进行排序的最佳方式（就时间和空间效率而言）是什么。例如 - 我想使用以下顺序对数组进行排序 -

RWQOJMVAHBSGZXNTCIEKUPDYFL

我有以下 Java 代码可以按预期工作，但不确定是否有任何其他有效的方法可以做到这一点。

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.lang.Math;

public class DiffSort {

    private static String order = "RWQOJMVAHBSGZXNTCIEKUPDYFL";

    // sort with comparator
    public static Comparator<String> diffNaturalOrder = new Comparator<String>() {
        public int compare(String v, String w) {
            int diff = 0, iter = 0;
            Integer index1, index2;
            Integer len1 = v.length();
            Integer len2 = w.length();
            int len = Math.min(len1, len2); // lesser of 2 strings

            for(int i=0; i<len; i++) {
                index1 = order.indexOf(v.charAt(i));
                index2 = order.indexOf(w.charAt(i));
                // if both chars are absent in order string, use natural ordering
                if(index1 == -1 && index2 == -1)
                    diff = new Character(v.charAt(i)).compareTo(new Character(w.charAt(i)));
                else if(index1 == -1 && index2 > 0)
                    diff = 1;
                else if(index1 > 0 && index2 == -1)
                    diff = -1;
                else
                    diff = index1.compareTo(index2);
                // break if we found mismatch
                if(diff != 0) break;
            }

            // return smaller string first in sort
            if(diff == 0)
                diff = len1.compareTo(len2);
            return diff;
        }
    };

    // test client
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        list.add("ABCE1!4");
        list.add("ABCE1!7");
        list.add("!SDF");
        list.add("TRWESF!");
        Collections.sort(list, DiffSort.diffNaturalOrder);

        // print sorted array
        for(String s:list)
            System.out.println(s);
    }
}

/* 输出 */

ABCE1!4

ABCE1!7

特维斯！

!SDF

4

4 回答 4

5

将 的所有字符order放入 a Map<Character, Integer>（其中整数对应于字符在 中的位置order），然后放入for-loop 中，而不是order.indexOf(c)use map.get(c)。

您可以相当轻松地设置此地图：

private static final Map<Character, Integer> map = 
                                new HashMap<Character, Integer>(order.length());

static {
    for (int i = 0; i < order.length(); i++)
        map.put(order.charAt(i), i);
}
于 2013-08-05T20:33:03.263 回答
2

我还要做的是缓存位置关闭字符的计算。

首先 w 将在签入地图之前比较字符是否相等。

然后在地图中将存储每个字符组合。

（左右）

如果 left 更早，则返回 1，如果 right 更早，则返回 -1，如果 left eq right 返回 0。

或者您可以创建一个 char 数组并在 char 的位置下存储订单。

public final class CustomAlphabetComparator implements Comparator<String> {

        private char order[] = new char[1<<16];


        public CustomAlphabetComparator (String alphabet) {
            if (alphabet == null) throw new IllegalArgumentException("Input must not be null");

            char index = 0;

            for(char c : alphabet.toCharArray()) {
                order[c] = index++;
            }
        }


        @Override
        public int compare(String o1, String o2) {

            if(o1 == o2) return 0; //We check the references

            if(o1 == null && o2 == null) return  0;
            if(o1 != null && o2 == null) return  1;
            if(o1 == null && o2 != null) return -1;

            if(o1.equals(o2)) return 0; //We check that are equal

            char[] c1 = o1.toCharArray();
            char[] c2 = o2.toCharArray();

            int shortest = c1.length < c2.length ? c1.length : c2.length;
            int result = 0;

            for(int i = 0; result == 0 & i < shortest; i++ ) {

                result = order[c1[i]] - order[c2[i]];

            }

            return result;
        }

    }
于 2013-08-05T20:37:44.310 回答
0

这是一个仅适用于大写英文字母的有效比较器（可以扩展，但并非没有限制）：

public static Comparator<String> diffNaturalOrder = new Comparator<String>() {
    private int[] order = new int[] {7, 9, 16, 22, 18, 24, 11, 8, 17, 4, 19, 25, 5, 14, 3, 21, 2, 0, 10, 15, 20, 6, 1, 13, 23, 12};
    public int compare(String v, String w) {
        int diff = 0;
        int len = Math.min(v.length(), w.length()); // lesser of 2 strings
        int o1, o2;
        for(int i=0; i<len; i++) {
            o1 = order[v.charAt(i)-65];
            o2 = order[w.charAt(i)-65];
            diff = o1 - o2;
            // break if we found mismatch
            if(diff != 0) break;
        }
        if (diff == 0) {
            diff = v.length() - w.length();
        }
        return diff;
    }
};

而不是indexOfor a Map<Character, Integer>，它使用 char 的整数值（小于 65）来索引包含排序数据的数组。数组可以这样生成：

private static void generateArray() {
    String order = "RWQOJMVAHBSGZXNTCIEKUPDYFL";
    int[] chars = new int[26];
    int i = 0;
    for (char c : order.toCharArray()) {
        chars[c-65] = i++;
    }
    System.out.println(Arrays.toString(chars));
}
于 2013-08-05T20:50:34.413 回答
0

显然，您拥有的代码有效，但要记住的一件事是 String.indexOf(ch) 逐个字符地遍历字符串，直到找到它正在寻找的那个。如果您的字符串接近“字母”的末尾，您将产生很多不必要的循环。

我会将排序存储在 a 中HashMap<Character, Integer>，并在恒定时间内从中提取索引信息。应该比遍历整个字符串更快（对于您要比较的每个字符！）...

于 2013-08-05T20:38:05.707 回答