带空列表的加权顺序

Question

我一直在尝试实现一个 Comparator class，它应该根据位置的权重对列表进行排序。我会解释我应该完成什么。

假设我有一个ArrayList<T>。此数组列表始终具有固定大小，用 null 个值填充其他槽。

//fixed size = 3
T myObj1, myObj2;
[myObj1, null, myObj2];

在这个例子中，myObj2 < myObj1，因为它存储在一个位置值小于第一个的槽中。

排序比较器应给出此输出：

//fixed size = 3
T myObj1, myObj2;
[myObj1, myObj2, null];

其他示例：

//fixed size = 7;
T myObj1, myObj2, myObj3, myObj4;
INPUT = [myObj1, null, null, myObj4, myObj3, myObj2, null];
RESULT = [myObj1, myObj4, myObj3, myObj2, null, null, null];

想过用aComparator<T>（T是具体的class，其实不需要通用）；有没有办法复制这种行为？

Answer 1

你总是可以在比较器中使空值 return > 0

if (one == null && two == null) {
    return 0;
} else if (two == null) {
    return -1;
} if (one == null) {
    return 1;
} else {
   //Compare logic...
}

这表示空值 "bigger" 比非空值

Answer 2

对于任何有需要的人，感谢@tomgeraghty3

public class TComparator implements Comparator<T> {
    public int compare(T r1, T r2) {
        if (r1 == null && r2 == null) {
            return 0;
        } else if (r2 == null) {
            return -1;
        } if (r1 == null) {
            return 1;
        } else {
           return 1;
        }
    }
}

Answer 3

与其编写自己的比较器逻辑，不如使用 Comparator.comparing.

等辅助方法之一通常更简单

> List<Integer> foo = Arrays.asList(1, null, 2, null, 1, null);
> Collections.sort(foo, Comparator.comparing(x -> x == null ? 1 : 0));
> foo
[1, 2, 1, null, null, null]

这样排序就好像非null元素全为0，null为1，所以排序时null会出现在非null之后。非空元素将保持原来的顺序，因为 Collections.sort 是稳定的。

对于@Zabuza 指出的这种特定情况，辅助方法Comparator.nullsLast 做的事情完全正确；参数是 null 因为没有 "fallback" 我们想要用于非空元素的比较器。

> Collections.sort(foo, Comparator.nullsLast(null));

也就是说，对于长度为 n 的列表，此解决方案需要 O(n log n) 时间，而两指针解决方案可以在 O(n) 时间内解决相同的问题。

带空列表的加权顺序

Weighted order of List with Null

java

null

arraylist

comparator