Въведение в сортирането на вмъкване в Java
Ако сте програмист, сигурно вече сте чували за сортирането много. Сортирането е основно подреждане на елементите или във възходящ ред, или в низходящ ред. Налични са толкова много алгоритми за сортиране, за да се сортират елементите и всеки алгоритъм има различни начини за сортиране, различна сложност. Така че зависи от конкретния сценарий и броя на елементите за това кой алгоритъм трябва да се използва. Вмъкването е също един от често използваните алгоритми за сортиране, които имат сложността на O (n 2) като цяло и се изпълнява така, както подреждаме игралните карти в ръцете си. В тази тема ще научим за сортирането на вмъкване в Java.
Как работи сортирането на вмъкване в Java?
Нека разберем работата на сортирането на вмъкване, като използваме пример. Да предположим, че има масив с име arr, съдържащ посочените по-долу елементи:
10 5 8 20 30 2 9 7
Стъпка # 1 - Сортирането на вмъкване започва с 2-ия елемент от масива, т.е. 5, като се има предвид първият елемент от масива, който е включен в себе си. Сега елемент 5 се сравнява с 10, тъй като 5 е по-малко от 10, така че 10 се премества с 1 позиция напред и 5 се вмъква преди него.
Сега полученият масив е:
5 10 8 20 30 2 9 7
Стъпка # 2 - Сега елементът arr (2), т.е. 8 се сравнява с елемента arr (1), т.е. 10. Тъй като 8 е по-малък от предходния му елемент 10, той се измества с една стъпка напред от позицията си и тогава е в сравнение с 5. Тъй като 8 е по-голямо от 5, така че се вмъква след него.
Тогава полученият масив е:
5 8 10 20 30 2 9 7
Стъпка # 3 - Сега елемент 20 се сравнява с 10, тъй като е по-голям от 10, той остава в своето положение.
5 8 10 20 30 2 9 7
Стъпка # 4 - Елемент 30 се сравнява с 20 и тъй като е по-голям от 20, няма да се правят промени и масивът остава такъв, какъвто е. Сега масивът ще бъде
5 8 10 20 30 2 9 7
Стъпка # 5 - Елемент 2 се сравнява с 30, тъй като е по-малък от 30, той се измества с една позиция напред, след това се сравнява с 20, 10, 8, 5, един по един и всички елементи се изместват на 1 позиция напред и 2 се вмъква преди 5.
Полученият масив е:
2 5 8 10 20 30 9 7
Стъпка # 6 - Елемент 9 се сравнява с 30, тъй като е по-малък от 30, той се сравнява с 20, 10 един по един и елементът се измества с 1 позиция напред и 9 се вмъква преди 10 и след 8. Полученият масив е:
2 5 8 9 10 20 30 7
Стъпка # 7 - Елемент 7 се сравнява с 30 и тъй като е по-малък от 30, той се сравнява с 30, 20, 10, 9, 8 и всички елементи се изместват 1 позиция напред един по един и 7 се вмъква преди 8 . Полученият масив ще стане:
2 5 7 8 9 10 20 30
По този начин всички елементи на масива се сортират, като се използва сортирането на вмъкването, като се започне сравнението с предходния елемент.
Примери за изпълнение на сортиране на вмъкване в Java
Сортиране на вмъкване в Java е прост алгоритъм за сортиране, подходящ за всички малки набори от данни.
public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)
изход:
12 15 18 21 23 52 61
Обяснение:
В горната програма за сортиране на вмъкване, функцията insertionSort () се използва за сортиране на елементите на оригиналния масив. Сортирането започва от втория елемент, тъй като първият елемент счита за сортиран сам по себе си. Така че цикълът на 'j' започва от индекс 1 на масива. 'i' е променлива проследяване на индекса непосредствено преди 'j', за да се сравни стойността. ' key 'е променливата, съдържаща стойността на текущия елемент, която трябва да бъде подредена в сортирана позиция. while () цикълът се изпълнява, ако текущата стойност е по-малка от най-лявата стойност, така че преместването на елементите може да бъде обработено и в края на вкарването на текущия елемент в правилната позиция. функцията printArray () се използва за окончателно отпечатване на сортирания масив.
1. Най-добър случай
При сортирането на вмъкване най-добрият случай би бил, когато всички елементи от масива са вече сортирани. Така че, когато всеки елемент се сравнява с най-левия му елемент, той винаги е по-голям и следователно няма да се обработва изместване и вмъкване на елементи. В този случай най-добрата сложност на случая ще бъде линейна, т.е. O (n).
2. Най-лошият случай
В горния код на сортиране на вмъкване, най-лошият случай би бил, когато масивът е в обратен ред, така че всеки път, когато елементът се сравнява с най-левия му елемент, той винаги е по-малък и след това се сравнява с всички протичащи елементи, които се провеждат и се изместват и се извършва поставяне. В този случай сложността на сортирането на вмъкване е O (n 2).
3. Среден случай
Дори в средния случай сортирането на вмъкване има сложност O (n 2), при която някои елементи не изискват изместване, докато някои елементи се изместват от позициите си и се извършва поставяне в правилната позиция.
4. Най-доброто използване
Сортирането на вмъкване е най-добре да се използва, когато размерът на масива не е много голям или трябва да се сортира само малък брой елементи, при които почти всички елементи са сортирани и трябва да се правят само някои промени. Сортирането на вмъкване е един от най-бързите алгоритми за масив с малки размери, дори по-бърз от Бързото сортиране. Всъщност quicksort използва сортиране Insertion, когато сортира малките си части от масива.
заключение
Горното обяснение ясно показва работата и изпълнението на сортирането на вмъкване в Java. И в други езици на програмиране логиката за извършване на сортиране на вмъкване остава същата само при промените в синтаксиса. Преди да внедрите алгоритъм за сортиране, е много важно да направите някакъв анализ на сценария, при който трябва да се извърши сортиране, тъй като не всеки алгоритъм за сортиране се вписва във всички сценарии.
Препоръчителни статии
Това е ръководство за сортиране на вмъкване в Java. Тук обсъждаме как работи сортирането на вмъкване в Java с примери за внедряване на сортиране на вмъкване в Java. Може да разгледате и следните статии, за да научите повече -
- Квадратни корени в Java
- BorderLayout в Java
- Обратен номер в Java
- StringBuffer в Java
- Квадратни корени в PHP
- Квадратно коренче в JavaScript
- Ръководство за Топ 6 сортиране на алгоритми в Python