1

首先：这不是Partial Ordered Comparator问题的副本，而是建立在它之上。

我的目标是对对象列表（例如[2，“a”，1]）进行就地排序，以便在排序后没有两个整数出现乱序。

为此，我在这个答案中使用了以下部分排序的实现并得到了IllegalArgumentException：

java.lang.IllegalArgumentException: Comparison method violates its general contract!
        at java.util.TimSort.mergeHi(TimSort.java:868)
        at java.util.TimSort.mergeAt(TimSort.java:485)
        at java.util.TimSort.mergeCollapse(TimSort.java:410)
        at java.util.TimSort.sort(TimSort.java:214)
        at java.util.TimSort.sort(TimSort.java:173)
        at java.util.Arrays.sort(Arrays.java:659)
        at java.util.Collections.sort(Collections.java:217)
        at MySortUtils.sortPartially(ArimsCollectionUtils.java:150)

这是因为建议的比较器存在缺陷。示范：

对iff和都是整数并根据整数的自然排序的R所有Object实例使用偏序：a.before(b)aba < b

public boolean before(Object a, Object b) {
    // only integers are ordered
    if (a instanceof Integer && b instanceof Integer) {
        int intA = ((Integer) a).intValue();
        int intB = ((Integer) b).intValue();
        return intA < intB;
    } else {
        return false;
    }
}

原因是通过以下实现

Comparator<Object> fullCmp = new Comparator<Object>() {

  // Implementation shamelessly plucked from
  // https://stackoverflow.com/a/16702332/484293
  @Override
  public int compare(Object o1, Object o2) {
    if(o1.equals(o2)) {
      return 0;
    }
    if(partialComparator.before(o1, o2)) {
        return -1;
    }
    if(partialComparator.before(o2, o1)) {
        return +1;
    }
    return getIndex(o1) - getIndex(o2);
  }

  private Map<Object ,Integer> indexMap = new HashMap<>();

  private int getIndex(Object i) {
    Integer result = indexMap.get(i);
    if (result == null) {
        indexMap.put(i, result = indexMap.size());
    }
    return result;
  }
};

这可以在生成的排序中产生一个循环，因为

// since 2 and "a" are incomparable, 
// 2 gets stored with index 0 
// "a" with index 1
assert fullCmp.compare(2, "a") == -1   

// since "a" and 1 are incomparable,
// "a" keeps its index 1
// 2 gets index 2
assert fullCmp.compare("a", 1) == -1

// since 1 and 2 are comparable:
assert fullCmp.compare(1,   2) == -1

都是真的，即 2 < "a"、"a" < 1 和 "1 < 2，这显然不是有效的总排序。

这给我留下了最后一个问题：如何修复这个错误？

4

4 回答 4

3

我不能为任何部分排序建议一个完整的解决方案。但是，对于您的特定任务（比较整数忽略其他任何内容），您只需要决定整数是在其他任何事情之前还是之后。这个假设整数先行的比较器应该可以正常工作（使用 Java-8 语法）：

Comparator<Object> comparator = (a, b) -> {
    if(a instanceof Integer) {
        if(b instanceof Integer) {
            return ((Integer) a).compareTo((Integer) b);
        }
        return -1;
    }
    if(b instanceof Integer)
        return 1;
    return 0;
};

例子：

List<Object> list = Arrays.asList("a", "bb", 1, 3, "c", 0, "ad", -5, "e", 2);
list.sort(comparator);
System.out.println(list); // [-5, 0, 1, 2, 3, a, bb, c, ad, e]
于 2015-08-12T16:30:35.200 回答
1

您正在getIndex()比较器内部使用。这通常很好，但在排序算法中交换值时就不行了。
所以选择一个只依赖于值的比较器函数，而不是它们在数组中的位置。
您可以将非整数排序在所有整数之前或之后。要么使它们都相等（0在比较器中返回），要么使用一些额外的标准来区分它们。

于 2018-12-31T02:24:32.177 回答
0

如果您想要的只是根据自己的自然顺序对整数（而不是其他完全有序的类型）进行排序，并且如果您不关心其他元素如何按照整数排序，但您确实希望结果是正确的总排序（即传递和反对称），然后对您开始并拒绝的答案进行微小的变化就可以了：

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

class IntegerPartialOrderComperator implements Comparator<Object> {
    @Override
    public int compare(Object o1, Object o2) {
        return getIndex(o1) - getIndex(o2);
    }

    private int getIndex(Object i) {
        Integer result = indexMap.get(i);
        if (result == null) {
            if (i instanceof Integer) {
                result = (Integer) i*2;
            } else {
                result = indexMap.size()*2+1;
            }
            indexMap.put(i, result);
        }
        return result;
    }

    private Map<Object,Integer> indexMap = new HashMap<>();

    public static void main(String[] args) {
        Comparator<Object> cmp = new IntegerPartialOrderComperator();
        // since 2 and "a" are incomparable,
        // 2 gets stored with index 4 and "a" with index 3
        assert cmp.compare(2, "a") > 0;

        // since "a" and 1 are incomparable,
        // "a" keeps its index 3 while 1 gets index 2
        assert cmp.compare("a", 1) > 0;

        // since 1 and 2 are comparable:
        assert cmp.compare(1, 2) < 0;
    }
}

这使用运行时为所有值生成的索引作为比较的基础，其中偶数用作Integers 的索引，奇数用作可能出现的任何其他内容的索引。

如果您的数字可以变大（> 2^30-1）或变小（< -2^30），则加倍将溢出，因此您必须求助于BigInteger索引映射的值类型。

请注意，除了 之外，相同的技巧不适用于许多类型Integer，因为您首先需要通过索引号来描述您想要尊重的总顺序。我认为如果不可能的话，解决方案会变得更加棘手：为新元素计算索引可能会花费最坏的时间与先前比较的元素数量呈线性关系，而这只会破坏Comparatorfor 排序（有效地）。

于 2015-08-20T15:18:21.613 回答
-1

您可以将元素分组为可以相互比较的元素。你有 canCompare(a, b) 和 canCompare(b, c) 但 !canCompare(a, c) 的问题。但是，我们认为情况并非如此，您可以

  • 从一个元素开始并将其与所有其他元素进行比较。如果它与任何其他元素都无法比较，则添加到目前的结果中
  • 如果您发现它与一个或多个元素具有可比性，请对它们进行排序并将它们添加到结果中。
  • 继续这样做，直到没有更多的元素。

这并不适合 Comparable，因为您没有使用传统的排序算法。但是，如果您必须这样做，您可以首先确定所需的订单并比较所需订单的索引。

一个简单的解决方法是提供任意排序策略，以便您拥有总排序。你遇到的问题是，如果你排序1, "a", 2你期望发生什么？您可以将其保留为未定义，无论您是否得到1, 2, "a"，或者"a", 1, 2您说所有可比较的东西都已经井井有条。如果后者没问题，冒泡排序将完成这项工作。

您不能使用 TimSort 进行部分排序。它假设如果你比较a，b你可以说它是大于、等于还是小于。没有其他选择。

但是，其他排序算法没有这个要求。插入排序就是其中之一。唯一的要求是a < b，b < c然后a < c必须遵循，否则您无法订购这些条目。

顺便说一句，您不能拥有-1无与伦比的均值，因为-1通常均值大于。

你能做的是

static final int INCOMPARABLE = Integer.MIN_VALUE;

// since 2 and "a" are incomparable, 
// 2 gets stored with index 0 
// "a" with index 1
assert fullCmp.compare(2, "a") == INCOMPARABLE;  

// since "a" and 1 are incomparable,
// "a" keeps its index 1
// 2 gets index 2
assert fullCmp.compare("a", 1) == INCOMPARABLE;  

// since 1 and 2 are comparable:
assert fullCmp.compare(1,   2) == -1;

assert fullCmp.compare(2,   1) == 1;
于 2015-08-12T16:24:47.317 回答