«1. Введение

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

2. Проблема

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

Merge Sorted Arrays

3. Алгоритм

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

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

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

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

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

Шаг 1:

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

Merge Arrays First Step

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

Шаг 2:

Merge Arrays Second Step

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

Шаг 3:

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

Шаг 4:

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

Merge Arrays Fourth Step

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.