insertion sort java insertion sort algorithm examples
Този урок обяснява сортирането при вмъкване в Java, включително неговия алгоритъм, псевдокод и примери за сортиране на масиви, списък с единично свързване и двойно свързване:
Техниката на алгоритъма за сортиране на вмъкване е подобна на сортирането на балончета, но е малко по-ефективна. Сортирането на вмъкването е по-осъществимо и ефективно, когато е включен малък брой елементи. Когато наборът от данни е по-голям, ще отнеме повече време за сортиране на данните.
=> Погледнете тук ръководството за начинаещи Java.
как да стартирам .swf
Какво ще научите:
- Въведение в сортирането по вмъкване в Java
- Алгоритъм за сортиране при вмъкване
- Псевдокод за сортиране при вмъкване
- Сортиране на масив с помощта на сортиране по вмъкване
- Внедряване на сортиране по вмъкване в Java
- Сортиране на свързан списък с помощта на сортиране по вмъкване
- Сортиране на двойно свързан списък с помощта на сортиране по вмъкване
- често задавани въпроси
- Заключение
Въведение в сортирането по вмъкване в Java
В техниката за сортиране на вмъкване приемаме, че първият елемент в списъка вече е сортиран и започваме с втория елемент. Вторият елемент се сравнява с първия и се разменя, ако не е в ред. Този процес се повтаря за всички следващи елементи.
Като цяло, техниката за сортиране на вмъкване сравнява всеки елемент с всички предишни елементи и сортира елемента, за да го постави в правилното му положение.
Както вече споменахме, техниката за сортиране на вмъкване е по-осъществима за по-малък набор от данни и по този начин масиви с малък брой елементи могат да бъдат сортирани с помощта на ефективно сортиране на вмъкване.
Сортирането по вмъкване е особено полезно при сортиране на свързани структури от данни на списъка. Както знаете, свързаните списъци имат указатели, сочещи към следващия му елемент (единично свързан списък) и предишния елемент (двойно свързан списък). Това улеснява проследяването на предишните и следващите елементи.
По този начин е по-лесно да използвате Insertion sort за сортиране на свързани списъци. Сортирането обаче ще отнеме много време, ако елементите от данни са повече.
В този урок ще обсъдим техниката за сортиране на вмъкване, включително нейния алгоритъм, псевдокод и примери. Също така ще приложим Java програми за сортиране на масив, единично свързан списък и двойно свързан списък, като използваме Insertion sort.
Алгоритъм за сортиране при вмъкване
Алгоритъмът за сортиране на вмъкването е както следва.
Етап 1 : Повторете стъпки 2 до 5 за K = 1 до N-1
Стъпка 2 : задайте temp = A [K]
Стъпка 3 : задайте J = K - 1
Стъпка 4 :
Повторете, докато темп<=A[J]
задайте A [J + 1] = A [J]
задайте J = J - 1
[край на вътрешния цикъл]
Стъпка 5 :
задайте A [J + 1] = темп
[край на цикъла]
Стъпка 6 : изход
Както знаете, сортирането при вмъкване започва от втория елемент, като се приема, че първият елемент вече е сортиран. Горните стъпки се повтарят за всички елементи в списъка от втория елемент нататък и се поставят в желаните им позиции.
Псевдокод за сортиране при вмъкване
Псевдокодът за техниката за сортиране на вмъкване е даден по-долу.
procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array[i] freePosition = i //locate free position to insert the element while freePosition > 0 and array[freePosition -1] > insert_val do: array [freePosition] = array [freePosition -1] freePosition = freePosition -1 end while //insert the number at free position array [freePosition] = insert_val end for end procedure
След това нека видим илюстрация, която демонстрира сортиране на масив с помощта на Insertion sort.
Сортиране на масив с помощта на сортиране по вмъкване
Нека вземем пример за сортиране с вмъкване с помощта на масив.
Масивът за сортиране е както следва:
Сега за всеки проход сравняваме текущия елемент с всички предишни елементи. Така че при първото преминаване започваме с втория елемент.
По този начин, ние изискваме N брой проходи, за да сортираме напълно масив, съдържащ N брой елементи.
Горната илюстрация може да бъде обобщена в таблична форма, както е показано по-долу:
разлика между изпитването на дим и здравословното състояние
Подайте | Несортиран списък | сравнение | Сортиран списък |
---|---|---|---|
1 | {10,2,6,15,4,1} | {10.2} | {2,10, 6,15,4,1} |
две | {2,10, 6,15,4,1} | {2,10, 6} | {2,6,10,15,4,1} |
3 | {2,6,10,15,4,1} | {2.6, 10.15} | {2,6,10,15,4,1} |
4 | {2,6,10,15,4,1} | {2.6, 10.15.4} | {2,4,6,10,15,1} |
5 | {2,4,6,10,15,1} | {2,4,6,10,15,1} | {1,2,4,6, 10,15} |
6 | {} | {} | {1,2,4,6, 10,15} |
Както е показано на илюстрацията по-горе, в края на всеки проход, един елемент отива на правилното си място. Следователно като цяло, за да поставим N елемента на правилното им място, ни трябват пропуски N-1.
Внедряване на сортиране по вмъкване в Java
Следващата програма показва изпълнението на сортирането на вмъкване в Java. Тук имаме масив, който трябва да бъде сортиран с помощта на сортирането Insertion.
import java.util.*; public class Main { public static void main(String[] args) { //declare an array and print the original contents int[] numArray = {10,6,15,4,1,45}; System.out.println('Original Array:' + Arrays.toString(numArray)); //apply insertion sort algorithm on the array for(int k=1; k=0 && temp <= numArray[j]) { numArray[j+1] = numArray[j]; j = j-1; } numArray[j+1] = temp; } //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(numArray)); } }
Изход:
Оригинален масив: [10, 6, 15, 4, 1, 45]
Сортиран масив: [1, 4, 6, 10, 15, 45]
В горното изпълнение се вижда, че сортирането започва от 2ndелемент на масива (циклична променлива j = 1) и след това текущият елемент се сравнява с всички негови предишни елементи. След това елементът се поставя в правилното му положение.
Сортирането с вмъкване работи ефективно за по-малки масиви и за масиви, които са частично сортирани, когато сортирането е завършено за по-малко проходи.
Сортирането по вмъкване е стабилно сортиране, т.е. поддържа реда на равни елементи в списъка.
Сортиране на свързан списък с помощта на сортиране по вмъкване
Следващата програма на Java показва сортирането на единично свързан списък с помощта на сортирането на вмъкване.
import java.util.*; class Linkedlist_sort { node head; node sorted; //define node of a linked list class node { int val; node next; public node(int val) { this.val = val; } } //add a node to the linked list void add(int val) { //allocate a new node node newNode = new node(val); //link new node to list newNode.next = head; //head points to new node head = newNode; } // sort a singly linked list using insertion sort void insertion_Sort(node headref) { // initially, no nodes in sorted list so its set to null sorted = null; node current = headref; // traverse the linked list and add sorted node to sorted list while (current != null) { // Store current.next in next node next = current.next; // current node goes in sorted list Insert_sorted(current); // now next becomes current current = next; } // update head to point to linked list head = sorted; } //insert a new node in sorted list void Insert_sorted(node newNode) { //for head node if (sorted == null || sorted.val >= newNode.val) { newNode.next = sorted; sorted = newNode; } else { node current = sorted; //find the node and then insert while (current.next != null && current.next.val Изход:
Оригинален свързан списък:
1 8 32 2 10
Сортиран свързан списък:
1 2 8 10 32

В горната програма дефинирахме клас, който създава свързан списък и добавя възли към него, както и го сортира. Тъй като единично свързаният списък има следващ указател, по-лесно е да се следи възлите при сортиране на списъка.
Сортиране на двойно свързан списък с помощта на сортиране по вмъкване
Следващата програма сортира двойно свързан списък с помощта на Insertion sort. Имайте предвид, че тъй като двойно свързаният списък има както предишни, така и следващи указатели, лесно е да се актуализират и свържат отново указателите, докато сортирате данните.
class Main { // doubly linked list node static class Node { int data; Node prev, next; }; // return a new node in DLL static Node getNode(int data){ //create new node Node newNode = new Node(); // assign data to node newNode.data = data; newNode.prev = newNode.next = null; return newNode; } // insert a node in sorted DLL static Node insert_Sorted(Node head_ref, Node newNode) { Node current; //list is empty if (head_ref == null) head_ref = newNode; // node is inserted at the beginning of the DLL else if ((head_ref).data >= newNode.data) { newNode.next = head_ref; newNode.next.prev = newNode; head_ref = newNode; } else { current = head_ref; // find the node after which new node is to be inserted while (current.next != null && current.next.data prev points to new node / if ((head_ref) != null) (head_ref).prev = newNode; // move the head to point to the new node / (head_ref) = newNode; return head_ref; } public static void main(String args[]) { // create empty DLL Node head = null; // add nodes to the DLL head=addNode(head, 5); head=addNode(head, 3); head=addNode(head, 7); head=addNode(head, 2); head=addNode(head, 11); head=addNode(head, 1); System.out.println( 'Original doubly linked list:'); print_DLL(head); head=insertion_Sort(head); System.out.println('
Sorted Doubly Linked List:'); print_DLL(head); } }
Изход:
Оригинален двойно свързан списък:
1 11 2 7 3 5
Сортиран двойно свързан списък:
1 2 3 5 7 11

често задавани въпроси
В # 1) Какво представлява сортирането при вмъкване в Java?
Отговор: Сортирането по вмъкване е проста техника за сортиране в Java, която е ефективна за по-малък набор от данни и на място. Предполага се, че първият елемент винаги се сортира и след това всеки следващ елемент се сравнява с всички предишни елементи и се поставя в правилното му положение.
Q # 2) Защо вмъкването е по-добро?
Отговор: Сортирането с вмъкване е по-бързо за по-малки набори от данни, когато другите техники като бързото сортиране добавят режийни чрез рекурсивни повиквания. Сортирането при вмъкване е сравнително по-стабилно от другите алгоритми за сортиране и изисква по-малко памет. Сортирането по вмъкване работи и по-ефективно, когато масивът е почти сортиран.
Q # 3) За какво се използва сортирането за вмъкване?
Отговор: Сортирането при вмъкване се използва най-вече в компютърни приложения, които изграждат сложни програми като търсене на файлове, намиране на пътеки и компресиране на данни.
Q # 4)Каква е ефективността на Insertion Sort?
Отговор: Сортирането при вмъкване има средно представяне на случая на O (n ^ 2). Най-добрият случай за сортиране на вмъкване е, когато масивът вече е сортиран и е O (n). Най-лошият резултат за сортиране при вмъкване отново е O (n ^ 2).
Заключение
Сортирането по вмъкване е проста техника за сортиране, която работи върху масиви или свързани списъци. Полезно е, когато наборът от данни е по-малък. С увеличаването на набора от данни тази техника става по-бавна и неефективна.
Сортирането по вмъкване също е по-стабилно и на място от другите техники за сортиране. Няма допълнителна памет, тъй като не се използва отделна структура за съхранение на сортирани елементи.
най-добрия софтуер за извличане на DVD за
Сортирането по вмъкване работи добре при сортиране на свързани списъци, които са едновременно и двойно свързани списъци. Това е така, защото свързаният списък се състои от възли, които са свързани чрез указатели. Следователно сортирането на възлите става по-лесно.
В нашия предстоящ урок ще обсъдим още една техника за сортиране в Java.
=> Прочетете серията Easy Training Training.
Препоръчително четене
- Сортиране на селекция в Java - Алгоритъм за сортиране на селекция и примери
- Сортиране по вмъкване в C ++ с примери
- Как да сортираме масив в Java - Урок с примери
- Метод за сортиране на MongoDB () с примери
- Команда за сортиране на Unix със синтаксис, опции и примери
- Сортиране на черупката в C ++ с примери
- Урок за интерфейс на Java и абстрактен клас с примери
- Сортиране на избора в C ++ с примери