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

Sort arrays of primitive types in descending order

提问by Benedikt Waldvogel

I've got a largearray of primitive types (double). How do I sort the elements in descending order?

我有一个大阵列的原始类型（双）的。如何按降序对元素进行排序？

Unfortunately the Java API doesn't support sorting of primitive types with a Comparator.

不幸的是，Java API 不支持使用 Comparator 对原始类型进行排序。

The first approach that probably comes to mind is to convert it to a list of objects (boxing):

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

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

However, boxing each primitive in the array is too slow and causes a lot of GC pressure!

但是，将数组中的每个原语装箱太慢，并且会导致很大的 GC 压力！

Another approach would be to sort and then reverse:

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

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;
}

This approach is also slow- particularly if the array is already sorted quite well.

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

What's a better alternative?

什么是更好的选择？

采纳答案by Brandon

Java Primitiveincludes functionality for sorting primitive arrays based on a custom comparator. Using it, and Java 8, your sample could be written as:

Java Primitive包括基于自定义比较器对原始数组进行排序的功能。使用它和 Java 8，您的示例可以编写为：

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

If you're using Maven, you can include it with:

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

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

When you pass falseas the third argument to sort, it uses an unstable sort, a simple edit of Java's built-in dual-pivot quicksort. This means that the speed should be close to that of built-in sorting.

当您将false第三个参数传递给 时sort，它使用了不稳定的排序，即 Java 内置双枢轴快速排序的简单编辑。这意味着速度应该接近内置排序的速度。

Full disclosure: I wrote the Java Primitive library.

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

回答by Jason Cohen

Your implementation (the one in the question) is faster than e.g. wrapping with toList()and using a comparator-based method. Auto-boxing and running through comparator methods or wrapped Collections objects is far slower than just reversing.

您的实现（问题中的实现）比例如toList()使用基于比较器的方法包装和使用更快。自动装箱和通过比较器方法或包装的 Collections 对象运行比仅仅反转要慢得多。

Of course you could write your own sort. That might not be the answer you're looking for, butnote that if your comment about "if the array is already sorted quite well" happens frequently, you might do well to choose a sorting algorithm that handles that case well (e.g. insertion) rather than use Arrays.sort()(which is mergesort, or insertion if the number of elements is small).

当然，您可以编写自己的排序。这可能不是您正在寻找的答案，但请注意，如果您关于“如果数组已经排序得很好”的评论经常发生，那么您最好选择一种可以很好地处理这种情况的排序算法（例如插入）而不是使用Arrays.sort()（如果元素数量很少，则是归并排序或插入）。

回答by Eli Courtwright

There's been some confusion about Arrays.asListin the other answers. If you say

Arrays.asList在其他答案中存在一些混淆。如果你说

double[] arr = new double[]{6.0, 5.0, 11.0, 7.0};
List xs = Arrays.asList(arr);
System.out.println(xs.size());  // prints 1

then you'll have a List with 1 element. The resulting List has the double[] array as its own element. What you want is to have a List<Double>whose elements are the elements of the double[].

那么您将拥有一个包含 1 个元素的列表。结果 List 将 double[] 数组作为它自己的元素。你想要的是有一个List<Double>其元素是double[].

Unfortunately, no solution involving Comparators will work for a primitive array. Arrays.sortonly accepts a Comparator when being passed an Object[]. And for the reasons describe above, Arrays.asListwon't let you make a List out of the elements of your array.

不幸的是，没有涉及 Comparator 的解决方案适用于原始数组。 Arrays.sort仅在传递Object[]. 由于上述原因，Arrays.asList不会让您从数组元素中创建一个列表。

So despite my earlier answer which the comments below reference, there's no better way than manually reversing the array after sorting. Any other approach (such as copying the elements into a Double[]and reverse-sorting and copying them back) would be more code and slower.

因此，尽管我之前的回答是下面的评论所引用的，但没有比在排序后手动反转数组更好的方法了。任何其他方法（例如将元素复制到 a 中Double[]并进行反向排序并将它们复制回来）将代码更多且速度更慢。

回答by Leo

I am not aware of any primitive sorting facilities within the Java core API.

我不知道 Java 核心 API 中的任何原始排序工具。

From my experimentations with the D programming language(a sort of C on steroids), I've found that the merge sort algorithm is arguably the fastest general-purpose sorting algorithm around (it's what the D language itself uses to implement its sort function).

从我对D 编程语言（一种类固醇上的 C）的实验中，我发现合并排序算法可以说是最快的通用排序算法（它是 D 语言本身用来实现其排序功能的） .

• One implementation in Java
• Another implementation
• One more implementation

• Java 中的一种实现
• 另一种实现
• 再一个实现

回答by user29480

I think it would be best not to re-invent the wheel and use Arrays.sort().

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

Yes, I saw the "descending" part. The sorting is the hard part, and you want to benefit from the simplicity and speed of Java's library code. Once that's done, you simply reverse the array, which is a relatively cheap O(n) operation. Here's some codeI found to do this in as little as 4 lines:

是的，我看到了“下降”部分。排序是困难的部分，您希望从 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;
}

回答by Krystian Cybulski

You cannot use Comparators for sorting primitive arrays.

您不能使用 Comparator 对原始数组进行排序。

Your best bet is to implement (or borrow an implementation) of a sorting algorithm that is appropriate for your use case to sort the array (in reverse order in your case).

最好的办法是实现（或借用实现）适合您的用例的排序算法来对数组进行排序（在您的情况下以相反的顺序）。

回答by lakshmanaraj

Your algorithm is correct. But we can do optimization as follows: While reversing, You may try keeping another variable to reduce backward counter since computing of array.length-(i+1) may take time! And also move declaration of temp outside so that everytime it needs not to be allocated

你的算法是正确的。但是我们可以做如下优化：在反转时，您可以尝试保留另一个变量以减少反向计数器，因为 array.length-(i+1) 的计算可能需要时间！并且还将临时声明移到外面，以便每次都不需要分配

double temp;

for(int i=0,j=array.length-1; i < (array.length/2); i++, j--) {

     // swap the elements
     temp = array[i];
     array[i] = array[j];
     array[j] = temp;
}

回答by lakshmanaraj

double[] array = new double[1048576];

...

...

By default order is ascending

默认顺序是升序

To reverse the order

颠倒顺序

Arrays.sort(array,Collections.reverseOrder());

回答by myplacedk

If performance is important, and the list usually already is sorted quite well.

如果性能很重要，并且列表通常已经排序得很好。

Bubble sort should be one of the slowest ways of sorting, but I have seen cases where the best performance was a simple bi-directional bubble sort.

冒泡排序应该是最慢的排序方式之一，但我见过最好的性能是简单的双向冒泡排序。

So this may be one of the few cases where you can benefit from coding it yourself. But you really need to do it right (make sure at least somebody else confirms your code, make a proof that it works etc.)

因此，这可能是您可以从自己编码中受益的少数情况之一。但是你真的需要做对（确保至少有其他人确认你的代码，证明它有效等）

As somebody else pointed out, it may be even better to start with a sorted array, and keep it sorted while you change the contents. That may perform even better.

正如其他人指出的那样，从排序数组开始可能会更好，并在更改内容时保持排序。那可能会表现得更好。

回答by Sean Patrick Floyd

Guavahas methods for converting primitive arrays to Lists of wrapper types. The nice part is that these lists are live views, so operations on them work on the underlying arrays as well (similar to Arrays.asList(), but for primitives).

Guava具有将原始数组转换为包装类型列表的方法。好的部分是这些列表是实时视图，因此对它们的操作也适用于底层数组（类似于Arrays.asList()，但适用于原语）。

Anyway, each of these Lists can be passed to Collections.reverse():

无论如何，这些列表中的每一个都可以传递给Collections.reverse()：

int[] intArr = { 1, 2, 3, 4, 5 };
float[] floatArr = { 1.0f, 2.0f, 3.0f, 4.0f, 5.0f };
double[] doubleArr = { 1.0d, 2.0d, 3.0d, 4.0d, 5.0d };
byte[] byteArr = { 1, 2, 3, 4, 5 };
short[] shortArr = { 1, 2, 3, 4, 5 };
Collections.reverse(Ints.asList(intArr));
Collections.reverse(Floats.asList(floatArr));
Collections.reverse(Doubles.asList(doubleArr));
Collections.reverse(Bytes.asList(byteArr));
Collections.reverse(Shorts.asList(shortArr));
System.out.println(Arrays.toString(intArr));
System.out.println(Arrays.toString(floatArr));
System.out.println(Arrays.toString(doubleArr));
System.out.println(Arrays.toString(byteArr));
System.out.println(Arrays.toString(shortArr));

Output:

输出：

[5, 4, 3, 2, 1]
[5.0, 4.0, 3.0, 2.0, 1.0]
[5.0, 4.0, 3.0, 2.0, 1.0]
[5, 4, 3, 2, 1]
[5, 4, 3, 2, 1]

[5, 4, 3, 2, 1]
[5.0, 4.0, 3.0, 2.0, 1.0]
[5.0, 4.0, 3.0, 2.0, 1.0]
[5, 4, 3, 2, 1]
[5, 4, 3 , 2, 1]

回答by Green Beret

Double[] d = {5.5, 1.3, 8.8};
Arrays.sort(d, Collections.reverseOrder());
System.out.println(Arrays.toString(d));

Collections.reverseOrder() doesn't work on primitives, but Double, Integer etc works with Collections.reverseOrder()

Collections.reverseOrder() 不适用于原语，但 Double、Integer 等适用于 Collections.reverseOrder()