Как объединить два отсортированных массива в Java

1. Введение

В этом уроке мы узнаем, как объединить два отсортированных массива в один отсортированный массив.

2. Проблема

Давайте разбираться в проблеме. У нас есть два отсортированных массива, и мы хотели бы объединить их в один.

3. Алгоритм

Когда мы анализируем проблему, довольно легко заметить, что мы можем решить эту проблему, используя операцию слияния сортировки слиянием .

Допустим, у нас есть два отсортированных массива foo и bar длины fooLength и barLength соответственно. Затем мы можем объявить другой объединенный массив размером fooLength + barLength .

Затем мы должны пройти оба массива в одном и том же цикле. Мы будем поддерживать текущее значение индекса для каждого, fooPosition и barPosition . На данной итерации нашего цикла мы берем любой массив, в индексе которого находится элемент с меньшим значением, и продвигаем этот индекс. Этот элемент займет следующую позицию в объединенном массиве.

Наконец, как только мы перенесли все элементы из одного массива, мы скопируем оставшиеся элементы из другого в объединенный массив.

Теперь давайте посмотрим на процесс в картинках, чтобы лучше понять алгоритм.

Шаг 1:

Мы начинаем со сравнения элементов в обоих массивах и выбираем меньший.

Затем мы увеличиваем позицию в первом массиве.

Шаг 2:

Здесь мы увеличиваем позицию во втором массиве и переходим к следующему элементу, который равен 8.

Шаг 3:

В конце этой итерации мы прошли все элементы первого массива.

Шаг 4:

На этом этапе мы просто копируем все оставшиеся элементы из второго массива в результат .

4. Реализация

Теперь давайте посмотрим, как это реализовать:

public static int[] merge(int[] foo, int[] bar) {

    int fooLength = foo.length;
    int barLength = bar.length;

    int[] merged = new int[fooLength + barLength];

    int fooPosition, barPosition, mergedPosition;
    fooPosition = barPosition = mergedPosition = 0;

    while(fooPosition < fooLength && barPosition < barLength) {
        if (foo[fooPosition] < bar[barPosition]) {
            merged[mergedPosition++] = foo[fooPosition++];
        } else {
            merged[mergedPosition++] = bar[barPosition++];
        }
    }

    while (fooPosition < fooLength) {
        merged[mergedPosition++] = foo[fooPosition++];
    }

    while (barPosition < barLength) {
        merged[mergedPosition++] = bar[barPosition++];
    }

    return merged;
}

И приступим к краткому тесту:

@Test
public void givenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray() {

    int[] foo = { 3, 7 };
    int[] bar = { 4, 8, 11 };
    int[] merged = { 3, 4, 7, 8, 11 };

    assertArrayEquals(merged, SortedArrays.merge(foo, bar));
}

5. Сложность

Мы просматриваем оба массива и выбираем меньший элемент. В конце копируем остальные элементы из массива foo или bar . Таким образом, временная сложность становится O(fooLength + barLength) . Мы использовали вспомогательный массив для получения результата. Таким образом, пространственная сложность также равна O(fooLength + barLength) .

6. Заключение

В этом уроке мы узнали, как объединить два отсортированных массива в один.

Как обычно, исходный код этого руководства можно найти на GitHub .