Сортирането на масиви е една от най-често срещаните операции, които начинаещият в Java трябва да знае How да прави. Въпреки че масивите не винаги са най-удобният начин за подреждане на данни и това се отнася най-вече за малки числа, концепцията зад сортирането на масиви има много applications в сложния софтуер и науката за данни. В тази публикация ще разгледаме по-подробно Howво представлява сортирането на вмъкване. Включихме някои примери и практически задачи, за да ви помогнем да разберете напълно тази концепция.
Какво е сортиране чрез вмъкване?
По принцип сортирането чрез вмъкване е алгоритъм, който разработчиците използват за организиране на низове от малки числа. Той разделя всички стойности на два стека - сортиран и несортиран. Едно по едно, числата в „несортирания“ стек се избират и подреждат в правилния ред. Нека разгледаме по-подробно входа и изхода на сортирането чрез вмъкване:
Вход: масив A с несортирани числови елементи: A[0,1, n, n-2...].
Изход: масив, съдържащ същите числа, но напълно сортирани. Това обикновено се нарича B: B[0]B[1]...B[n-1].
Има няколко начина за използване на сортиране чрез вмъкване - ето най-популярните:
Числово сортиране (в низходящ ред): [5, 4, 3, 2, 1]
Сортиране по азбучен ред: [a, b, c, d]
Забележка: ако имате празен масив or сингълтон, те се считат за сортирани по подразбиране.
Разбиране на теорията за сортиране чрез вмъкване
Преди да проучим codeа зад сортирането чрез вмъкване, нека разбием алгоритъма, използвайки нетехнически език. Тъй като ще покажем codeа за сортиране във възходящ ред, има смисъл да обясним алгоритъма стъпка по стъпка в тази публикация. Стъпка 1. Повторение между arr[1]и arr[n]къде nе числова стойност, обикновено по-малка от 10. Стъпка 2. Сравнете елемента, който сте избрали (известен като key) с предишното число в последователността, като използвате sort()метода. Стъпка 3. Ако всички елементи са по-малки от своите наследници, повторете сравнението, докато намерите по-голяма стойност. Стъпка 4. Разменете по-голяма стойност една позиция след по-малката, за да създадете подредена последователност. Стъпка 5. Повторете процеса, докато получите сортиран низ от знаци
Сортиране на примитивни масиви
Тъй като алгоритъмът е една от най-простите операции на Java, дори напълно начинаещите не би трябвало да имат много проблеми с прилагането му. Ето ръководство стъпка по стъпка за сортиране на масив
1. Декларирайте масив за сортиране
Като начало, нека създадем низ от стойности, които по-късно ще покажем с помощта на Java. За да използвате сортиране чрез вмъкване, трябва да създадете масив. За това използвайтеint[]
int[] arrayA = {10, 14, 20, 30};
2. Използвайте sort_arr, за да приложите алгоритъма
Методът sort_arr е един от най-често срещаните начини за прилагане на сортиране чрез вмъкване. На практика това изглежда така:
for(int i=0; i< sort_arr.length; ++i){
int j = i;
3. Създайте цикъл и итератор
Чрез използването на цикъл в алгоритъма за сортиране при вмъкване, разработчиците не трябва да повтарят логиката за всеки елемент. Въпреки че създаването на цикли изглежда сложно, то е доста просто - ето един пример:
for(int i=0; i< sort_arr.length; ++i){
Сега, когато имате функциониращ цикъл, е време да създадете итератор, който ще сортира всички елементи в желания ред. Отсега нататък ще наричаме итератора „ j“.
int j = i;
4. Създаване на "while цикъл"
Когато става въпрос за сортиране чрез вмъкване, цикълът "while" е от съществено meaning за нов, сортиран масив. За да го настрои за сортиране на вмъкване във възходящ ред, разработчикът трябва да спазва две условия:
Стойността, присвоена на j, трябва да бъде по-голяма от 0
Стойността, присвоена на j-1трябва да е по-голяма от jиндекса
Веднага след като и двете условия в цикъла while са верни, ключовата стойност на масива ще се изравни с индекса j.
5. Сортиране на масива
След като настроите цикъла while, стойностите на jи j-1ще се разменят, докато едното or и двете условия в цикъла while се провалят. По същия начин, сортирането ще се повтаря за всяка стойност в for цикъла, докато условията на for цикъл също се провалят. Ето How работи на практика процесът на сортиране чрез вмъкване:
Въпреки че разбирането на математиката зад сортирането при вмъкване е важно, когато става въпрос за разработка на софтуер в реалния живот, вие ще сортирате ArrayLists много повече от последователности в примитивни масиви. Ето ръководство стъпка по стъпка за сортиране на ArrayList:
Създайте нов Elementклас за елементите, които принадлежат към колекцията.
public class Element {
private int id;
public Element(int id) {
this.id = id;
}
В колекцията има compareTo()метод - ще го използваме, за да сравним идентификаторите на два елемента.
public int compareTo(Element element) {
int res = 0;
if (this.id < element.getId()) {
res = -1;
}
if (this.id > element.getId()) {
res = 1;
}
return res;
}
}
Приложете алгоритъма и създайте няколко цикъла, за да сортирате обектите в ArrayListinstead of да ги сравнявате.
public static void insertionSortArrayList(List<element> list) {
for (int j = 1; j < list.size(); j++) {
Element current = list.get(j);
int i = j-1;
while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
list.set(i+1, list.get(i));
i--;
}
list.set(i+1, current);
}
}
Можете да добавите още елементи към ArrayList, Howто е показано по-долу:
List<element> list = new ArrayList<>();
// Create elements w/ IDs 0-24
for (int i = 0; i < 25; i++) {
list.add(new Element(i));
}
// To use insertion sort, shuffle the values
Collections.shuffle(list);
Сега е време за сортиране:
// This helps print values before sorting
list.forEach(e -> System.out.print(e.getId() + ", "));
// Sort the list
insertionSortArrayList(list);
System.out.println();
// Display a sorted array
list.forEach(e -> System.out.print(e.getId() + ", "));
Сега нека сравним входа и изхода, за да сме сигурни, че нямаме грешки. Ето сравнението на низа, който използвахме като пример.
Сега, след като се справихте с този алгоритъм за сортиране, е време да подложите теоретичните и практическите си умения на изпитание. Теоретичен тест #1 Даден ви е масив [1, 4, 6, 8] и добавяте нов елемент n = 7 към него. Какъв е броят сравнения, които трябва да направите, за да получите сортирана последователност от числа? Посочете крайната стойност на индекс n в масива. Теоретичен тест №2 На интервю за работа ръководител на екип ви моли да докажете, че вмъкването на сортиране е неефективен метод. При даден цифров низ от [0, 3, 6, 8, 9], Howъв трябва да бъде редът на вашата входна последователност, за да увеличите максимално времето за изпълнение, необходимо за сортиране? Практически проблем Сортирайте масива [0, 1, 4, 5, 2, 3, 7, 9, 8] във възходящ ред, като използвате сортиране чрез вмъкване за Java.
Заключение
Най-голямото предизвикателство при разбирането на сортирането на вмъкване е в разбирането How работи процесът. След като го овладеете, превръщането на шаблона в code е лесно. Докато практикувате и преразглеждате съответните практически проблеми с течение на времето, бързо ще подобрите скоростта на сортиране при вмъкване.
Нека разгледаме по-подробно входа и изхода на сортирането чрез вмъкване:
GO TO FULL VERSION