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

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

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

В других ответах была некоторая путаница по поводу 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[].

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

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

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

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

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

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

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

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

Ваш алгоритм верен. Но мы можем сделать оптимизацию следующим образом: При движении задним ходом вы можете попробовать сохранить другую переменную, чтобы уменьшить обратный счетчик, поскольку вычисление array.length- (i + 1) может занять время! А также переместите объявление temp наружу, чтобы каждый раз его не нужно было выделять

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

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

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

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

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

Гуава имеет методы для преобразования массивов примитивов в списки типов оболочки. Приятно то, что эти списки представляют собой живые представления, поэтому операции с ними работают и с базовыми массивами (аналогично 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]

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

Примитив 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>

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

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

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

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

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

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!

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

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

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

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

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

Подробное объяснение можно найти в моем сообщении в блоге здесь.

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

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

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

Вот однострочный, с использованием потоков в Java 8

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

Вот полная программа, которая сортирует объекты на основе внутреннего поля.

package Algorithms.BranchAndBound;

import java.util.Arrays;
import java.util.Comparator;

public class KnapSack01 {
    private class ItemVals {
        double weight;
        double cost;
        double ratio;

        public ItemVals(double weight, double cost) {
            this.weight = weight;
            this.cost = cost;
            this.ratio = weight/cost;
        }
    }

    public ItemVals[] createSortedItemVals(double[] weight, double[] cost) {
        ItemVals[] itemVals = new ItemVals[weight.length];
        for(int i = 0; i < weight.length; i++) {
            ItemVals itemval = new ItemVals(weight[i], cost[i]);
            itemVals[i] = itemval;
        }
        Arrays.sort(itemVals, new Comparator<ItemVals>() {
            @Override
            public int compare(ItemVals o1, ItemVals o2) {
                return Double.compare(o2.ratio, o1.ratio);
            }
        });
        return itemVals;
    }

    public void printItemVals(ItemVals[] itemVals) {
        for (int i = 0; i < itemVals.length; i++) {
            System.out.println(itemVals[i].ratio);
        }
    }

    public static void main(String[] args) {
        KnapSack01 knapSack01 = new KnapSack01();
        double[] weight = {2, 3.14, 1.98, 5, 3};
        double[] cost = {40, 50, 100, 95, 30};
        ItemVals[] itemVals = knapSack01.createSortedItemVals(weight, cost);
        knapSack01.printItemVals(itemVals);
    }
}