Меню

Сортиране при вмъкване в Java - Алгоритъм за сортиране при вмъкване и примери

  • Основен
  • Други
  • Сортиране при вмъкване в Java - Алгоритъм за сортиране при вмъкване и примери

insertion sort java insertion sort algorithm examples

Опитайте Нашия Инструмент За Премахване На Проблемите

Този урок обяснява сортирането при вмъкване в Java, включително неговия алгоритъм, псевдокод и примери за сортиране на масиви, списък с единично свързване и двойно свързване:

Техниката на алгоритъма за сортиране на вмъкване е подобна на сортирането на балончета, но е малко по-ефективна. Сортирането на вмъкването е по-осъществимо и ефективно, когато е включен малък брой елементи. Когато наборът от данни е по-голям, ще отнеме повече време за сортиране на данните.

=> Погледнете тук ръководството за начинаещи Java.

как да стартирам .swf

Сортиране на вмъкване в 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.

Сортиране на масив с помощта на сортиране по вмъкване

Нека вземем пример за сортиране с вмъкване с помощта на масив.

Масивът за сортиране е както следва:

масив за сортиране

Сега за всеки проход сравняваме текущия елемент с всички предишни елементи. Така че при първото преминаване започваме с втория елемент.

Сравнете 2-ри елемент с 1-ви елемент

преминете 2

преминете 3

пас 4

преминете 5

преминете 6

По този начин, ние изискваме 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.

Препоръчително четене

^