Меню

Бързо сортиране в Java - алгоритъм, илюстрация и внедряване

  • Основен
  • Други
  • Бързо сортиране в Java - алгоритъм, илюстрация и внедряване

quicksort java algorithm

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

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

Техниката за сортиране Quicksort се използва широко в софтуерните приложения. Quicksort използва стратегия за разделяне и завладяване като сортиране чрез сливане.

В алгоритъма за бърза сортировка първо се избира специален елемент, наречен „pivot“ и въпросният масив или списък се разделя на две подмножества. Разделените подмножества могат или не могат да бъдат с еднакъв размер.

=> Прочетете серията Easy Training Training.

Техника за бързо сортиране в Java

Преградите са такива, че всички елементи, по-малки от елемента на въртене, са вляво от пивота, а елементите, по-големи от пивота, са вдясно от пивота. Подпрограмата Quicksort рекурсивно сортира двата под-списъка. Quicksort работи ефективно и също така по-бързо дори за по-големи масиви или списъци.

Какво ще научите:

Quicksort дял Java

Разделянето е ключовият процес на техниката Quicksort. И така, какво е разделяне?

Като се има предвид масив A, ние избираме стойност x, наречена pivot, така че всички елементи, по-малки от x, да са преди x, а всички елементи, по-големи от x, да са след x.

Осева стойност може да бъде всяко от следните:

  • Първият елемент в масива
  • Последният елемент в масива
  • Средният елемент в масива
  • Всеки произволен елемент в масива

След това тази обобщена стойност се поставя на правилното му място в масива чрез разделяне на масива. По този начин изходът на процеса на ‘разделяне’ е стойността на въртене в правилната му позиция и елементите, по-малки от въртене вляво и елементи, по-големи от въртене вдясно.

Обмислете следната диаграма, която обяснява процеса на разделяне.

процес на разделяне

Горната диаграма показва процеса на разделяне на масива чрез многократно избиране на последния елемент в масива като опорна точка. На всяко ниво имайте предвид, че разделяме масива на два подмасива, като поставяме pivot в правилната му позиция.

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

Алгоритъм за бърз сорт Java

Общият алгоритъм за бърза сортировка е даден по-долу.

quicksort(Arr, low, high) begin Declare array Arr(N) to be sorted low = 1st element; high = last element; pivot if(low

По-долу е даден псевдокодът за техниката за бързо сортиране.

Псевдокод за бързо сортиране

Следва псевдокодът за техника за бързо сортиране. Имайте предвид, че сме предоставили псевдокода за рутинна сортировка и разделяне.

//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of the array high – last element of array begin if (low

Илюстрация

Нека да видим илюстрацията на алгоритъма за бързо сортиране. Вземете за пример следния масив. Тук сме избрали последния елемент като pivot.

Както е показано, първият елемент е етикетиран ниско, а последният е висок.

Илюстрация на алгоритъма Quicksort

Както е видно от горната илюстрация, има два указателя, висок и нисък, които съответно сочат към последния и първия елемент на масива. И двата указателя се преместват с напредването на бързата сортировка.

Когато елементът, посочен от долния указател, стане по-голям от въртящия елемент, а елементът, посочен от високия показател, е по-малък от основния елемент, ние обменяме елементите, посочени от долния и високия указател, и всеки указател напредва с 1 позиция.

Горните стъпки се извършват, докато двата показалеца се пресичат един в друг в масива. След като се пресекат, шарнирният елемент получава правилното си положение в масива. В този момент масивът е разделен и сега можем да сортираме всеки под-масив независимо чрез рекурсивно прилагане на алгоритъм за бързо сортиране към всеки от под-масива.

Внедряване на Quicksort в Java

Техниката QuickSort може да бъде внедрена в Java, използвайки рекурсия или итерация. В този раздел ще видим и двете техники.

Рекурсивна Quicksort

Знаем, че основната техника на бърза сортировка, илюстрирана по-горе, използва рекурсия за сортиране на масива. В рекурсивната бърза сортировка след разделяне на масива рутинната сортировка се извиква рекурсивно за сортиране на подмасивите.

Долната реализация демонстрира техниката на бърза сортировка, използваща рекурсия.

import java.util.*; class QuickSort { //selects last element as pivot, pi using which array is partitioned. int partition(int intArray(), int low, int high) { int pi = intArray(high); int i = (low-1); // smaller element index for (int j=low; j

Изход:

Оригинален масив: (4, -1, 6, 8, 0, 5, -3)
Сортиран масив: (-3, -1, 0, 4, 5, 6, 8)

Рекурсивна бърза сортировка - изход

Итеративен бърз сорт

В итеративна бърза сортировка използваме помощния стек за поставяне на междинни параметри, вместо да използваме рекурсия и сортиране на дялове.

Следващата програма Java изпълнява итеративна бърза сортировка.

import java.util.*; class Main { //partitions the array around pivot=> last element static int partition(int numArray(), int low, int high) { int pivot = numArray(high); // smaller element index int i = (low - 1); for (int j = low; j <= high - 1; j++) { // check if current element is less than or equal to pivot if (numArray(j) <= pivot) { i++; // swap the elements int temp = numArray(i); numArray(i) = numArray(j); numArray(j) = temp; } } // swap numArray(i+1) and numArray(high) (or pivot) int temp = numArray(i + 1); numArray(i + 1) = numArray(high); numArray(high) = temp; return i + 1; } //sort the array using quickSort static void quickSort(int numArray(), int low, int high) { //auxillary stack int() intStack = new int(high - low + 1); // top of stack initialized to -1 int top = -1; // push initial values of low and high to stack intStack(++top) = low; intStack(++top) = high; // Keep popping from stack while is not empty while (top>= 0) { // Pop h and l high = intStack(top--); low = intStack(top--); // Set pivot element at its correct position // in sorted array int pivot = partition(numArray, low, high); // If there are elements on left side of pivot, // then push left side to stack if (pivot - 1 > low) { intStack(++top) = low; intStack(++top) = pivot - 1; } // If there are elements on right side of pivot, // then push right side to stack if (pivot + 1

Изход:

Оригинален масив: (3, 2, 6, -1, 9, 1, -6, 10, 5)
Сортиран масив: (- 6, -1, 1, 2, 3, 6, 9, 10, 5)

Итеративна бърза сортировка - изход

често задавани въпроси

В # 1) Как работи Quicksort?

Отговор: Quicksort използва стратегия за разделяне и завладяване. Quicksort първо разделя масив около избран елемент на шарнирен елемент и генерира подмасиви, които се сортират рекурсивно.

В # 2) Каква е сложността във времето на Quicksort?

Отговор: Сложността във времето на бързата сортировка средно е O (nlogn). В най-лошия случай това е O (n ^ 2) същото като сортирането на селекцията.

В # 3) Къде се използва Quicksort?

Отговор: Quicksort се използва най-вече в рекурсивни приложения. Quicksort е част от C-библиотеката. Също така, почти езиците за програмиране, които използват вградено сортиране, изпълняват бърза сортировка.

В # 4) Какво е предимството на Quicksort?

Отговор:

  • Quicksort е ефективен алгоритъм и може лесно да сортира дори огромен списък с елементи.
  • Това е сортиране на място и следователно не се нуждае от допълнително пространство или памет.
  • Той се използва широко и осигурява ефективен начин за сортиране на набори от данни с всякаква дължина.

В # 5) Защо Quicksort е по-добър от сортирането?

Отговор: Основната причина, поради която бързата сортировка е по-добра от сортирането, е, че тази бърза сортировка е метод за сортиране на място и не изисква допълнително пространство в паметта. Сливането на обединяване изисква допълнителна памет за междинно сортиране.

Заключение

Quicksort се счита за най-добрият алгоритъм за сортиране главно поради ефективността му да сортира дори огромен набор от данни за O (nlogn) време.

Quicksort също е сортиране на място и не изисква допълнително място в паметта. В този урок видяхме рекурсивното и итеративно изпълнение на бърза сортировка.

В нашия предстоящ урок ще продължим с методите за сортиране в Java.

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

къде мога да гледам аниме безплатно

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

^