Как да обединим два сортирани масива в Java

1. Въведение

В този урок ще научим как да обединим два сортирани масива в един сортиран масив.

2. Проблем

Нека разберем проблема. Имаме два сортирани масива и бихме искали да ги обединим в един.

3. Алгоритъм

Когато анализираме проблема, е доста лесно да забележим, че можем да разрешим този проблем, като използваме операцията за сливане на Merge Sort.

Да приемем, че имаме два сортирани масива 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. Сложност

Прекосяваме и двата масива и избираме по-малкия елемент. В крайна сметка, ние копиране на останалите елементи от на Mt. или бар масив. Така сложността на времето става O (fooLength + barLength) . Използвахме спомагателен масив, за да получим резултата. Така че космическата сложност също е O (fooLength + barLength) .

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

В този урок научихме как да обединим два сортирани масива в един.

Както обикновено, изходният код за този урок може да бъде намерен в GitHub.