Сортировать массивы примитивных типов в порядке убывания

Question

У меня большой массив примитивных типов (double). Как отсортировать элементы в в порядке убывания ?

К сожалению, Java API не поддерживает сортировку примитивных типов с помощью Comparator.

Один из обходных путей - отсортировать, а затем развернуть:

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

Это медленно - особенно если массив уже отсортирован довольно хорошо.

Какая альтернатива лучше?

Answer 1

Java Primitive включает в себя функциональность для сортировки примитивных массивов на основе пользовательского компаратора. Используя его и 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>

Когда вы передаете false в качестве третьего аргумента sort, он использует нестабильную сортировку, простое редактирование встроенной в Java быстрой развертки двойной поворот . Это означает, что скорость должна быть близка к скорости встроенной сортировки.

Полное раскрытие: я написал библиотеку Java Primitive.

Answer 2

Я думаю, что было бы лучше не изобретать велосипед и не использовать 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;
}

Answer 3

Guava имеет методы для преобразования примитивных массивов в списки типов оболочек. Приятно то, что эти списки являются живыми представлениями, поэтому операции с ними работают и с базовыми массивами (аналогично Arrays.asList(), но для примитивов).

В любом случае, каждый из этих списков может быть передан в 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));

Выход:

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

Answer 4

double[] array = new double[1048576];

...

По умолчанию порядок возрастает

Чтобы отменить заказ

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

Answer 5

Я думаю, что самое простое решение по-прежнему:

1. Получение естественного порядка массива
2. Нахождение максимума в этом отсортированном массиве, который является последним элементом
3. Использование цикла for с оператором декремента

Как уже говорили другие: использование toList - это дополнительное усилие, Arrays.sort (array, Collections.reverseOrder ()) не работает с примитивами, и использование дополнительной инфраструктуры кажется слишком сложным, когда все, что вам нужно, уже встроено и, следовательно, скорее всего и быстрее ...

Пример кода:

import java.util.Arrays;

public class SimpleDescending {

    public static void main(String[] args) {

        // unsorted array
        int[] integerList = {55, 44, 33, 88, 99};

        // Getting the natural (ascending) order of the array
        Arrays.sort(integerList);

        // Getting the last item of the now sorted array (which represents the maximum, in other words: highest number)
        int max = integerList.length-1;

        // reversing the order with a simple for-loop
        System.out.println("Array in descending order:");
        for(int i=max; i>=0; i--) {
            System.out.println(integerList[i]);
        }

        // You could make the code even shorter skipping the variable max and use
        // "int i=integerList.length-1" instead of int "i=max" in the parentheses of the for-loop
    }
}

Answer 6

Вы не можете использовать Компараторы для сортировки примитивных массивов.

Лучше всего реализовать (или заимствовать реализацию) алгоритм сортировки, который подходит для вашего варианта использования для сортировки массива (в обратном порядке в вашем случае).

Answer 7

С числовыми типами отрицание элементов до и после сортировки представляется возможным. Скорость относительно одного реверса после сортировки зависит от кэша, и если реверс не быстрее, любая разница может быть потеряна в шуме.

Answer 8

Ваша реализация (рассматриваемая) быстрее, чем, например, обтекание toList() и использование метода сравнения. Автобокс и запуск через методы компаратора или обернутые объекты коллекций намного медленнее, чем просто реверсирование.

Конечно, вы можете написать свой собственный вид. Это может быть не тот ответ, который вы ищете, , но обратите внимание, что если ваш комментарий о том, «массив уже достаточно хорошо отсортирован», встречается часто, вам лучше выбрать алгоритм сортировки, который будет case хорошо (например, вставка), а не использовать Arrays.sort() (который является сортировкой слиянием, или вставка, если число элементов мало).

Answer 9

В других ответах возникла путаница в отношении 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

тогда у вас будет список с 1 элементом. Результирующий список имеет массив double [] в качестве собственного элемента. Вам нужно иметь List<Double>, элементы которого являются элементами double[].

К сожалению, ни одно решение с участием Comparators не будет работать для примитивного массива. Arrays.sort принимает компаратор только при получении Object[]. И по причинам, описанным выше, Arrays.asList не позволит вам составить список из элементов вашего массива.

Так что, несмотря на мой предыдущий ответ, на который ссылаются комментарии ниже, нет лучшего способа, чем вручную перевернуть массив после сортировки. Любой другой подход (например, копирование элементов в Double[] и обратная сортировка и копирование их обратно) был бы более сложным и медленным.

Answer 10

Before sorting the given array multiply each element by -1 

, затем используйте Arrays.sort (arr), затем снова умножьте каждый элемент на -1

for(int i=0;i<arr.length;i++)
    arr[i]=-arr[i];
Arrays.sort(arr);
for(int i=0;i<arr.length;i++)
    arr[i]=-arr[i];