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

1. Въведение

В този урок ще разгледаме алгоритъма Merge Sort и прилагането му в Java .

Сливането на обединяване е една от най-ефективните техники за сортиране и се основава на парадигмата „разделяй и владей“.

2. Алгоритъмът

Сливането на обединяване е алгоритъм „разделяй и владей“, при който първо разделяме проблема на подпроблеми. Когато решенията за подзадачите са готови, ние ги комбинираме заедно, за да получим окончателното решение на проблема.

Това е един от алгоритмите, който може лесно да се приложи с помощта на рекурсия, тъй като се справяме с подпроблемите, а не с основния проблем.

Алгоритъмът може да бъде описан като следния двуетапен процес:

  • Разделяне: В тази стъпка разделяме входния масив на 2 половини , като въртенето е средната точка на масива. Тази стъпка се извършва рекурсивно за всички половин масиви, докато няма повече половин масиви за разделяне.
  • Conquer: В тази стъпка сортираме и обединяваме разделените масиви отдолу нагоре и получаваме сортирания масив.

Следващата диаграма показва пълния процес на сортиране на обединяване за примерен масив {10, 6, 8, 5, 7, 3, 4}.

Ако разгледаме по-отблизо диаграмата, можем да видим, че масивът е разделен рекурсивно на две половини, докато размерът стане 1. След като размерът стане 1, процесите на сливане влизат в действие и започват да обединяват масиви обратно при сортиране:

3. Прилагане

За изпълнението ще напишем функция mergeSort, която приема параметрите на входния масив и неговата дължина . Това ще бъде рекурсивна функция, така че се нуждаем от основата и рекурсивните условия.

Основното условие проверява дали дължината на масива е 1 и то просто ще се върне. В останалите случаи рекурсивното повикване ще бъде изпълнено.

За рекурсивния случай получаваме средния индекс и създаваме два временни масива l [] и r [] . След това функцията mergeSort се извиква рекурсивно и за двата под-масива:

public static void mergeSort(int[] a, int n) { if (n < 2) { return; } int mid = n / 2; int[] l = new int[mid]; int[] r = new int[n - mid]; for (int i = 0; i < mid; i++) { l[i] = a[i]; } for (int i = mid; i < n; i++) { r[i - mid] = a[i]; } mergeSort(l, mid); mergeSort(r, n - mid); merge(a, l, r, mid, n - mid); }

След това извикваме функцията за сливане, която приема входа и както под-масивите, така и началния и крайния индекс на двата под-масива .

Функцията за сливане сравнява елементите на двата под-масива един по един и поставя по-малкия елемент във входния масив.

Когато достигнем края на един от под-масивите, останалите елементи от другия масив се копират във входния масив, като по този начин ни дават окончателния сортиран масив:

public static void merge( int[] a, int[] l, int[] r, int left, int right) { int i = 0, j = 0, k = 0; while (i < left && j < right) { if (l[i] <= r[j]) { a[k++] = l[i++]; } else { a[k++] = r[j++]; } } while (i < left) { a[k++] = l[i++]; } while (j < right) { a[k++] = r[j++]; } } 

Единичен тест за програмата:

@Test public void positiveTest() { int[] actual = { 5, 1, 6, 2, 3, 4 }; int[] expected = { 1, 2, 3, 4, 5, 6 }; MergeSort.mergeSort(actual, actual.length); assertArrayEquals(expected, actual); }

4. Сложност

Тъй като сортирането по сливане е рекурсивен алгоритъм, сложността на времето може да бъде изразена като следната рекурсивна връзка:

T(n) = 2T(n/2) + O(n)

2T (n / 2) съответства на времето, необходимо за сортиране на подмасивите и O (n) време за обединяване на целия масив.

Когато се реши, сложността във времето ще достигне до O (nLogn).

Това важи за най-лошия, средния и най-добрия случай, тъй като винаги ще разделя масива на две и след това ще се слее.

Сложността на пространството на алгоритъма е O (n), тъй като ние създаваме временни масиви във всяко рекурсивно повикване.

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

В този бърз урок видяхме как работи алгоритъмът за сортиране на сливане и как можем да го приложим в Java.

Целият работен код е достъпен в GitHub.