Как отсортировать массив или ArrayList <Point>ASC сначала по x, а затем по y?

Question

Я просто хочу использовать Collections.sort или Arrays.sort для сортировки списка точек (класс Point) сначала по x, а затем по y.

У меня есть класс Ponto, который реализует Comparable следующим образом:

public int compareTo(Ponto obj) {
        Ponto tmp = obj;
        if (this.x < tmp.x) {
            return -1;
        } else if (this.x > tmp.x) {
            return 1;
        }
        return 0;
    }

но теперь я хочу отсортировать по y тоже после x.

Как я могу это сделать, изменив приведенный выше код?Или это лучший и "чистый" способ сделать это?Я также использую этот код для передачи в C ++, в котором я создал структуру под названием Point с эквивалентным сопоставимым методом.

Answer 1

Замените return 0 тем же алгоритмом сравнения на this.y и obj.y.

Кстати, переназначение на tmp здесь не нужно. Оптимизированная картинка может выглядеть так:

public int compareTo(Ponto other) {
    if (this.x == other.x) {
        return (this.y < other.y) ? -1 : ((this.y == other.y) ? 0 : 1);
    } else {
        return (this.x < other.x) ? -1 : 1;
    }
}

Answer 2

BalusC дает правильный ответ: в основном вы отдаете приоритет x над y. Вот вариант, написанный с использованием вложенных тернарных операторов, который проясняет приоритет.

public int compareTo(Ponto other) {
    return
      (this.x < other.x) ? -1 :
      (this.x > other.x) ? +1 :
      (this.y < other.y) ? -1 :
      (this.y > other.y) ? +1 :
      0;
}

Другой способ сделать это, если вы не хотите писать пользовательский Comparator<T> для каждой приоритетной схемы, - это выполнить множественную сортировку с использованием stable алгоритма.

Если вы хотите заказать по x (основной), а затем y (дополнительный), то:

• Сортировать по y сначала (!!!)
• Затем сортировка по x с использованием стабильной сортировки

Это асимптотически все еще O(N log N), но, конечно, вы делаете несколько этапов. Это удобно, когда у вас много критериев сортировки. Вместо того, чтобы писать сложный код, просто сделайте многоэтапное (и оптимизируйте, только если / когда это необходимо).

Итак, если у вас есть ключи сортировки k1, k2, k3, ..., kM, в том порядке приоритета, вы делаете:

• Сортировать по kM
• Стабильная сортировка по kM-1
• ...
• Стабильная сортировка по k1
• СДЕЛАНО!

Обратите внимание, что Collections.sort стабильно.

Этот сорт гарантированно будет стабильным : равные элементы не будут переупорядочены в результате сортировки.