Сортирането на масиви е една от най-често срещаните операции, които начинаещият в Java трябва да знае How да прави. Въпреки че масивите не винаги са най-удобният начин за подреждане на данни и това се отнася най-вече за малки числа, концепцията зад сортирането на масиви има много applications в сложния софтуер и науката за данни. В тази публикация ще разгледаме по-подробно Howво представлява сортирането на вмъкване. Включихме някои примери и практически задачи, за да ви помогнем да разберете напълно тази концепция.
![Сортиране чрез вмъкване в Java - 1]()
Нека разгледаме по-подробно входа и изхода на сортирането чрез вмъкване:
Какво е сортиране чрез вмъкване?
По принцип сортирането чрез вмъкване е алгоритъм, който разработчиците използват за организиране на низове от малки числа. Той разделя всички стойности на два стека - сортиран и несортиран. Едно по едно, числата в „несортирания“ стек се избират и подреждат в правилния ред.
Нека разгледаме по-подробно входа и изхода на сортирането чрез вмъкване:
- Вход: масив A с несортирани числови елементи: A[0,1, n, n-2...].
- Изход: масив, съдържащ същите числа, но напълно сортирани. Това обикновено се нарича B: B[0]B[1]...B[n-1].
- Числово сортиране (възрастващ ред): [1, 2, 3, 4, 5]
- Числово сортиране (в низходящ ред): [5, 4, 3, 2, 1]
- Сортиране по азбучен ред: [a, b, c, d]
Разбиране на теорията за сортиране чрез вмъкване
Преди да проучим 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индекса
j.
5. Сортиране на масива
След като настроите цикъла while, стойностите наjи j-1ще се разменят, докато едното or и двете условия в цикъла while се провалят. По същия начин, сортирането ще се повтаря за всяка стойност в for цикъла, докато условията на for цикъл също се провалят. Ето How работи на практика процесът на сортиране чрез вмъкване:
int key = sort_arr[j];
sort_arr[j] = sort_arr[j-1];
sort_arr[j-1] = key;
j = j-1;
Сортиране на ArrayList
Въпреки че разбирането на математиката зад сортирането при вмъкване е важно, когато става въпрос за разработка на софтуер в реалния живот, вие ще сортирате 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() + ", ")); - Сега нека сравним входа и изхода, за да сме сигурни, че нямаме грешки. Ето сравнението на низа, който използвахме като пример.
4, 2, 6, 7, 0, 5, 9, 1, 8, 3, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
GO TO FULL VERSION