Дан набор объектов, которые имеют 2 значения.Сортировать набор по 1-му значению, а затем по 2-му значению

Question

Например:

{2,3},{1,2},(2,2},{3,1},{2,1} to {1,2},{2,1},{2,2},{2,3},{3,1}

Вот что я думаю:

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

Объединить сортировать этот список во втором столбце, а затем интегрировать их в основной набор. Хотя это кажется возможным, это кажется слишком сложным. Это должно работать в O(NlogN), поэтому, если кто-то может придумать более быстрый / такой же сложный алгоритм, который также проще, пожалуйста, опубликуйте его!

Спасибо!

Answer 1

Просто реализуйте Comparator<T>, который сравнивает любые два объекта вашего типа, сначала сравнивая первое поле, а затем переходит ко второму полю, если первые поля равны.Затем вы можете скопировать набор в список, позвонить по номеру Collections.sort и передать ему список и свой компаратор.Нет необходимости реализовывать сортировку самостоятельно.

Компаратор будет выглядеть примерно так:

public class TwoFieldComparator implements Comparator<Foo>
{
    public int compare(Foo first, Foo second)
    {
        // TODO: null checks
        int firstComparison = Integer.compare(first.x, second.x);
        return firstComparison != 0 ? firstComparison
                                    : Integer.compare(first.y, second.y);
    }
}

В качестве альтернативы, вы можете сделать так, чтобы ваш класс реализовывал Comparable<T> таким же образом.

Answer 2

Что вам нужно сделать, это выполнить стабильную сортировку по второму столбцу, а затем еще раз по первому столбцу.

Если диапазон чисел может быть определен, O (N) может быть достигнут с некоторой линейной сортировкой.

РЕДАКТИРОВАТЬ:

Возьмите «сортировку слиянием» в качестве примера(это стабильно):
1, Запустите сортировку слиянием во втором столбце, затем пары чисел будут расположены в соответствии со значением второго столбца.
2, Запустите сортировку слиянием снова в первом столбце, числопары будут расположены в порядке значения первого столбца.Однако, поскольку метод сортировки стабилен, это означает, что если первое число одинаково, второе число будет также отсортировано (мы сделали это в первом порядке).

Таким образом, числопара массив в порядке сейчас.Больше никаких действий не требуется.
Сортировка слиянием - это O (NlogN), поэтому 2 * O (NlogN) - это все еще O (NlogN).

EDIT2:
Что ж, я мог бы усложнить эту проблему,Даже если метод сортировки должен быть реализован нами самостоятельно, пока определена структура данных, заполнение кода сравнения Jon Skeet в соответствующей части метода ручной сортировки будет наиболее удобным способом.

Answer 3

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

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