带空列表的加权顺序

Question

我一直在尝试实现Comparator类，该类应根据位置的权重对列表进行排序。我将解释我应该完成的工作。

假设我有一个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];

我考虑过使用a Comparator<T>（T是一个特定的类，实际上并不需要是一般的）；有没有办法复制这种行为？

Answer 1

您总是可以在比较器中使null返回> 0

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

这说空值比非空值“大”

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之类的辅助方法之一。

Comparator.comparing

这样，排序就好像非null元素全为0，而null为1，因此在对非null进行排序时，它们将出现在非null之后。非空元素将保留其原始顺序，因为

> 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]

是稳定的。

就是说，当双指针解决方案可以在O（n）时间内解决相同的问题时，此解决方案需要O（n log n）的时间来获取长度为n的列表。