Как я могу отсортировать ArrayList быстрее?

Question

Я делаю проект класса, и мне нужно отсортировать ArrayLists пользовательских объектов на основе значений их атрибутов int.

Я сейчас использую что-то вроде этого:

public static void Sort(ArrayList <MyObject> objectList){

    for (int i = 0; i < list.size()-1; i++){

        for (int j = 0; j < list.size()-1; j++){

            if (objectList.get(j).getA() > objectList.get(j+1).getA()){

                Collections.swap(objectList, j, j+1);
            }
        }    
    }    
}

Программа работает хорошо, если ArrayList имеет менее 10 ^ 4 элементов. Но если я попытаюсь отсортировать 10 ^ 5 элементов, это займет несколько минут, и мне нужно отсортировать 10 ^ 6 элементов. Есть предложения?

Answer 1

В настоящее время ваша реализация равна O(n^2), что означает, что по мере роста массива время будет увеличиваться квадратично.

Не вдаваясь в подробности использования mergesort (O(log(n) x n)), самый быстрый способ - использовать встроенное решение Java для сортировки.

Collections.sort(list);

Ссылка на API .Существует также Collection.sort(list, comparator), который позволяет вам предоставить собственный компаратор .

Хотите, чтобы это было еще быстрее?Вы можете использовать новую функцию Java , которая позволяет выполнять параллельную сортировку с несколькими ядрами.Вот API .Обратите внимание, что Arrays.sort() и Arrays.parallelSort() принимают массив в качестве первого параметра.Вам нужно будет преобразовать список в массив, используя list.toArray().

Наконец, обратите внимание, что List#sort() был введен только в Java 8.

Answer 2

Используйте метод List::sort:

objectList.sort(Comparator.comparing(MyObject::getA));

Как упоминалось ниже @lexicore, похоже, что getA() возвращает числовой тип, и в этом случае, если он возвращает int, тогда лучшеиспользуйте comparingInt вместо comparing выше, если это long, используйте comparingLong или float / double, тогда используйте comparingDouble для повышения производительности.