Как да внедрим QuickSort в Java?

QuickSort е алгоритъм за разделяне и завладяване. В парадигмата за проектиране на алгоритъма Divide & Conquer разделяме проблемите на подзадачи рекурсивно, след това решаваме подзадачите и накрая комбинираме решенията, за да намерим крайния резултат. В тази статия ще се спрем на QuickSort In

Следните указания ще бъдат обхванати в тази статия,

• QuickSort в Java
• Функция за бързо сортиране
• Код на дяла
• QuickSort Java код

Нека да започнем!

Едно нещо, което трябва да имате предвид, докато разделяте проблемите на подпроблеми, е, че структурата на подпроблемите не се променя от първоначалния проблем.
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.
 Имате въпрос към нас? Моля, споменете го в раздела за коментари на този блог и ние ще се свържем с вас възможно най-скоро.