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

Ответ 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 dual-pivot быстрой сортировки. Это означает, что скорость должна быть близка к скорости встроенной сортировки.

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

Ответ 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;
}

Ответ 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]

Ответ 4

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

• Получение естественного порядка массива
• Поиск максимального значения внутри этого отсортированного массива, который является последним элементом
• Использование for-loop с оператором декремента

Как уже говорилось другими: использование 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
    }
}

Ответ 5

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

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

Ответ 6

В других ответах была некоторая путаница в отношении 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 элементом. В результате List имеет двойной массив [] как свой собственный элемент. Вы хотите иметь List<Double>, элементы которого являются элементами double[].

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

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

Ответ 7

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

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

Ответ 8

double[] array = new double[1048576];

...

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

Чтобы отменить порядок

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

Ответ 9

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

Ответ 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];

Ответ 11

Мне не известно о каких-либо примитивных параметрах сортировки в Java API.

Из моих экспериментов с D языком программирования (своего рода C на стероидах), я обнаружил, что алгоритм сортировки слияния возможно, самый быстрый алгоритм сортировки общего назначения (это то, что сам язык D использует для реализации своей функции сортировки).

• Одна реализация в Java
• Другая реализация
• Еще одна реализация

Ответ 12

Ваш алгоритм правильный. Но мы можем сделать оптимизацию следующим образом: При обратном, вы можете попытаться сохранить другую переменную для уменьшения обратного счетчика, поскольку вычисление 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;
}

Ответ 13

Если производительность важна, и список обычно уже отсортирован достаточно хорошо.

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

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

Как заметил кто-то другой, может быть даже лучше начать с сортированного массива и сохранить его отсортированным, пока вы меняете содержимое. Это может работать еще лучше.

Ответ 14

для небольших массивов это может работать.

int getOrder (double num, double[] array){
    double[] b = new double[array.length];
    for (int i = 0; i < array.length; i++){
        b[i] = array[i];
    }
    Arrays.sort(b);
    for (int i = 0; i < b.length; i++){
        if ( num < b[i]) return i;
    }
    return b.length;
}

Я был удивлен, что начальная загрузка массива b необходима

double[] b = array; // makes b point to array. so beware!

Ответ 15

Если вы используете java8, просто конвертируйте массив в поток, сортируйте и конвертируйте обратно. Все задачи могут выполняться только в одной строке, поэтому я чувствую, что это не так уж плохо.

double[] nums = Arrays.stream(nums).boxed().
        .sorted((i1, i2) -> Double.compare(i2, i1))
        .mapToDouble(Double::doubleValue)
        .toArray();

Ответ 16

Ниже мое решение, вы можете адаптировать его к вашим потребностям.

Как это работает? Он принимает массив целых чисел в качестве аргументов. После этого он создаст новый массив, который будет содержать те же значения, что и массив из аргументов. Причина этого заключается в том, чтобы оставить исходный массив неповрежденным.

Как только новый массив содержит скопированные данные, мы сортируем его, заменяя значения до тех пор, пока условие if (newArr [i] < newArr [i + 1]) не станет равным false. Это означает, что массив сортируется в порядке убывания.

Для подробного объяснения проверьте мой блог здесь.

public static int[] sortDescending(int[] array)
{
    int[] newArr = new int[array.length];

    for(int i = 0; i < array.length; i++)
    {
        newArr[i] = array[i];
    }

    boolean flag = true;
    int tempValue;

    while(flag) 
    {
        flag = false;

        for(int i = 0; i < newArr.length - 1; i++) 
        {
            if(newArr[i] < newArr[i+1])
            {
                tempValue = newArr[i];
                newArr[i] = newArr[i+1];
                newArr[i+1] = tempValue;
                flag = true;
            }
        }
    }

    return newArr;
}

Ответ 17

Понимаю, это очень старый пост, но я наткнулся на похожую проблему, пытаясь отсортировать примитивные массивы int, поэтому публикую свое решение. Предложения/комментарии приветствуются -

int[] arr = {3,2,1,3};
List<Integer> list = new ArrayList<>();
Arrays.stream(arr).forEach(i -> list.add(i));
list.stream().sorted(Comparator.reverseOrder()).forEach(System.out::println);

Ответ 18

double s =-1;
   double[] n = {111.5, 111.2, 110.5, 101.3, 101.9, 102.1, 115.2, 112.1};
   for(int i = n.length-1;i>=0;--i){
      int k = i-1;
      while(k >= 0){
          if(n[i]>n[k]){
              s = n[k];
              n[k] = n[i];
              n[i] = s;
          }
          k --;
      }
   }
   System.out.println(Arrays.toString(n));
 it gives time complexity O(n^2) but i hope its work

Ответ 19

Вот одна строка, использующая потоки в Java 8

int arr = new int[]{1,2,3,4,5};
Arrays.stream(arr).boxed().sorted(Collections.reverseOrder()).mapToInt(Integer::intValue).toArray();

Ответ 20

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

Collections.reverseOrder() не работает с примитивами, но Double, Integer и т.д. работают с Collections.reverseOrder()

Ответ 21

В Java 8 лучшим и более кратким подходом может быть:

double[] arr = {13.6, 7.2, 6.02, 45.8, 21.09, 9.12, 2.53, 100.4};

Double[] boxedarr = Arrays.stream( arr ).boxed().toArray( Double[]::new );
Arrays.sort(boxedarr, Collections.reverseOrder());
System.out.println(Arrays.toString(boxedarr));

Это даст обратный массив и будет более презентабельным.

Исходные данные: [13,6, 7,2, 6,02, 45,8, 21,09, 9,12, 2,53, 100,4]

Выход: [100,4, 45,8, 21,09, 13,6, 9,12, 7,2, 6,02, 2,53]