按降序对基元类型数组进行排序

sorting java

2022-08-31 16:13:41

我有大量的基元类型（双精度）。如何按降序对元素进行排序？

不幸的是，Java API不支持使用比较器对基元类型进行排序。

可能想到的第一种方法是将其转换为对象列表（装箱）：

double[] array = new double[1048576];    
Arrays.stream(array).boxed().sorted(Collections.reverseOrder())…

但是，对数组中的每个基元进行装箱太慢，并且会造成很大的GC压力！

另一种方法是排序，然后反转：

double[] array = new double[1048576];
...
Arrays.sort(array);
// reverse the array
for (int i = 0; i < array.length / 2; i++) {
     // swap the elements
     double temp = array[i];
     array[i] = array[array.length - (i + 1)];
     array[array.length - (i + 1)] = temp;
}

这种方法也很慢 - 特别是如果数组已经很好地排序。

什么是更好的选择？

答案 1

我认为最好不要重新发明轮子并使用Arrays.sort（）。

是的，我看到了“下降”部分。排序是困难的部分，您希望从Java库代码的简单性和速度中受益。完成此操作后，您只需反转数组，这是一个相对便宜的O（n）操作。下面是一些代码我发现在短短4行中就可以做到这一点：

for (int left=0, right=b.length-1; left<right; left++, right--) {
    // exchange the first and last
    int temp = b[left]; b[left]  = b[right]; b[right] = temp;
}

答案 2

Java 基元包括基于定制比较器对基元数组进行排序的功能。使用它和Java 8，你的示例可以写成：

double[] array = new double[1048576];
...
Primitive.sort(array, (d1, d2) -> Double.compare(d2, d1), false);

如果您使用的是 Maven，则可以将其包含在以下各项中：

<dependency>
    <groupId>net.mintern</groupId>
    <artifactId>primitive</artifactId>
    <version>1.2.1</version>
</dependency>

当您将第三个参数传递给时，它使用不稳定的排序，这是对Java内置的双透视快速排序的简单编辑。这意味着速度应接近内置排序的速度。falsesort

完全披露：我写了Java Primitive库。