Úvod do triediacich algoritmov v Jave
Zoradiť informácie v určitom poradí, často v rámci typu poľa, je ich usporiadanie. Môžete použiť rôzne požiadavky na poradie, populárne sú triedenie čísel od najmenších po najväčšie alebo naopak, alebo lexikograficky triediace reťazce. Pokrývame rôzne algoritmy, od neefektívnych, ale intuitívnych alternatív až po efektívne algoritmy efektívne implementované v jazyku Java a ďalších jazykoch, ak máte záujem o to, ako má triedenie fungovať.
Rôzne algoritmy triedenia v jave
Existujú rôzne algoritmy triedenia a nie všetky sú rovnako účinné. Aby sme ich mohli porovnať a zistiť, ktoré z nich majú najlepšiu výkonnosť, analyzujeme ich časové zložitosti.
- Zoradenie vloženia
- Triedenie bubliniek
- Výber Zoradiť
- Zlúčiť zoradenie
- Heapsort
1. Zoradenie vloženia
Koncepcia za vložením triedenia rozdeľuje rozsah na čiastkové polia, ktoré sú triedené a netriedené. Klasifikovaná časť je na začiatku trvania 1 a zodpovedá prvej (ľavej strane) komponentu v poli. Počas každej iterácie prechádzame cez pole a rozširujeme klasifikovanú časť poľa o jednu súčasť. Po rozbalení umiestnime čerstvý prvok do zoradeného podskupiny. Robíme to tak, že presunieme všetky prvky doprava, kým nezistíme, že nemusíme meniť prvú zložku. Ak je hrubá časť zoradená vzostupne, napríklad v nasledujúcom poli, nastane:
- 3 5 7 8 4 2 1 9 6: Zvážte 4 a vložte toto, čo potrebujeme. Radíme sa od 8> 4
- 2. 3 5 7 x 8 2 1 9 6
- 3 5 x 7 8 2 1 9 6
- 3 x 5 7 8 2 1 9 6
- 3 4 5 7 8 2 1 9 6
kód:
public class InsertionSortEx (
public static void insertionSort(int() arr) (
for (int x = 1; x < arr.length; x++) (
int current = arr(x);
int y = x - 1;
while(y >= 0 && current < arr(y)) (
arr(y+1) = arr(y);
y--;
)
arr(y+1) = current;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 7, 8, 4, 2, 1, 9, 6);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
insertionSort(arr1);//sorting array using insertion sort
System.out.println("After Insertion Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)
Výkon:
Podľa tejto metódy jeden komponent rozšíril triedenú časť, teraz máme päť namiesto štyroch prvkov. Každá iterácia to robí a celé pole bude zoradené podľa konca.
Poznámka: Je to preto, že musíme preniesť celý klasifikovaný zoznam jeden po druhom v každej iterácii, ktorá je O (n). Pre každý komponent v každej tabuľke to musíme urobiť, čo znamená, že je O (n 2) ohraničené.2.2. Zoradenie bubliniek
Ak bublina nie je v požadovanom poradí, funguje výmenou susedných komponentov. Toto sa opakuje, kým nie sú všetky komponenty v poriadku od začiatku poľa. Vieme, že ak sa nám podarí urobiť celú iteráciu bez swapov, všetky položky v porovnaní s ich susednými prvkami boli v požadovanom poradí, a teda celé pole. Dôvodom algoritmu Bubble Sort je to, že čísla ako „bubliny hore“ do „zeme“. Ak po určitom množstve znova prejdete inštanciou (4 je dobrá inštancia), všimnete si, že číslo pomaly sa posúva doprava.
Kroky na triedenie bublín sú nasledujúce:
- 4 2 1 5 3: 1. prvé dve čísla nie sú v správnom poradí, preto musíme zoradiť obidve čísla.
- 2 4 1 5 3: Potom ani ďalšia dvojica čísel nie je v správnom poradí. Takže triedenie nastane znova.
- 2 1 4 5 3: Títo dvaja sú v správnom poradí, 4 <5, preto nie je potrebné ich zamieňať.
- 2 1 4 5 3 : Znovu musíme vymeniť za správny poriadok.
- 2 1 4 3 5: Toto je výsledné pole po jednej iterácii.
- Tento proces musíme opakovať znova, kým čísla nie sú v poriadku.
kód:
public class BubbleSortExample (
public static void bubbleSort(int() arr) (
int n = arr.length;
int tmp = 0;
for(int x=0; x < n; x++)(
for(int y=1; y < (nx); y++)(
if(arr(y-1) > arr(y))(
//swap elements
tmp = arr(y-1);
arr(y-1) = arr(y);
arr(y) = tmp;
)
)
)
)
public static void main(String() args) (
int arr() =(4, 2, 1, 5, 3);
System.out.println("Array Before Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
System.out.println();
bubbleSort(arr);
System.out.println("Array After Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
)
)
Výkon:
3. Výber Zoradiť
Výber zoradí pole do radu klasifikácií, ktoré nie sú usporiadané. Tentoraz sa však triediaci podarray vytvorí vložením minimálneho prvku netriedeného podradeného poľa na konci triedeného poľa výmenou:
- 3 5 1 2 4
- 1 5 3 2 4
- 1 2 3 5 4
- 1 2 3 5 4
- 1 2 3 4 5
- 1 2 3 4 5
kód:
public class SelectionSortEx (
public static void selectionSort(int() arr)(
for (int x = 0; x < arr.length - 1; x++)
(
int indx = x;
for (int y = x + 1; y < arr.length; y++)(
if (arr(y) < arr(indx))(
indx = y;
)
)
int smallNumber = arr(indx);
arr(indx) = arr(x);
arr(x) = smallNumber;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 1, 2, 4);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
selectionSort(arr1);
System.out.println("After Selection Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)
Výkon:
4. Zlúčiť zoradenie
Merge Sort využíva rekurziu na vyriešenie problému metódy rozdelenia a dobytia efektívnejšie ako predtým opísané algoritmy.
Tento strom ukazuje, ako fungujú rekurzívne hovory. Polia označené šípkou nadol sú polia, pre ktoré nazývame funkciou, zatiaľ čo polia so šípkami nahor. Potom sledujte šípku k okraju stromu a potom sa vráťte a zlúčte. Máme rad 3 5 3 1, takže sme ho rozdelili na 3 5 4 a 2 1. Rozdelili sme ich na ich časti, aby sme ich usporiadali. Keď sa dostaneme na dno, začneme ich fúzovať a triediť.
kód:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class MergeSort (
static void merge(int() array, int lowval, int midval, int highval)(
int x, y, k;
int() c= new int(highval-lowval+1);
k = 0;
x=lowval;
y=midval+1;
while(x<=midval && y<=highval)(
if(array(x)<=array(y))(
c(k++) = array(x++);
)
else(
c(k++) = array(y++);
)
)
while(x<=midval)(
c(k++) = array(x++);
)
while(y<=highval)(
c(k++) = array(y++);
)
k=0;
for(x = lowval; x<=highval; x++)(
array(x) = c(k++);
)
)
static void mergeSort(int() array, int lowval, int highval)(
if(highval-lowval+1>1)(
int midval = (lowval+highval)/2;
mergeSort(array, lowval, midval);
mergeSort(array, midval+1, highval);
merge(array, lowval, midval, highval);
)
)
public static void main(String() args) (
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
int size;
System.out.println("Enter the array");
try (
size = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("Please Enter valid Input");
return;
)
int() array = new int(size);
System.out.println("Enter array elements");
int x;
for (x = 0; x < array.length; x++) (
try (
array(x) = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("An error Occurred");
)
)
System.out.println("After Sorting");
System.out.println(Arrays.toString(array));
mergeSort(array, 0, array.length-1);
System.out.println("Before Merge Sorting");
System.out.println(Arrays.toString(array));
)
)
V tomto programe sme požiadali používateľa o zadanie vstupu. Výstup bude zoradený podľa vstupu používateľa.
Výkon:
5. Usporiadanie haldy
Najprv musíte poznať rámec, v ktorom Heapsort pracuje - halda -, aby ste pochopili, prečo funguje. Budeme hovoriť konkrétne o binárnej halde, ale môžete ju zovšeobecniť aj na iné haldy. Halda je strom, ktorý spĺňa vlastnosti haldy, a to, že všetky jej deti majú vzťahy s každým uzlom. Halda musí byť tiež takmer hotová. Binárny program s hĺbkou takmer d má hĺbku d-1 s rovnakým koreňom a každý uzol má celú ľavú podstromu s ľavým klesaním.
Inými slovami, pri pohybe nadol stromu získate menšie a nižšie číslo (min-halda) alebo väčšie a väčšie (max-halda). Toto je inštancia s maximálnou veľkosťou haldy:
- 6 1 8 3 5 2 4 : Tu sú obe čísla detí menšie ako rodičia, takže nemusíme nič meniť.
- 6 1 8 3 5 2 4: Tu, 5> 1, ich musíme vymeniť. Potrebujeme haldifikovať 5.
- 6 5 8 3 1 2 4: Obidve čísla detí sú menšie, všetko zostáva rovnaké.
- 6 5 8 3 1 2 4: Tu, 8> 6, mali by sme ich vymeniť.
- 8 5 6 3 1 2 4: Po tomto opakovaní získame tento výsledok.
Po opätovnom opakovaní tohto procesu získame nasledujúce výsledky:
- 8 5 6 3 1 2 4
- 4 5 6 3 1 2 8 : Výmena
- 6 5 4 3 1 2 8 : Heapify
- 2 5 4 3 1 6 8 : Výmena
- 5 2 4 2 1 6 8 : Heapify
- 1 2 4 2 5 6 8 : Výmena
kód:
public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
)public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
)
Výkon:
Môžete si ju pozrieť z bodu na úroveň grafu, zľava doprava. To, čo sme tu dosiahli, je, že keď máme k-tý komponent v poli, pozícia jeho detí je 2 \ * k + 1 a 2 \ * k + 2 (za predpokladu, že indexovanie začína na 0). Môžete to sledovať vy. Pozícia rodiča je vždy (k-1) / 2 pre k-tý komponent. Môžete ľahko „maximalizovať hromadu“ ľubovoľného rozsahu, pretože to viete. Skontrolujte, či je jedno z jeho detí nižšie ako množstvo pre každú súčasť. Ak áno, spárujte jedného rodiča a tento krok opakujte rekurzívne s rodičom.
Poznámka: Pretože opakovanie for-loop v celom poli vytvára heapSort) (samozrejme O (N), vytvorilo by to celkovú komplexnosť Heapsort O (nlog n). Heapsort má typ na mieste, čo znamená, že vyžaduje O ( 1) viac miesta ako zlúčiť zoradenie, má však niektoré nevýhody, napríklad tvrdé paralely.Záver - Radenie algoritmov v jazyku Java
Zoradenie je veľmi rozšírený postup s množinami údajov, či už ide o ďalšiu analýzu, zrýchlenie vyhľadávania s efektívnejšími algoritmami založenými na utriedených informáciách, informácie o filtrovaní atď. Zoradenie podporuje niekoľko jazykov a rozhrania často zakrývajú to, čo programátor robí.
Odporúčané články
Toto je sprievodca triedením algoritmov v Jave. Tu diskutujeme rôzne typy triedenia v Jave spolu s ich algoritmami. Môžete si tiež prečítať naše ďalšie navrhované články -
- Zlúčiť algoritmy triedenia v Jave
- JComboBox v Jave
- StringBuffer v Jave
- JTextField v Jave
- Halda Zoradiť v Pythone
- Algoritmy rýchleho triedenia v Jave
- Kompletný sprievodca triedením v C # s príkladmi
- Zoradenie algoritmov v JavaScripte
- Sprievodca príkladmi algoritmu C ++
- Kompletný sprievodca triedením algoritmov v Pythone