selection sort java selection sort algorithm examples
Този урок ще обясни всичко за сортирането на избора в Java заедно с алгоритъма за сортиране на избора, Java кода, внедряването в Java и примери за Java:
Техниката за сортиране на селекция е метод, при който най-малкият елемент в масива се избира и разменя с първия елемент на масива. След това вторият най-малък елемент в масива се обменя с втория елемент и обратно.
=> Проверете тук, за да видите A-Z на уроците за обучение по Java тук.
Какво ще научите:
Сортиране на избора в Java
По този начин най-малкият елемент в масива се избира многократно и се поставя в правилното му положение, докато целият масив не бъде сортиран.
Два под-масива се поддържат за сортиране на подбора:
- Сортиран подмасив: Във всяка итерация минималният елемент се намира и поставя в правилното му положение. Този подмасив е сортиран.
- Несортиран подмасив: Останалите елементи, които не са сортирани.
Сортирането на селекцията е проста и лесна техника за сортиране. Техниката включва само намиране на най-малкия елемент при всеки пас и поставянето му в правилната позиция. Сортирането на селекцията е идеално за по-малки набори от данни, тъй като ефективно сортира по-малкия набор от данни.
По този начин можем да кажем, че сортирането на подбор не е препоръчително за по-големи списъци с данни.
Алгоритъм за сортиране на избора
Общият алгоритъм за сортиране на подбора е даден по-долу:
Сортиране на избора (A, N)
Етап 1 : Повторете стъпки 2 и 3 за K = 1 до N-1
Стъпка 2 : Повикване на рутина най-малко (A, K, N, POS)
Стъпка 3 :
Разменете A (K) с A (POS)
(Край на цикъла)
Стъпка 4 : EXIT
Рутинни най-малки (A, K, N, POS)
Етап 1 : (инициализиране) задаване на най-малък елемент = A (K)
Стъпка 2 : (инициализиране) задайте POS = K
Стъпка 3 :
за J = K + 1 до N -1, повторете
ако е най-малъкItem> A (J)
задайте най-малъкItem = A (J)
задайте POS = J
(ако край)
(Край на цикъла)
Стъпка 4 : връщане на POS
Както можете да видите, рутината за намиране на най-малкото число се извиква, докато обхождате набора от данни. След като бъде намерен най-малкият елемент, той се поставя в желаното от него положение.
как да отворите xml файл в браузъра -
Псевдокод за сортиране по избор
Псевдокодът за алгоритъма за сортиране на избора е даден по-долу.
Procedure selection_sort(array,N) array – array of items to be sorted N – size of array begin for I = 1 to N-1 begin set min = i for j = i+1 to N begin if array(j) Нека сега илюстрираме сортирането на масив, използвайки сортиране на селекция.
Пример за сортиране на селекцията
Помислете за следния масив, който трябва да бъде сортиран като пример за сортиране на селекция.
По-долу е представено таблично представяне за илюстрацията:
Несортиран списък Най-малко елемент Сортиран списък {17,10,7,29,2} две {} {17,10,7,29} 7 {две} {17,10,29} 10 {2.7} {17.29} 17 {2,7,10) {29} 29 {2,7,10,17} {} {2,7,10,17,29}
От илюстрацията виждаме, че при всяко преминаване следващият най-малък елемент се поставя в правилното си положение в сортирания масив. Като цяло, за да сортираме масив от N елемента, ни трябват общо N-1 преминавания.
Изпълнение на сортиране по избор в Java
Нека сега демонстрираме програмата Java за реализиране на сортиране на селекцията.
import java.util.*; class Main { static void sel_sort(int numArray()) { int n = numArray.length; // traverse unsorted array for (int i = 0; i Изход:
Оригинален масив: (7, 5, 2, 20, 42, 15, 23, 34, 10)
Сортиран масив: (2, 5, 7, 10, 15, 20, 23, 34, 42)
В горния пример за java многократно намираме най-малкия елемент в масива и го поставяме в сортирания масив, докато целият масив бъде напълно сортиран.
Избор Сортиране на свързан списък в Java
Даден по-долу е свързан списък и ние трябва да го сортираме с помощта на сортиране по избор. За целта ще използваме рекурсивния подход на сортиране на селекцията. Вместо да разменяме частта с данни на възела, ние ще разменяме възлите и ще пренасочваме указателите.
Така че, ако свързаният списък е даден по следния начин:
По-долу е дадена програмата Java, която реализира горното сортиране.
// add a node to the beginning of the linked list static Node addNode( Node head_ref, int new_data) { // create a node Node newNode = new Node(); // assign data to node newNode.data = new_data; // link the node to linked list newNode.next = (head_ref); //head now points to new node (head_ref) = newNode; return head_ref; } // method to swap nodes static Node swapNodes( Node head_ref, Node curr_node1, Node curr_node2, Node prev_node) { // curr_node2 is new head head_ref = curr_node2; // realign links prev_node.next = curr_node1; // now swap next pointers of nodes Node temp = curr_node2.next; curr_node2.next = curr_node1.next; curr_node1.next = temp; return head_ref; } // sort the linked list using selection sort static Node Selection_Sort( Node head) { // only a single node in linked list if (head.next == null) return head; // minNode => node with minimum data value Node minNode = head; // prevMin => node previous to minNode Node prevMin = null; Node ptr; // traverse the list from head to last node for (ptr = head; ptr.next != null; ptr = ptr.next) { // check if current node is minimum if (ptr.next.data Изход:
Оригинален свързан списък:
7 9 3 5 1 11
Свързан списък след сортиране:
1 3 5 7 9 11
Имайте предвид, че в горната програма сме пренаредили връзките на възлите, вместо да сортираме само компонента за данни на възела.
често задавани въпроси
В # 1) Как работи сортирането на подбора?
Отговор: Сортирането по избор работи чрез поддържане на два под-масива. Минималният елемент от несортирания подмасив се поставя в правилното му положение в сортиран подмасив. След това вторият най-нисък елемент се поставя в правилното му положение. По този начин целият масив се сортира чрез избиране на минимален елемент по време на всяка итерация.
Q # 2) Каква е сложността на сортирането на селекцията?
Отговор: Цялостната сложност на сортирането на подбора е O (nдве), като по този начин го прави алгоритъм, който е неефективен при по-големи масиви от данни. Други техники за сортиране са по-ефективни.
Q # 3) Какви са предимствата и недостатъците на сортирането на селекцията?
Отговор: Сортирането по избор е техниката за сортиране на място и по този начин не се изисква допълнително съхранение за съхранение на междинни елементи.
Той работи ефективно върху по-малки структури от данни, както и на масиви от данни, които са почти сортирани.
Основният недостатък на техниката за сортиране на подбора е, че тя се представя много лошо, тъй като размерът на структурата на данните се увеличава. Той не само става по-бавен, но и намалява ефективността.
Q # 4) Колко суапа има в сортирането на селекцията?
Отговор: Техниката за сортиране на подбора отнема минималния брой суапове. За най-добрия случай, когато масивът е сортиран, броят на суаповете в сортирането на селекцията е 0.
Q # 5) Сортирането по избор ли е по-бързо от сортирането при вмъкване?
Отговор: Сортирането при вмъкване е по-бързо и по-ефективно, както и стабилно. Сортирането на селекцията е по-бързо само за по-малки набори от данни и частично сортирани структури.
Заключение
Сортирането по избор е техника, която работи чрез избиране на минималния елемент, докато обхожда масива. За всеки проход / итерация се избира следващият минимален елемент в набора от данни и се поставя в правилното му положение.
Техниката за сортиране на подбор работи ефективно, когато броят на елементите в набора от данни е по-малък, но започва да се представя слабо, тъй като размерът на набора от данни нараства. Той става неефективен в сравнение с други подобни техники като вмъкване.
кой е най-добрият безплатен изтегляне на mp3
В този урок внедрихме примери за сортиране на масиви и свързани списъци, като използваме сортиране на селекция.
=> Посетете тук, за да видите серията за обучение за Java за всички.
Препоръчително четене
- Как да сортираме масив в Java - Урок с примери
- Сортиране на избора в C ++ с примери
- Урок за дължина на масив Java с примери за кодове
- Метод за сортиране на MongoDB () с примери
- Назъбен масив в Java - урок с примери
- Команда за сортиране на Unix със синтаксис, опции и примери
- Обръщане на масив в Java - 3 метода с примери
- Урок за JAVA за начинаещи: 100+ практически ръководства за Java видео
