Въведение в Бързо сортиране в Java
Следващата статия Бързо сортиране в Java предоставя контур за алгоритъма за бързо сортиране в Java. Алгоритъмът за бързо сортиране е един от алгоритмите за сортиране, който е ефективен и подобен на алгоритъма за сортиране на сливане. Това е един от широко използваните алгоритми за целите на сортиране в реално време. Най-лошият случайна сложност на този алгоритъм е O (n 2), средната сложна времева сложност е O (n log n), а най-добрият времеви сложност е O (n log n).
Сложността на пространството, ако O (n log n) където е n, е размерът на входа. Процесът на сортиране включва разделяне на входа, рекурсивни итерации и маркиране на основен елемент за всяка рекурсия. Типът на сортиране в този алгоритъм включва сравнение на съседни елементи по итеративен начин.
Как работи бързото сортиране в Java?
Алгоритъмът за бързо сортиране може да бъде реализиран в Java чрез формиране на псевдо код с последователност от стъпки, проектирани и следвани по ефективен начин.
- Основният принцип на алгоритъма за бързо сортиране, който той работи, се основава на подхода разделяне и завладяване и е също така ефикасен алгоритъм за сортиране.
- Входният масив е разделен на подмасиви и разделението се основава на основен елемент, който е централен елемент. Под-масивите от двете страни на въртящия се елемент са основните области, където реално се извършва сортирането.
- Централният въртящ елемент е основата за разделяне на масива на два дяла, където лявата половина на елементите на масива е по-малка от въртящия елемент, а дясната половина на елементите на масива е по-голяма от въртящия елемент.
- Преди да разгледаме въртящия елемент, той може да бъде всеки от елементите на масива. Това обикновено се счита за средно или първо или последно за лесното разбиране. Елементът на въртене може да бъде произволен от всеки от елементите на масива.
- В нашия пример последният елемент от масива се счита за въртящ елемент, където разделянето на подмасиви започва от десния край на масива.
- И накрая, въртящият се елемент ще бъде в реалното си сортирано положение след приключване на процеса на сортиране, където основният процес на сортиране се намира в логиката на дяла на алгоритъма за сортиране.
- Ефективността на алгоритъма зависи от размера на подредовете и от това как са балансирани. Колкото повече подравненията са неуравновесени, толкова повече сложността във времето ще доведе до най-лоша сложност.
- Изборът на въртящи се елементи на случаен принцип води до най-добра времева сложност в много случаи, вместо да се избере конкретен начален, краен или среден индекс като опорни елементи.
Примери за внедряване на бързо сортиране в Java
Алгоритъмът QuickSort е реализиран с езика за програмиране на Java, както е показано по-долу, и изходният код е показан под кода.
- Първоначално кодът приема въвеждането чрез метода quickSortAlgo () с масива, началния индекс и крайния индекс, т.е. дължината на масива като аргументи.
- След извикване на метода quickSortAlgo (), той проверява дали първоначалният индекс е по-малък от крайния индекс и след това извиква метода arrayPartition (), за да получи стойност на въртящия елемент.
- Елементът на дяла съдържа логиката на подреждането на по-малките и по-големите елементи около въртящия елемент въз основа на стойностите на елементите.
- След получаване на индекса на шарнирния елемент след изпълнение на метода на дяла, методът quickSortAlgo () се извиква сам по себе си рекурсивно, докато всички подмасиви не бъдат разделени и сортирани напълно.
- В логиката на дяла последният елемент е присвоен като въртящ се елемент и първият елемент се сравнява с въртящия се елемент, т.е. последният, при който елементите се разменят въз основа на това дали са по-малки или по-големи.
- Този процес на рекурсия се случва, докато всички елементи на масива не бъдат разделени и сортирани, където крайният резултат е комбиниран сортиран масив.
- Елементите се разменят във вътрешността на итерацията за цикъл само в случай, че елементът е по-малък или равен на въртящия се елемент.
- След приключване на процеса на итерация, последният елемент се сменя, т.е. стойността на шарнирния елемент се премества в лявата страна, така че новите дялове се правят и същият процес се повтаря под формата на рекурсия, което води до серия от операции за сортиране на различни възможни дялове като формиране на подмасиви от дадените елементи от масива.
- Кодът по-долу може да се стартира на всеки IDE и изходът може да бъде проверен чрез промяна на стойността на масива в main () Основният метод се използва само за целите на получаване на изхода в конзолата. Като част от стандартите за кодиране на Java, основният метод може да бъде премахнат отдолу и да се създаде обект и по-долу методи да се извикат, като ги прави нестатични.
Кодова реализация на алгоритъм за бързо сортиране в Java
/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm (
public static void main(String() args) (
int() array = ( 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 );
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) (
System.out.print(ar + " ");
)
)
public static int arrayPartition(int() array, int start, int end) (
int pivot = array(end);
int i = (start - 1);
for (int ele = start; ele < end; ele++) (
if (array(ele) <= pivot) (
i++;
int swap = array(i);
array(i) = array(ele);
array(ele) = swap;
)
)
// Swapping the elements
int swap = array(i + 1);
array(i + 1) = array(end);
array(end) = swap;
return i + 1;
)
public static void quickSortAlgo(int() arrayTobeSorted, int start, int end) (
if (start < end) (
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
)
)
)
изход:
заключение
Алгоритмът за бързо сортиране е ефективен, но не много стабилен в сравнение с другите техники за сортиране. Ефективността на алгоритмите за бързо сортиране намалява в случай на по-голям брой повторени елементи, което е недостатък. Пространствената сложност е оптимизирана в този алгоритъм за бързо сортиране.
Препоръчителни статии
Това е ръководство за бързо сортиране в Java. Тук обсъждаме как работи бързо сортиране в Java заедно с пример и изпълнение на код. Можете да разгледате и другите ни предложени статии, за да научите повече -
- Сортиране в купа с Java
- Какво е бинарно дърво в Java?
- Манипулация на бит в Java
- Преглед на сортирането на сливания в JavaScript
- Преглед на бързото сортиране в JavaScript
- Сортиране на купи в Python
- Топ 6 алгоритъм за сортиране в JavaScript