Сравнение и сортировка в Java

Question

У меня есть 2 массива данных в Java.Основываясь на порядке первого массива, я должен отсортировать следующий массив.Например -

String[] Array1 = {"EUROPE","MIDDLEEAST","OTHERs","AUSTRALIA"};
String[] Array2 = {"MIDDLEEAST","EUROPE","AUSTRALIA","OTHERs","ASIA","EUROPE"};

Мой вывод должен выглядеть следующим образом:

{"EUROPE","EUROPE","MIDDLEEAST","OTHERs","AUSTRALIA","ASIA"}

Как лучше всего это сделать?

Answer 1

Для сортировки вам необходимо определить порядок сортировки, чтобы по заданным элементам A и B можно было легко определить, должен ли A идти до или после B в отсортированном списке.

Эта концепция формализована с концепцией Comparator в Java.

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

В зависимости от размера ваших данных это может быть слишком медленно. Затем вы можете создать HashMap<String,Long>, который содержит индекс данной строки в Array1. Здесь он будет содержать «DEF» -> 0, «ABC» -> 1, «XYZ» -> 2.

Answer 2

Две другие идеи:

1. Могут ли эти значения быть enum, а не набором строк? Естественным порядком перечисления является порядок объявления, поэтому Arrays.sort() просто сработает.

2. Вспомогательный код существует в Guava Ordering.explicitOrder (List) :

   String[] explicitOrder = {"EUROPE", "MIDDLEEAST", "OTHERs", "AUSTRALIA"};
   String[] toSort = ...
   
   Comparator<String> comparator = Ordering.explicit(Arrays.asList(explicitOrder));
   String[] sorted = Arrays.sort(toSort, comparator); 
   

Answer 3

Существует (как минимум) два способа сортировки одного массива и переупорядочения второго массива, чтобы соответствующие элементы по-прежнему совпадали. И то, и другое требует построения третьего массива и написания пользовательской функции сравнения.

Метод 1

Определить пользовательский объект, который содержит один элемент каждого массива. (В вашем случае это может быть массив из двух элементов String.) Напишите компаратор (или реализуйте Comparable) для пользовательского объекта, который просто сравнивает элементы из первого массива. Создайте массив пользовательских объектов из двух входных массивов, отсортируйте третий массив и затем извлеките результаты.

Этот метод чаще всего рекомендуется для этой проблемы.

Метод 2

Создание массива целочисленных индексов, инициализированных 0, 1, 2, ..., n-1 (где n == Array1.length). Сортируйте массив индексов с помощью компаратора, который сравнивает индексы, сравнивая индексируемые элементы Array1.

Второй метод будет более быстрым и не потребует столько строительства объекта.

Answer 4

Вы определенно можете сделать это в O (n log n). Но лучший подход зависит от того, что важнее: быстрый, чистый код или отсутствие выделения дополнительной памяти.

Если вам не нужно использовать дополнительную память, вы можете выделить отдельный массив, где каждый элемент представляет собой пару:

public class Pair implements Comparable {
  ...
}

Тогда вы бы отсортировали массив пар, используя Arrays.sort(Object[]).

Если вы не хотите выделять достаточно много места, вы можете использовать вспомогательный массив, содержащий индексы в форме Integer:

final String[] array1 = ...;
final String[] array2 = ...;

assert array1.length == array2.length;

Comparator<Integer> c = new Comparator<Integer> {
  int compare(Integer a, Integer b) {
    return array1[a].compareTo(array1[b]);
  }
};

Integer[] aux = new Integer[array1.length];
for (int i = 0; i < aux.length; ++i) { aux[i] = i; }
Arrays.sort(aux, c);

String[] result = new String[array1.length];
for (int i = 0; i < aux.length; ++i) {
  result[i] = array2[aux[i]];
}

Если вы пытаетесь сделать все на месте и не выделять дополнительную память, то вам нужно будет самостоятельно реализовать один из алгоритмов сортировки n-log-n ...

Answer 5

Может быть так:

1) Сортировать их оба.

2) Создать пустую таблицу результатов

3) Взять первый элемент из отсортированного массива 2 и поместить егоТаблица результатов с исходным индексом первого элемента в отсортированном массиве Array1

3) Повторите шаг 3 для второго элемента и так далее.

Сложность вычислений будет похожа на используемый метод сортировки: O (nlogn) для быстрой сортировки