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.