QuickSort е алгоритъм за разделяне и завладяване. В парадигмата за проектиране на алгоритъма Divide & Conquer разделяме проблемите на подзадачи рекурсивно, след това решаваме подзадачите и накрая комбинираме решенията, за да намерим крайния резултат. В тази статия ще се спрем на QuickSort In
Следните указания ще бъдат обхванати в тази статия,
Нека да започнем!
Едно нещо, което трябва да имате предвид, докато разделяте проблемите на подпроблеми, е, че структурата на подпроблемите не се променя от първоначалния проблем.
Divide & Conquer алгоритъмът има 3 стъпки:
- Разделяне: Разбиване на проблема на подпроблеми
- Conquer: Рекурсивно решаване на подпроблемите
- Комбиниране: Комбиниране на решенията за получаване на крайния резултат
Съществуват различни алгоритми, базирани на парадигмата „разделяй и владей“. Бързо сортиране и обединяване са сред тях.
Въпреки че сложността на QuickSort във времето е O (n2), което е повече от много други алгоритми за сортиране като Merge Sort и Heap Sort, QuickSort е по-бърз на практика, тъй като неговият вътрешен цикъл може да бъде ефективно приложен в повечето архитектури и в повечето реални данни.
Нека поговорим за внедряването на алгоритъм за бързо сортиране. Алгоритмите Quicksort вземат pivot елемент и разделят масива около pivot елемента. Има няколко варианта на Quicksot, които зависят от начина, по който изберете елемента на въртене. Има няколко начина за избор на въртящия елемент:
- Бране на първия елемент
- Изберете последния елемент
- Избиране на случаен елемент
- Бране на средния елемент
Следващото важно нещо, което трябва да разберете, е функцията partition () в алгоритъма за бързо сортиране. Функция за разделяне, за да вземе опорен елемент, поставя го в дясно положение, премества всички елементи по-малки от шарнирния елемент вляво и всички елементи по-големи вдясно. Quicksort отнема линейно време, за да го направи.
Тогава масивът се разделя на две части от елемента pivot (т.е. елементи по-малко от pivot и елементи, по-големи от pivot) и двата масива се рекурсивно сортират с помощта на алгоритъма Quicksort.
php конвертира масива в обект
Сега, когато разбираме работата на алгоритъма QuickSort. Нека разберем как да имплементирам алгоритъма Quicksort в Java.
Бързо сортиране Функция:
/ * Функцията Quicksort се нуждае от масива да бъде сортиран с най-ниския и най-високия индекс * /
void sort (int arr [], int lowIndex, int highIndex) {// До lowIndex = highIndex if (lowIndexСега нека разгледаме кода за разделяне, за да разберем как работи.
Преграда Код
В кода за разделяне ще изберем последния елемент като въртящ елемент. Преминаваме през пълния масив (т.е. използвайки променлива j в нашия случай). Проследяваме последния най-малък елемент в масива (т.е. използвайки променлива i в нашия случай). Ако намерим някакъв елемент, по-малък от ос, преместваме суап текущия елемент a [j] с arr [i], иначе продължаваме да се движим.
int дял (int arr [], int lowIndex, int highIndex) {// Осъществяване на последния елемент като pivot int pivot = arr [highIndex] // Използване на i за проследяване на по-малки елементи от pivot int i = (lowIndex-1) за (int j = lowIndex jСлед като разбрахте функцията Quicksort & partition, нека да разгледаме бързо пълния код
sas урок по програмиране за начинаещи
Бързо сортиране Java код
клас QuickSort {// Метод на разделяне int дял (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) за (int j = lowIndex j// Метод за сортиране
сортиране на невалидни (int arr [], int lowIndex, int highIndex) {if (lowIndex// Метод за отпечатване на масив
static void printArray (int arr []) {int n = arr.length за (int i = 0 i// Основен метод
публична статична празнота main (String args []) {int arr [] = {101, 37, 68, 29, 11, 5} int n = arr.length QuickSort ob = new QuickSort () ob.sort (arr, 0, n-1) System.out.println ('сортиран масив') printArray (arr)}} Изход:
След изпълнението на горната Java програма бихте разбрали как работи QuickSort и как да го внедрите в Java.По този начин стигнахме до края на тази статия за „Quicksort в Java“. Ако искате да научите повече,вижте от Edureka, доверена компания за онлайн обучение. Курсът за обучение и сертифициране на Java J2EE и SOA на Edureka е предназначен да ви обучи както за основни, така и за разширени Java концепции, заедно с различни Java рамки като Hibernate & Spring.
Имате въпрос към нас? Моля, споменете го в раздела за коментари на този блог и ние ще се свържем с вас възможно най-скоро.