自定义比较器

Question

给定以下列表："A", "B", "C", "D", "E", "F", "G"

我需要一个可以进行以下排序的比较器：

指定某个元素（例如"D"）
从元素
后跟原始列表的所有后续元素（按原始顺序）
后跟原始列表中所有前面的元素，按原始顺序排列

结果将是："D", "E", "F", "G", "A", "B", "C"

请注意，我知道我可以做类似于以下的事情：

List<String> following = myList.subList(myList.indexOf("D") + 1, myList.size());
List<String> preceding = myList.subList(0, myList.indexOf("D"));
List<String> newList = Stream.of(Collections.singletonList("D"), following, preceding)
                       .flatMap(List::stream)
                       .collect(Collectors.toList());

在这个问题中，我明确表示 Comparator 实现。

很明显，它必须有列表&元素作为参数，我只是不清楚比较算法本身：

private static class MyComparator<T> implements Comparator<T> {

  private final List<T> list;
  private final T element;

  private MyComparator(List<T> list, T element) {
    this.list = list;
    this.element = element;
  }

  @Override
  public int compare(T o1, T o2) {
    // Not clear
  }
}

Answer 1

如果我答对了你该怎么做Collections.sort(myList, myComparator);

那么我可以建议您使用定义的整理器：

List<String> myList = Arrays.asList("A", "B", "C", "D", "E", "F", "G");
System.out.println(myList);
String rules = "< d,D < e,E < f,F < g,G < a,A < b,B < c,C";

RuleBasedCollator ruleBasedCollator = new RuleBasedCollator(rules);
Collections.sort(myList, ruleBasedCollator);
System.out.println(myList);

这里的规则是"< d,D < e,E < f,F < g,G < a,A < b,B < c,C"这意味着哪些字符比其他字符具有更高的权重...剩下的就是通常的排序方法

输出

[A, B, C, D, E, F, G]

[D, E, F, G, A, B, C]

Answer 2

在这里使用 Comparator 没有多大意义，因为它会非常低效（因为你必须在原始列表中找到 2 个比较元素的索引，这会导致每次比较都需要线性时间）。

如果列表包含重复项，它可能无论如何都会失败。

但是，既然你问了，这样的事情可能会奏效：

public int compare(T o1, T o2) {
    if (o1.equals(o2)
        return true;
    int i1 = list.indexOf(o1);
    int i2 = list.indexOf(o2);
    int ie = list.indexOf(element); // this can be done in the constructor of the Comparator
    // now you have to check whether i1 and i2 are smaller than or larger than
    // ie, and based on that determine which of the corresponding elements should come
    // first
}

或者，直接调用

Collections.rotate(list,list.size() - list.indexOf(element));

Answer 3

我想这就是你想要的:

class ImposedOrder<T> implements Comparator<T> {

    private final List<T> list;
    private final int startIndex;

    ImposedOrder(List<T> list, T startElement) {
        this.list = new ArrayList<>(list);
        this.startIndex = list.indexOf(startElement);
        if (startIndex < 0) {
            throw new IllegalArgumentException();
        }
    }

    @Override
    public int compare(T t1, T t2) {
        int t1Index = list.indexOf(t1);
        int t2Index = list.indexOf(t2);
        return Integer.compare(adjust(t1Index), adjust(t2Index));
    }

    private int adjust(int rawIndex) {
        if (rawIndex >= startIndex) {
            return rawIndex;
        }
        return rawIndex + list.size();
    }
}

一些额外的验证可能是为了避免强加的重复顺序列表。

使用 indexOf 的线性搜索性能不佳，但对于小订单列表可能就足够了。否则，您可以将元素映射到比较器构造函数中调整后的索引，而不是保存强加顺序列表的副本。

像这样：

class ImposedOrder<T> implements Comparator<T> {

    private final Map<T, Integer> map;
    private final int startIndex;

    ImposedOrder(List<T> list, T startElement) {
        this.startIndex = list.indexOf(startElement);
        if (startIndex < 0) {
            throw new IllegalArgumentException();
        }
        this.map = IntStream.range(0, list.size())
                .boxed()
                .collect(Collectors.toMap(
                        list::get,
                        i -> adjust(startIndex, list.size(), i)
                ));
    }

    @Override
    public int compare(T t1, T t2) {
        Integer t1Index = map.get(t1);
        Integer t2Index = map.get(t2);
        return t1Index.compareTo(t2Index);
    }

    private static int adjust(int startIndex, int size, int rawIndex) {
        if (rawIndex >= startIndex) {
            return rawIndex;
        }
        return rawIndex + size;
    }
}

Answer 4

我知道这是可能的，但它很乱...... 而且不安全

将第一个块推到最后的想法是添加一个 String 以强制这些值更大。这样，如果 "A" 在比较时看起来像 "ZA"，则它比 "G" 大。

    List<String> list = Arrays.asList(new String[]{ "A", "B", "C", "D", "E", "F"});
    final String split = "D";
    Collections.sort(list, new Comparator<String>(){
        public int compare(String o1, String o2) {
            //Prepend with a big String value (like "ZZZZ") if it is before the value `split`.
            if(o1.compareTo(split) < 0)
                o1 = "ZZZZ" + o1;
            if(o2.compareTo(split) < 0)
                o2 = "ZZZZ" + o2;

            return o1.compareTo(o2); //then compare
        }
    });

    System.out.println(list);

[D, E, F, A, B, C]

这不安全，因为在前面加上一个更大的安全值可能会很复杂，我考虑过使用 Character.MAX_VALUE，但我不确定这是否更安全。好吧，使用 split 值本身可能更简单..

Answer 5

您需要比较元素的索引。

private static class MyComparator<T> implements Comparator<T> {

    private final List<T> list;
    private final int elementIndex;

    private MyComparator(List<T> list, T element) {
        // keep original order
        this.list = new ArrayList<>(list);
        this.elementIndex = list.indexOf(element);
    }

    @Override
    public int compare(T o1, T o2) {
        int i1 = list.indexOf(o1);
        int i2 = list.indexOf(o2);
        if (i1 == elementIndex) {
            // "shift" first element left
            return -1;
        } else if (i2 == elementIndex) {
            // "shift" secont element left
            return 1;
        }
        boolean left1 = i1 < elementIndex;
        boolean left2 = i2 < elementIndex;
        if (left1 != left2) {
            // different part
            return i2 - elementIndex;
        } else {
            // same part
            return i1 - i2;
        }
    }
}

Answer 6

思想是根据列表中的原始索引比较元素的权重——如果当前元素的索引 >= 指定特定元素的索引（例如 "D"），则在新的索引中列表应向左移动，"D" 的索引正是所需的偏移量。

int weightO1 = list.indexOf(o1) - list.indexOf(element);

在相反的情况下 (list.indexOf(o1) < list.indexOf(element)) 权重的计算应该将元素向右移动，例如可能是

int weightO1 = list.indexOf(o1) + list.size();

我会在本地方法中封装权重计算：

   int weight (T o) {
    return int weight = list.indexOf(o) < list.indexOf(element) ? list.indexOf(o) + list.size() : list.indexOf(o) - list.indexOf(element);
   }

所以比较方法的实现是这样的：

@Override
  public int compare(T o1, T o2) {
     return weight(o1) - weight(o2); 
  }

自定义比较器

Custom Comparator

java

sorting

list

comparator