Въведение в бързо сортиране на алгоритми в Java
Бързото сортиране в Java също познато като сортиране за размяна на дялове е алгоритъм за сортиране на разделение и завладяване. Бързото сортиране е добър пример за алгоритъм, който използва най-добре кешовете на процесора, поради разделението си и завладява природата. Quicksort алгоритъмът е един от най-използваните алгоритми за сортиране, особено за сортиране на големите списъци и повечето програмни езици са го приложили. В алгоритъма на Quicksort първоначалните данни са разделени на две части, които се сортират индивидуално и след това се обединяват, за да се получат сортирани данни.
Нека помислим, че масивът (8, 6, 3, 4, 9, 2, 1, 7) трябва да бъде сортиран с помощта на Quick Sort.
Стъпки за внедряване на бързо сортиране на алгоритми
1. Изберете елемент, наречен въртящ се от масива. По принцип средният елемент е избран като въртящ се. Нека вземем 4 като опорна точка.
2. Пренаредете масива на две части, така че елементи, по-малки от въртенето, да се появят преди въртенето, а елементи, по-големи от въртенето, да се появят след въртенето. Следват стъпки:
- Изберете най-левия елемент, т.е. 8, Тъй като 4 е въртящият се елемент, а 8 е повече от 4, 8 трябва да се премести вдясно от 4, От дясната страна оставяме 7, тъй като е по-голям от 4 и изберете 1 за смяна с 8 оттук след размяна на масива става: 1, 6, 3, 4, 9, 2, 8, 7
- Изберете следващия ляв елемент, т.е. 6, Тъй като 4 е въртящият се елемент, а 6 е повече от 4, 6 трябва да се премести вдясно от 4, От дясната страна оставяме 7, 8, тъй като те са по-големи от 4 и изберете 2 за замяна с 6 оттук след размяна на масива става: 1, 2, 3, 4, 9, 6, 8, 7
- Тъй като всички елементи отляво на въртенето са по-малки от въртенето и всички елементи отдясно на въртенето са по-големи от въртенето, ние сме готови с 4 като въртене.
3. Рекурсивно приложете стъпки 1 и 2 за левия под масив (масив с елементи по-малък от въртящия се) и за десния подмасив (масив с елементи повече от въртящия се). Ако масивът съдържа само един или нулев елемент, тогава масивът се счита за асортиран.
Програма за прилагане на алгоритми за бързо сортиране
Ето ява програма за сортиране на масив от цели числа, използвайки алгоритъм за бързо сортиране.
Код:
import java.lang.*;
import java.util.*;
public class Main (
private int array();
private int length;
public void sort(int() inputArrayArr) (
if (inputArrayArr == null || inputArrayArr.length == 0) (
return;
)
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
)
private void performQuickSort(int lowerIndex, int higherIndex) (
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array(lowerIndex+(higherIndex-lowerIndex)/2);
// Divide into two subarrays
while (i <= j) (
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array(i) < pivot) (
i++;
)
while (array(j) > pivot) (
j--;
)
if (i <= j) (
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
)
)
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
)
private void swapNumbers(int i, int j) (
int temp = array(i);
array(i) = array(j);
array(j) = temp;
)
public static void main(String args())(
Main quickSort = new Main();
int() inputArray = (8, 6, 3, 4, 9, 2, 1, 7);
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
)
)
изход:
Предимства на алгоритмите за бързо сортиране
Следните са предимствата на алгоритъма за бързо сортиране:
- Отлична референтна локалност : Референтната локалност е способността на процесора да осъществява достъп до едно и също място в паметта многократно за кратък период от време. Бързото сортиране в java осигурява отлично местоположение на справочник поради много малкия брой пропуски в кеша, което в съвременните архитектури е изключително важно за ефективността.
- Бързото сортиране е паралелно: След като приключи първоначалната стъпка на разделяне на масив в по-малки региони, всички отделни подредове могат да бъдат сортирани независимо паралелно. Поради тази причина, бързото сортиране се представя по-добре.
Анализ на сложността на бързото сортиране
Quicksort е бърз и рекурсивен алгоритъм, който работи по принципа на разделяне и завладяване. Ето неговия анализ на сложността в най-добрия, средния и най-лошия случай:
- Най-добра сложност на случая: Ако масив или списък съдържа n елемента, тогава за първото изпълнение ще е необходимо O (n). Сега Сортирането на останалите две подредове отнема 2 * O (n / 2). Това завършва сложността на O (n logn) в най-добрия случай.
- Средна сложност на случая : Средният случай на бърз корт е O (n log n).
- Най-лоша сложност на случая: Избирането на първа или последна би довело до най-лошо изпълнение за почти сортирани или почти обратни сортирани данни. Бързото сортиране изпълнява O (n 2) в най-лошия случай.
В Java, масиви. Методът Sort () използва алгоритъм за бързо сортиране, за да сортира масив.
Препоръчителни статии
Това е ръководство за бързо сортиране на алгоритми в Java. Тук обсъждаме стъпките за прилагане, анализ на предимствата и сложността на алгоритъма за бързо сортиране в Java заедно с програмата. Можете също да разгледате следните статии, за да научите повече -
- Сортиране на вмъкване в Java
- do-while цикъл в Java
- JComponent в Java
- Квадрати в Java
- Размяна в PHP
- Сортиране в C #
- Сортиране в Python
- C ++ Алгоритъм | Примери за C ++ алгоритъм