Въведение в сортирането на алгоритми в Java
Да сортирате информацията в определен ред, често в рамките на подобен на масив, означава да ги подредите. Можете да използвате различни изисквания за последователност, популярни от тях са сортирането на числа от най-малко до най-големите или обратно, или лексикографски сортиране на низове. Ще обхванем различни алгоритми, от неефективни, но интуитивни алтернативи до ефективни алгоритми, ефективно прилагани в Java и на други езици, ако се интересувате от това как да сортирате.
Различни алгоритми за сортиране в Java
Има различни алгоритми за сортиране и не всички от тях са еднакво ефективни. За да ги сравним и видим кои от тях се представят най-добре, ще анализираме техните сложни времена.
- Сортиране на вмъкване
- Сортиране на балончета
- Сортиране на селекцията
- Обединяване Сортиране
- пирамидално сортиране
1. Сортиране на вмъкване
Концепцията зад Insertion Sort разделя диапазона на подредовете, които са сортирани и несортирани. Класифицираната част е в началото на продължителност 1 и съвпада с първия (отляво) компонент в масива. Преминаваме през масива и разширяваме класифицираната част от масива по един компонент по време на всяка итерация. Когато разширяваме, позиционираме свежия елемент в подредения под-масив. Правим това, като преместваме всички елементи надясно, докато установим, че не е нужно да променяме първия компонент. Когато смелият дял е сортиран във възходящ ред, например в следния масив, това се случва:
- 3 5 7 8 4 2 1 9 6: Обмислете 4 и вмъкнете това е това, от което се нуждаем. Разместваме се от 8> 4
- 2. 3 5 7 x 8 2 1 9 6
- 3 5 x 7 8 2 1 9 6
- 3 x 5 7 8 2 1 9 6
- 3 4 5 7 8 2 1 9 6
Код:
public class InsertionSortEx (
public static void insertionSort(int() arr) (
for (int x = 1; x < arr.length; x++) (
int current = arr(x);
int y = x - 1;
while(y >= 0 && current < arr(y)) (
arr(y+1) = arr(y);
y--;
)
arr(y+1) = current;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 7, 8, 4, 2, 1, 9, 6);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
insertionSort(arr1);//sorting array using insertion sort
System.out.println("After Insertion Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)
изход:
Следвайки този метод, един компонент разшири подредената част, сега имаме пет вместо четири елемента. Всяка итерация прави това и целият масив ще бъде сортиран до края.
Забележка: Това е така, защото трябва да прехвърлим целия класифициран списък един по един във всяка итерация, която е O (n). За всеки компонент във всяка таблица трябва да направим това, което означава, че е ограничен O (n 2).2. Сортиране на балончета
Ако балонът не е в необходимия ред, той работи, като заменя съседните компоненти. Това се повтаря, докато всички компоненти са в ред от началото на масива. Знаем, че ако успеем да извършим цялата итерация без суапове, всички елементи в сравнение със съседните им елементи бяха в желания ред и, като разширение, целия масив. Причината за алгоритъма за сортиране на балончета е, че числата като „балончета нагоре“ в „земята“. Ако след определена сума отново преминете през инстанцията (4 е добър инстанция), ще забележите, че числото бавно се движи вдясно.
Стъпки за сортиране на балончета са следните:
- 4 2 1 5 3: Тук, първите две числа не са в правилния ред, следователно трябва да сортираме и двете числа.
- 2 4 1 5 3: След това следващата двойка номер също не е в правилния ред. Така сортирането става отново.
- 2 1 4 5 3: Тези две са в правилния ред, 4 <5, следователно няма нужда да ги разменяте.
- 2 1 4 5 3 : Отново трябва да сменим за правилна поръчка.
- 2 1 4 3 5: Ето получения масив след една итерация.
- Трябва да повторим този процес отново, докато числата са в правилен ред.
Код:
public class BubbleSortExample (
public static void bubbleSort(int() arr) (
int n = arr.length;
int tmp = 0;
for(int x=0; x < n; x++)(
for(int y=1; y < (nx); y++)(
if(arr(y-1) > arr(y))(
//swap elements
tmp = arr(y-1);
arr(y-1) = arr(y);
arr(y) = tmp;
)
)
)
)
public static void main(String() args) (
int arr() =(4, 2, 1, 5, 3);
System.out.println("Array Before Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
System.out.println();
bubbleSort(arr);
System.out.println("Array After Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
)
)
изход:
3. Сортиране на селекцията
Selection Sort разделя масива на масив от класификации, които не са сортирани. Този път, обаче, подредбата за сортиране се формира чрез вмъкване в края на сортирания масив минималния елемент на несортираното подребрие чрез размяна:
- 3 5 1 2 4
- 1 5 3 2 4
- 1 2 3 5 4
- 1 2 3 5 4
- 1 2 3 4 5
- 1 2 3 4 5
Код:
public class SelectionSortEx (
public static void selectionSort(int() arr)(
for (int x = 0; x < arr.length - 1; x++)
(
int indx = x;
for (int y = x + 1; y < arr.length; y++)(
if (arr(y) < arr(indx))(
indx = y;
)
)
int smallNumber = arr(indx);
arr(indx) = arr(x);
arr(x) = smallNumber;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 1, 2, 4);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
selectionSort(arr1);
System.out.println("After Selection Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)
изход:
4. Сливане на сортиране
Merge Sort използва рекурсия, за да реши проблема с метода на разделяне и завладяване по-ефективно от по-рано описаните алгоритми.
Това дърво показва как функционират рекурсивните повиквания. Маркираните със стрелка надолу масиви са масивите, за които ние наричаме функция, докато обединяваме стреловите масиви. След това следвате стрелката до ръба на дървото и след това се връщате и се сливате. Имаме 3 5 3 1 обхват, така че го разделихме на 3 5 4 и 2 1. Разделихме ги на техните части, за да ги сортираме. Започваме да ги слеем и да ги сортираме, докато вървим към дъното.
Код:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class MergeSort (
static void merge(int() array, int lowval, int midval, int highval)(
int x, y, k;
int() c= new int(highval-lowval+1);
k = 0;
x=lowval;
y=midval+1;
while(x<=midval && y<=highval)(
if(array(x)<=array(y))(
c(k++) = array(x++);
)
else(
c(k++) = array(y++);
)
)
while(x<=midval)(
c(k++) = array(x++);
)
while(y<=highval)(
c(k++) = array(y++);
)
k=0;
for(x = lowval; x<=highval; x++)(
array(x) = c(k++);
)
)
static void mergeSort(int() array, int lowval, int highval)(
if(highval-lowval+1>1)(
int midval = (lowval+highval)/2;
mergeSort(array, lowval, midval);
mergeSort(array, midval+1, highval);
merge(array, lowval, midval, highval);
)
)
public static void main(String() args) (
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
int size;
System.out.println("Enter the array");
try (
size = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("Please Enter valid Input");
return;
)
int() array = new int(size);
System.out.println("Enter array elements");
int x;
for (x = 0; x < array.length; x++) (
try (
array(x) = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("An error Occurred");
)
)
System.out.println("After Sorting");
System.out.println(Arrays.toString(array));
mergeSort(array, 0, array.length-1);
System.out.println("Before Merge Sorting");
System.out.println(Arrays.toString(array));
)
)
В тази програма сме помолили потребителя да въведе информация. Изходът ще бъде подреден в зависимост от данните на потребителя.
изход:
5. Heap Sort
Първо трябва да знаете рамката, върху която оперира Heapsort - грамадата, за да разберете защо работи. Специално ще говорим за бинарна купчина, но можете да обобщите това и за други конструкции на купчина. Купа е дърво, което изпълнява свойството на купчината, а именно, че всичките му деца имат отношения към всеки възел. Купа също трябва да бъде почти завършена. Двоичният код на почти пълна дълбочина има d-1 поддърво, със същия корен и всеки възел има пълно, ляво под-дърво, с ляво низходящо.
С други думи, вие получавате по-ниско и по-ниско число (min-heap) или по-голямо и по-голямо (max-heap) при движение надолу по дървото. Ето екземпляр с max-heap:
- 6 1 8 3 5 2 4 : Ето, номерата на двете деца са по-малки от родителските, следователно не е необходимо да променяме нищо.
- 6 1 8 3 5 2 4: Ето, 5> 1, трябва да ги разменим. Необходимо е да натрупаме 5.
- 6 5 8 3 1 2 4: И двете номера на децата са по-малки, всичко остава едно и също.
- 6 5 8 3 1 2 4: Ето, 8> 6, следователно трябва да ги разменим.
- 8 5 6 3 1 2 4: След тази итерация ще получим този резултат.
След като повторим този процес отново, ще получим следните резултати:
- 8 5 6 3 1 2 4
- 4 5 6 3 1 2 8 : Размяна
- 6 5 4 3 1 2 8 : Надуйте
- 2 5 4 3 1 6 8 : Размяна
- 5 2 4 2 1 6 8 : Надуйте
- 1 2 4 2 5 6 8 : Размяна
Код:
public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
)public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
)
изход:
Можете да го видите от точка до ниво на графиката, отляво надясно. Това, което постигнахме тук, е, че когато имаме kth компонент в масива, позицията на неговите деца е 2 \ * k + 1 и 2 \ * k + 2 (ако приемем, че индексирането започва от 0). Това може да се наблюдава от вас. Позицията на родителя е винаги (k-1) / 2 за kth компонента. Можете лесно да „увеличите максимално“ всяка гама, защото знаете това. Проверете дали едно от децата му е по-ниско от това за всеки компонент. Ако е така, сдвойте един родител и повторете тази стъпка рекурсивно с родителя.
Забележка: Тъй като повторението за цикли през целия масив прави heapSort) (очевидно O (N), това би създало общата сложност на Heapsort O (nlog n). Heapsort има тип на място, което означава, че изисква O ( 1) повече място в сравнение с Merge Sort, но има някои недостатъци, като твърди паралели.Заключение - сортиране на алгоритми в Java
Сортирането е много разпространена процедура с набори от данни, независимо дали за по-нататъшен анализ, ускоряване на търсенето с по-ефективни алгоритми, разчитащи на сортирана информация, филтриране на информация и др. Сортирането се одобрява от няколко езика и често интерфейсите затъмняват какво прави програмистът.
Препоръчителни статии
Това е ръководство за сортиране на алгоритми в Java. Тук обсъждаме различни видове сортиране в Java, заедно с техните алгоритми. Можете да разгледате и другите ни предложени статии -
- Обединяване на алгоритми за сортиране в Java
- JComboBox на Java
- StringBuffer в Java
- JTextField в Java
- Сортиране на купи в Python
- Бързо сортиране на алгоритми в Java
- Пълно ръководство за сортиране в C # с примери
- Сортиране на алгоритми в JavaScript
- Ръководство за примери на алгоритъм C ++
- Пълно ръководство за сортиране на алгоритми в Python