Какова временная сложность метода java.util.Collections.sort ()?

Question

Я написал следующий класс:

public class SortingObjectsWithAngleField implements Comparator<Point> {  
    public int compare(Point p1, Point p2) {
        double delta = p1.getAngle() - p2.getAngle();
        if(delta == 0.00001)
            return 0;
        return (delta > 0.00001) ? 1 : -1;
    }
}

Затем в моем методе main() я создал List, к которому я добавил несколько объектов с полями "X" и "angle".

Я тогда использую:

Collections.sort(list, new SortingObjectsWithAngleField());

В чем сложность этого метода сортировки?

Answer 1

Вы могли бы прочитать документы по сортировке Коллекций, но вот для вас:

Алгоритм сортировки - это измененная сортировка слиянием (в которой объединение опускается, если самый высокий элемент внизкий подсписок меньше, чем самый низкий элемент в высоком подсписке).Этот алгоритм обеспечивает гарантированную производительность n log (n).

Ваш Comparator не меняет эту сложность, если вы ничего не делаете с циклами над своей коллекцией, чего у вас нет.

Answer 2

Вы должны были найти его в API: n log (n) .

Answer 3

взято из Collections.sort -

Алгоритм сортировки представляет собой модифицированную сортировку слиянием (в которой объединение опускается, если самый высокий элемент в нижнем подсписке меньше самого низкого элемента в верхнем подсписке).Этот алгоритм предлагает гарантированную производительность n * log (n)

Answer 4

Каждый указал API doc , добавив некоторую более важную информацию, которую я нашел.

Если вы предоставите пользовательский компаратор, тогда будет измененная версия mergesort (также известная как timsort) используется.Реализация была заимствована из списка сортировки для python .

В лучшем случае требуется всего n-1 сравнений, поэтому best case is O(n) и guaranteed performance in all the cases is O(n.lg(n))