Въведение в сливането сортиране алгоритми в Java
Алгоритмите за сортиране на сливания са много важни в компютърните науки. Резултатът от сортирането е да подредите елементите от списък в определен ред (възходящ или низходящ). Сливането сортиране е един от най-ефективните алгоритми за сортиране, наличен, тъй като се основава на концепцията за разделяне и завладяване. Както подсказва името, първо разделете по-големия проблем на малки проблеми, отколкото разрешете по-малките, за да разрешите по-големия проблем. В тази статия ще обсъдим Алгоритмите за сортиране на сливане в Java. В концептуален план сортирането на сливане е комбинация от два основни алгоритма, наречени MERGE и MERGE_SORT, който работи както следва:
- Разделете несортирания списък на n брой под-списъци с единични елементи (n е общият брой елементи в несортирания списък).
- Многократно сливат подлистите в сортирани подлистове, докато има само един сортиран списък.
Внедряване на алгоритми за сортиране на сливане в Java
Алгоритъмът MERGE е процедурата за комбиниране на два сортирани списъка в един сортиран списък.
Пример: Да предположим, че има два списъка, т.е. списък 1 (6, 3) и списък 2 (3, 1, 9).
1. Първо сортирайте двата списъка.
Списък 1
Списък 2
Сега ще приложим техника за сливане върху него.
- След това ще създадем нов списък с размер m + n, където m е броят на елементите в Списък 1, а n е броят на елементите в Списък 2.
Списък 3
В нашия случай m = 2 и n = 3, така че m + n = 5.
- Сега имаме двупоказател. Първи показалец, сочещ към първата позиция на списък 1, и втори показалец, сочещ към първата позиция на списък 2.
4. След това ще сравним стойността на двата указателя. Показалеца с по-малка стойност копирайте този елемент в Списък 3 и преместете показалеца вдясно от списъка с по-малка стойност и резултата от списъка (т.е. Списък 1 и Списък 3).
5. По същия начин изпълнете стъпка 4 отново и отново.
По-нататъшно преминаване … ..
ЗАБЕЛЕЖКА: Ако някой от списъците (т.е. списък 1 или списък 2) бъде напълно преминат, както в горния случай, след това копирайте цялото съдържание на други списъци от показалеца в списъка с резултати (т.е. списък 3), както следва.
Алгоритъм и псевдокод
Двата алгоритма, използвани в обединения алгоритъм, са:
- MERGE (ARR, F, M, L) е процес, който предполага следното:
- ARR (F… .M) и ARR (M + 1… .L) са сортирани списъци.
- Обединява двата сортирани под-списъка в един ARR (F… .L).
- SORT (ARR (), F, L) // тук F е първият, а L е последният индекс на масива.
Ако (L> 1)
- Намерете средната точка, за да разделите списъка на две половини:
средна M = (F + L) / 2
- Сортиране на обаждания за първото полувреме:
Обадете се SORT (ARR, 1, M)
- Сортиране на обаждания за втората половина:
Обадете се SORT (ARR, M + 1, L)
- Обединете половините, сортирани в стъпки 2 и 3:
Обадете се MERGE (ARR, L, M, R)
пример
Нека вземем пример за масив ARR (10, 6, 8, 5, 7, 3, 4). Ще използваме алгоритъма за сливане, за да сортираме масива, използвайки неговата Техника за разделяне и завладяване. Можем да видим по-долу фигурата, че масивът е рекурсивно разделен на две половини, докато размерът стане 1. След като размерът стане 1, ние извикваме процеси на сливане и започваме обединяване на списъци обратно, докато пълният списък не бъде обединен.
ЗАБЕЛЕЖКА: На фигурата по-долу цифрите в червено показват реда, в който стъпките се обработват, за да образуват сортиран масив.
Програмен код:
import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)
изход:
Заключение - Обединяване на сортиране на алгоритми в Java
Обединяване сортиране най-добри, най-лоши и средно сложни времеви сложности са същите, което го прави по-ефективен алгоритъм. Работи по-бързо от другите техники за сортиране. Сливане сортиране може да се приложи към файлове от всякакъв размер. Той е силно паралелен поради използването на метода на разделяне и завладяване. За да развиете силни основи в компютърните науки, ви съветваме да разберете подробно различни алгоритми за сортиране.
Препоръчителни статии
Това е ръководство за сливане на сортиране на алгоритми в Java. Тук обсъждаме Прилагането на Алгоритми за сортиране на сливане в Java и Алгоритъм и псевдокод с пример. Можете да разгледате и другите ни предложени статии -
- Сортиране на селекцията в Java
- Декларация на случая в Java
- Достъп до модификатори в Java
- Сливане Сортиране в JavaScript
- Какво представлява изявлението на случая в JavaScript?
- Достъп Модификатори в PHP
- Бързо сортиране на алгоритми в Java
- Пълно ръководство за сортиране в C # с примери
- Функция за сортиране в Python с примери
- Топ 6 алгоритъм за сортиране в JavaScript