3

我正在尝试对一些 ( Mutable)IntList对象进行排序。装箱/拆箱整数的成本与我的程序相关（这正是我使用原始集合的原因）。我想按以下标准排序：

  • 所有负数都在非负数之前
  • 首先是最小（最接近于零）的数字

[1, 7, 0, -9, -3] -> [-3, -9, 0, 1, 7]

Eclipse Collections 库中的类是否有IntList允许自定义比较器的排序方法？到目前为止我还没有找到它，但是定义的符号列表很大，搜索框只匹配精确的字符串，并且几乎不存在文档（我相信大部分是从方法签名自动生成的）。

我最后的手段是编写自己的 int-int 比较器和排序函数，这没什么大不了的，但我宁愿不这样做。

请不要浪费您的时间来编写概念证明分类器，我将不胜感激。我知道如何对列表进行排序，但我只是不知道如何在 Eclipse Collections 文档中找到东西。如果您可以提供帮助，请随时将其包含在您的答案中。

4

3 回答 3

3

从 10.3 版开始，Eclipse Collections 中引入了对原始集合的间接排序支持。可变原始集合支持它。您可以在https://medium.com/javarevisited/eclipse-collections-now-supports-indirect-sorting-of-primitive-lists-e2447ca5dbc3查看更多详细信息和使用示例

OP 示例如下所示：

@Test
public void soTest()
{
    // [1, 7, 0, -9, -3] -> [-3, -9, 0, 1, 7]
    MutableIntList list = IntLists.mutable.of(1, 7, 0, -9, -3);

    list.sortThis((a, b) -> {
        // negative before non-negative
        // otherwise, smallest numbers first
        if (a == b) { return 0; }
        if (a < 0 && b < 0) {
            return (a < b) ? 1 : -1;
        }
        return (a < b) ? -1 : 1;}
    );

    Assert.assertEquals(IntLists.immutable.of(-3, -9, 0, 1, 7), list);
}

比较器 lambda 可以简化为：

list.sortThis((a, b) ->
        (a < 0 && b < 0) ? Integer.compare(b, a) : Integer.compare(a, b));
于 2021-03-28T17:57:44.560 回答
1

由于这里也没有“快速”的答案，我继续自己实现了这样的分类设备。

public class IntListUtils {
    public interface IntIntComparator {
        int compare(int a, int b);
    }

    public static void sort(MutableIntList subject, IntIntComparator comparator) {
        quicksort(subject, 0, subject.size() - 1, comparator);
    }

    public static void quicksort(MutableIntList subject, int low, int high, IntIntComparator comparator) {
        if (low >= high) { return; }
        int pivot = partition(subject, low, high, comparator);
        quicksort(subject, low, pivot - 1, comparator);
        quicksort(subject, pivot, high, comparator);
    }

    private static int partition(MutableIntList subject, int low, int high, IntIntComparator comparator) {
        int pivot = subject.get(high);
        int i = low;
        for (int j = low; j <= high - 1; j++) {
            if (comparator.compare(subject.get(j), pivot) < 0) {
                int t = subject.get(i);
                subject.set(i, subject.get(j));
                subject.set(j, t);
                i += 1;
            }
        }
        int t = subject.get(i);
        subject.set(i, subject.get(high));
        subject.set(high, t);
        return i;
    }
}

可以使用它来实现我上面描述的排序顺序：

MutableIntList list = ...;
IntListUtils.sort(list, (a, b) -> {
    // negative before non-negative
    // otherwise, smallest numbers first
    if (a == b) { return 0; }
    if (a < 0 && b < 0) {
        return (a < b) ? 1 : -1;
    }
    return (a < b) ? -1 : 1;
});

编辑：我意识到这种快速排序并不是目前最快的排序方法，但它所要做的就是比排序后将我的整个IntList转换为 aList<Integer>并返回更快，这在排序时分配 O(n) 内存（n 很大）方法就地发生。

于 2018-10-04T14:39:27.463 回答
1

IntList 是MutableIntList和 ImmutableIntList 扩展的接口。

我看到有一个在这种情况下可以帮助你的实现类是IntArrayList，它是 MutableIntList 的实现。

有一个 sortThis() 方法正在执行

Arrays.sort(this.items, 0, this.size);

因此，对于您而言，它将返回 -9, -3, 0, 1, 7

但我注意到你想要 -3、-9、0、1、7。我不确定这是一个错字还是这是一个要求。当您检查时，我们可以进一步讨论

于 2018-10-04T14:08:06.180 回答