Меню

Сливане на обединяване в Java - Програма за внедряване на

  • Основен
  • Други
  • Сливане на обединяване в Java - Програма за внедряване на

merge sort java program implement mergesort

Опитайте Нашия Инструмент За Премахване На Проблемите

Този урок обяснява какво е Merge Sort в Java, MergeSort Algorithm, Pseudo Code, Merge Sort Implementation, Примери за итеративно и рекурсивно MergeSort:

Техниката за сортиране чрез сливане използва стратегия „Разделяй и владей“. При тази техника наборът от данни, който трябва да се сортира, се разделя на по-малки единици, за да се сортира.

=> Прочетете серията Easy Training Training.

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

Какво ще научите:

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

Например, ако даден масив трябва да бъде сортиран с помощта на mergesort, тогава масивът е разделен около средния си елемент на два под-масива. Тези два под-масива са допълнително разделени на по-малки единици, докато имаме само 1 елемент на единица.

След като разделянето приключи, тази техника обединява тези отделни единици, като сравнява всеки елемент и ги сортира при сливане. По този начин, докато целият масив се обедини обратно, получаваме сортиран масив.

В този урок ще обсъдим всички подробности за тази техника за сортиране като цяло, включително нейния алгоритъм и псевдо кодове, както и прилагането на техниката в Java.

MergeSort Algorithm In Java

Следва алгоритъмът за техниката.

# 1) Декларирайте масив myArray с дължина N

# две) Проверете дали N = 1, myArray вече е сортиран

# 3) Ако N е по-голямо от 1,

  • задайте ляво = 0, дясно = N-1
  • изчисли средата = (вляво + вдясно) / 2
  • Извикайте подпрограма merge_sort (myArray, ляво, средна) => това сортира първата половина на масива
  • Извикайте подпрограма merge_sort (myArray, средно + 1, вдясно) => това ще сортира втората половина на масива
  • Извикайте сливането на подпрограмата (myArray, ляво, средно, дясно), за да обедините масиви, сортирани в горните стъпки.

# 4) Изход

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

Обединяване на сортиране на псевдо код

Нека да видим псевдокода за техниката Mergesort. Както вече беше обсъдено, тъй като това е техника „разделяй и владей“, ще представим процедурите за разделяне на набора от данни и след това обединяване на сортираните набори от данни.

procedure mergesort( var intarray as array ) if ( n == 1 ) return intarray var lArray as array = intarray(0) ... intarray (n/2) var rArray as array = intarray (n/2+1) ... intarray (n) lArray = mergesort(lArray ) rArray = mergesort(rArray ) return merge(lArray, rArray ) end procedure procedure merge( var l_array as array, var r_array as array ) var result as array while (l_array and r_array have elements ) if (l_array (0) > r_array (0) ) add r_array (0) to the end of result remove r_array (0) from r_array else add l_array (0) to the end of result remove l_array (0) from l_array end if end while while (l_array has elements ) add l_array (0) to the end of result remove l_array (0) from l_array end while while (r_array has elements ) add r_array (0) to the end of result remove r_array (0) from r_array end while return result end procedure

В горния псевдокод имаме две процедури, т.е. Mergesort и merge. Подпрограмата Mergesort разделя входния масив на индивидуален масив, който е достатъчно лесен за сортиране. След това извиква рутинното сливане.

Подпрограмата за сливане обединява отделните под-масиви и връща резултантно сортиран масив. След като видяхме алгоритъма и псевдокода за сортиране на Merge, нека сега илюстрираме тази техника, като използваме пример.

MergeSort илюстрация

Помислете за следния масив, който трябва да бъде сортиран с помощта на тази техника.

Обединяване на илюстрация за сортиране

Сега, според алгоритъма за сортиране Merge, ще разделим този масив в средния му елемент на два подмасива. След това ще продължим да разделяме под-масивите на по-малки масиви, докато не получим по един елемент във всеки масив.

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

Процесът е показан по-долу:

Процес на сортиране на обединяване

Както е показано на горната илюстрация, виждаме, че масивът се разделя многократно и след това се обединява, за да се получи сортиран масив. Имайки предвид тази концепция, нека преминем към внедряването на Mergesort в езика за програмиране Java.

Обединяване на изпълнението на сортиране в Java

Можем да приложим техниката в Java, използвайки два подхода.

Итеративно сортиране на обединяване

Това е подход отдолу нагоре. Под-масивите от всеки един елемент се сортират и обединяват, за да образуват масиви от два елемента. След това тези масиви се обединяват, за да образуват масиви от четири елемента и така нататък. По този начин сортираният масив се изгражда чрез преминаване нагоре.

Долният пример на Java показва итеративната техника на сортиране на обединяване.

import java.util.Arrays; class Main { // merge arrays : intArray(start...mid) and intArray(mid+1...end) public static void merge(int() intArray, int() temp, int start, int mid, int end) { int k = start, i = start, j = mid + 1; // traverse through elements of left and right arrays while (i <= mid && j <= end) { if (intArray(i) < intArray(j)) { temp(k++) = intArray(i++); } else { temp(k++) = intArray(j++); } } // Copy remaining elements while (i <= mid) { temp(k++) = intArray(i++); } // copy temp array back to the original array to reflect sorted order for (i = start; i <= end; i++) { intArray(i) = temp(i); } } // sorting intArray(low...high) using iterative approach public static void mergeSort(int() intArray) { int low = 0; int high = intArray.length - 1; // sort array intArray() using temporary array temp int() temp = Arrays.copyOf(intArray, intArray.length); // divide the array into blocks of size m // m = (1, 2, 4, 8, 16...) for (int m = 1; m <= high - low; m = 2*m) { for (int i = low; i < high; i += 2*m) { int start = i; int mid = i + m - 1; int end = Integer.min(i + 2 * m - 1, high); //call merge routine to merge the arrays merge(intArray, temp, start, mid, end); } } } public static void main(String() args) { //define array to be sorted int() intArray = { 10,23,-11,54,2,9,-10,45 }; //print the original array System.out.println('Original Array : ' + Arrays.toString(intArray)); //call mergeSort routine mergeSort(intArray); //print the sorted array System.out.println('Sorted Array : ' + Arrays.toString(intArray)); } }

Изход:

Оригинален масив: (10, 23, -11, 54, 2, 9, -10, 45)
Сортиран масив: (-11, -10, 2, 9, 10, 23, 45, 54)

Итеративно сортиране на обединяване - изход

Сортиране на рекурсивно сливане

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

Следващият Java код реализира рекурсивния подход на техниката за сортиране Merge.

import java.util.Arrays; public class Main { public static void merge_Sort(int() numArray) { //return if array is empty if(numArray == null) { return; } if(numArray.length > 1) { int mid = numArray.length / 2; //find mid of the array // left half of the array int() left = new int(mid); for(int i = 0; i

Изход:

Оригинален масив: (10, 23, -11, 54, 2, 9, -10, 45)
Сортиран масив: (- 11, -10, 2, 9, 10, 23, 45, 54)

Рекурсивен MergeSort - изход

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

Сортиране на свързан списък с помощта на обединяване Сортиране в Java

Техниката Mergesort е най-предпочитаната за сортиране на свързани списъци. Други техники за сортиране се представят слабо, когато става въпрос за свързания списък, поради предимно последователния му достъп.

Следващата програма сортира свързан списък, използвайки тази техника.

import java.util.*; // A singly linked list node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } }; class Main { //two sorted linked list are merged together to form one sorted linked list public static Node Sorted_MergeSort(Node node1, Node node2) { //return other list if one is null if (node1 == null) return node2; else if (node2 == null) return node1; Node result; // Pick either node1 or node2, and recur if (node1.data <= node2.data) { result = node1; result.next = Sorted_MergeSort(node1.next, node2); } else { result = node2; result.next = Sorted_MergeSort(node1, node2.next); } return result; } //splits the given linked list into two halves public static Node() FrontBackSplit(Node source) { // empty list if (source == null || source.next == null) { return new Node(){ source, null } ; } Node slow_ptr = source; Node fast_ptr = source.next; // Advance 'fast' two nodes, and advance 'slow' one node while (fast_ptr != null) { fast_ptr = fast_ptr.next; if (fast_ptr != null) { slow_ptr = slow_ptr.next; fast_ptr = fast_ptr.next; } } // split the list at slow_ptr just before mid Node() l_list = new Node(){ source, slow_ptr.next }; slow_ptr.next = null; return l_list; } // use Merge sort technique to sort the linked list public static Node Merge_Sort(Node head) { // list is empty or has single node if (head == null || head.next == null) { return head; } // Split head into 'left' and 'right' sublists Node() l_list = FrontBackSplit(head); Node left = l_list(0); Node right = l_list(1); // Recursively sort the sublists left = Merge_Sort(left); right = Merge_Sort(right); // merge the sorted sublists return Sorted_MergeSort(left, right); } // function to print nodes of given linked list public static void printNode(Node head) { Node node_ptr = head; while (node_ptr != null) { System.out.print(node_ptr.data + ' -> '); node_ptr = node_ptr.next; } System.out.println('null'); } public static void main(String() args) { // input linked list int() l_list = { 4,1,6,2,7,3,8 }; Node head = null; for (int key: l_list) { head = new Node(key, head); } //print the original list System.out.println('Original Linked List: '); printNode(head); // sort the list head = Merge_Sort(head); // print the sorted list System.out.println(' Sorted Linked List:'); printNode(head); } }

Изход:

Оригинален свързан списък:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> нула
Сортиран свързан списък:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> нула

какво е инструмент за събиране на данни

Резултат - Сортиране на свързан списък

Сортирай ArrayList с помощта на Merge Sort In Java

Подобно на масиви и свързани списъци, ние също можем да използваме тази техника за сортиране на ArrayList. Ще използваме подобни процедури, за да разделяме ArrayList рекурсивно и след това да обединяваме подлистите.

По-долу Java кодът реализира техниката за сортиране Merge за ArrayList.

import java.util.ArrayList; class Main { //splits arrayList into sub lists. public static void merge_Sort(ArrayList numList){ int mid; ArrayList left = new ArrayList<>(); ArrayList right = new ArrayList<>(); if (numList.size() > 1) { mid = numList.size() / 2; // left sublist for (int i = 0; i numList, ArrayList left, ArrayList right){ //temporary arraylist to build the merged list ArrayList temp = new ArrayList<>(); //initial indices for lists int numbersIndex = 0; int leftIndex = 0; int rightIndex = 0; //traverse left and righ lists for merging while (leftIndex = left.size()) { temp = right; tempIndex = rightIndex; } else { temp = left; tempIndex = leftIndex; } for (int i = tempIndex; i numList = new ArrayList<>(); int temp; //populate the ArrayList with random numbers for (int i = 1; i <= 9; i++) numList.add( (int)(Math.random() * 50 + 1) ); //print original ArrayList of random numbers System.out.println('Original ArrayList:'); for(int val: numList) System.out.print(val + ' '); //call merge_Sort routine merge_Sort(numList); //print the sorted ArrayList System.out.println(' Sorted ArrayList:'); for(int ele: numList) System.out.print(ele + ' '); System.out.println(); } }

Изход:

Оригинален списък с масиви:
17 40 36 7 6 23 35 2 38
Сортиран списък с масиви:
2 6 7 17 23 35 36 38 40

Изход - Сортирай ArrayList

често задавани въпроси

В # 1) Може ли сортирането на обединяване да се извършва без рекурсия?

Отговор: Да. Можем да извършим нерекурсивно сортиране на обединяване, наречено „итеративно сортиране на обединяване“. Това е подход отдолу-нагоре, който започва чрез обединяване на под-масиви с един елемент в под-масив от два елемента.

След това тези под-масиви с 2 елемента се обединяват в под-масиви с 4 елемента и така нататък, използвайки итеративни конструкции. Този процес продължава, докато имаме сортиран масив.

Q # 2) Може ли да се извърши сортиране на обединяване на място?

Отговор: Сортирането на обединяване обикновено не е на място. Но можем да го направим на място, като използваме някои интелигентни приложения. Например, чрез съхраняване на стойност на два елемента на една позиция. Това може да бъде извлечено след това с помощта на модул и разделяне.

Q # 3) Какво е тристепенно обединяване?

Отговор: Техниката, която видяхме по-горе, е двупосочно сортиране на Merge, при което разделяме масива, за да бъде сортиран на две части. След това сортираме и обединяваме масива.

При трипосочно сортиране Merge, вместо да разделяме масива на 2 части, ние го разделяме на 3 части, след това сортираме и накрая го обединяваме.

Q # 4) Каква е сложността във времето на Mergesort?

Отговор: Общата времева сложност на Merge sort във всички случаи е O (nlogn).

Q # 5) Къде се използва сортирането Merge?

Отговор: Използва се най-вече при сортиране на свързания списък за O (nlogn) време. Той се използва и в разпределени сценарии, при които нови данни влизат в системата преди или след сортиране. Това се използва и в различни сценарии на база данни.

Заключение

Сливането на обединяване е стабилно сортиране и се извършва чрез първо разделяне на множеството данни многократно на подмножества и след това сортиране и обединяване на тези подмножества, за да се формира сортиран набор от данни. Наборът от данни се разделя, докато всеки набор от данни е тривиален и лесен за сортиране.

Видяхме рекурсивния и итеративен подход към техниката на сортиране. Също така обсъдихме сортирането на структурата от данни на Linked List и ArrayList, използвайки Mergesort.

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

=> Посетете тук за ексклузивната серия уроци за обучение по Java.

Препоръчително четене

^