Сортировка списка мест

Question

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

Это правильный выбор?

Большое спасибо

Answer 1

Если это List локаций, я бы выбрал Collections.sort + пользовательский Comparator:

final Location myLocation = someLocation;

Collections.sort(locations, new Comparator<Location>() {
    @Override
    public int compare(Location o1, Location o2) {
        Float dist1 = o1.distanceTo(myLocation);
        Float dist2 = o2.distanceTo(myLocation);
        return dist1.compareTo(dist2);
    }
});

Answer 2

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

Сортировка вставки имеет наихудшую временную сложность Senario O (n ^ 2) [n - количество элементов в списке], означающее, что если список для сортировки был перевернутым отсортированным списком, он должен был бы пройти через весь список для каждого объекта в списке, чтобы отсортировать его. Это может не показаться проблемой, если у вас нет очень больших списков.

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