Uvod v razvrščanje algoritmov na Javi
Podatke razvrstite po določenem vrstnem redu, pogosto v okviru podoben matriki. Uporabite lahko različne zahteve po zaporedju, priljubljene so razvrščanje števil od najmanj do največjih ali obratno ali leksikografsko razvrščanje nizov. Zajemali bomo različne algoritme, od neučinkovitih, a intuitivnih alternativ do učinkovitih algoritmov, ki se učinkovito izvajajo na Javi in v drugih jezikih, če vas zanima, kako naj razvrščanje deluje.
Različni algoritmi za razvrščanje v javi
Obstajajo različni algoritmi za razvrščanje in niso vsi enako učinkoviti. Da jih primerjamo in vidimo, kateri se najbolje odrežejo, bomo analizirali njihove časovne zapletenosti.
- Razvrsti vstavljanje
- Razporeditev mehurčkov
- Razvrstitev izbire
- Združi razvrstitev
- Zmogljivost
1. Razvrstitev vstavka
Koncept za Vstavljanje sorte razdeli obseg na poddruge, ki so razvrščene in nesortirane. Razvrščeni del je na začetku trajanja 1 in se ujema s prvo (levo stransko) komponento v nizu. Skozi matriko se premikamo in razvrstimo razvrščeni del matrike za eno komponento med vsako ponovitvijo. Ko se razširimo, svež element postavimo v razvrščeno podpolje. To naredimo tako, da vse elemente premaknemo v desno, dokler ne ugotovimo, da nam prve komponente ni treba spreminjati. Ko je krepki del razvrščen v naraščajočem vrstnem redu, na primer, v naslednji niz:
- 3 5 7 8 4 2 1 9 6: Razmislimo o 4 in vstavljanje tega je tisto, kar potrebujemo. Prestavljamo se 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
Koda:
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+" ");
)
)
)
Izhod:
Po tej metodi je ena komponenta razširila razvrščeni del, zdaj jih imamo pet namesto štirih elementov. Vsaka iteracija to stori in do konca bo razvrščen celoten niz.
Opomba: To je zato, ker moramo v vsaki iteraciji prenesti celoten tajni seznam, ki je O (n). Za vsako komponento v vsaki tabeli moramo to narediti, kar pomeni, da je omejena z O (n 2).2. Razporeditev mehurčkov
Če mehurček ni v želenem vrstnem redu, deluje z zamenjavo sosednjih komponent. To se ponavlja, dokler vse komponente niso v redu od začetka matrike. Vemo, da če nam uspe izvesti celotno iteracijo brez zamenjav, so bili vsi predmeti v primerjavi s sosednjimi elementi v želenem vrstnem redu in podaljšek celotni niz. Razlog za algoritem Razvrščanje mehurčkov je v tem, da številke, kot so "mehurčki", v "zemljo". Če po določenem znesku znova preidete skozi primerek (4 je dober primerek), boste opazili, da številka počasi premakne se v desno.
Koraki za razvrščanje mehurčkov so naslednji:
- 4 2 1 5 3: Tukaj prvi dve številki nista v pravem vrstnem redu, zato moramo obe številki razvrstiti.
- 2 4 1 5 3: Po tem naslednji par številk tudi ni v pravem vrstnem redu. Tako se razvrščanje spet pojavi.
- 2 1 4 5 3: Ta dva sta v pravem vrstnem redu, 4 <5, zato ju ni treba zamenjati.
- 2 1 4 5 3 : Spet moramo zamenjati za pravilno naročilo.
- 2 1 4 3 5: Tu je nastali niz po eni ponovitvi.
- Ponoviti moramo ta postopek, dokler številke ne bodo v ustreznem vrstnem redu.
Koda:
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) + " ");
)
)
)
Izhod:
3. Razvrstitev izbire
Selection Sort razdeli matriko na matriko klasifikacij, ki niso razvrščene. Tokrat pa se podvrsti sortiranja oblikujejo tako, da se na koncu razvrščenega niza vstavi minimalni element nesortiranega podreja z zamenjavo:
- 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
Koda:
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+" ");
)
)
)
Izhod:
4. Združi razvrstitev
Združitve Razvrstitev uporablja rekurzijo, da odpravi težavo z načinom delitve in osvajanja učinkoviteje kot prej opisani algoritmi.
To drevo prikazuje, kako delujejo rekurzivni klici. Zaznamovani nizi s puščicami navzdol so matriki, za katere pokličemo funkcijo, medtem ko matrike puščic gorimo. Nato sledite puščici do roba drevesa in se nato vrnite in združite. Imamo razpon 3 5 3 1, zato ga razdelimo na 3 5 4 in 2 1. Razdelimo jih na njihove dele, da jih razvrstimo. Začnemo jih zliti in razvrščati, ko gremo, ko pridemo do dna.
Koda:
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 tem programu smo uporabnika prosili za vnos vnosa. Izhod bo razvrščen glede na uporabnikov vnos.
Izhod:
5. Heap Sort
Najprej morate poznati okvir, v katerem deluje Heapsort - kup, da bi razumeli, zakaj deluje. Posebej bomo govorili o binarni gomili, vendar lahko to posplošite tudi na druge konstrukcije kopice. Kopča je drevo, ki izpolnjuje lastnost kopice, in sicer da imajo vsi njegovi otroci razmerja do vsakega vozlišča. Kopa mora biti tudi skoraj končana. Binarni zapis skoraj popolne d-globine ima poddrevo d-1 z istim korenom in vsako vozlišče ima polno, levo poddrevo z levo padajočim.
Z drugimi besedami, med premikanjem po drevesu dobite nižje in manjše število (min-heap) ali večje in večje (max-heap). Tu je primer max-heap:
- 6 1 8 3 5 2 4 : Tu sta obe otroški številki manjši od staršev, zato nam ni treba ničesar spremeniti.
- 6 1 8 3 5 2 4: Tukaj, 5> 1, jih moramo zamenjati. Za 5 moramo zbrati.
- 6 5 8 3 1 2 4: Obe otroški številki sta manjši, vse ostane enako.
- 6 5 8 3 1 2 4: Tukaj, 8> 6, zato bi jih morali zamenjati.
- 8 5 6 3 1 2 4: Po tej ponovitvi bomo dobili ta rezultat.
Po ponovitvi tega postopka bomo dobili naslednje rezultate:
- 8 5 6 3 1 2 4
- 4 5 6 3 1 2 8 : Zamenjava
- 6 5 4 3 1 2 8 : Napihnite
- 2 5 4 3 1 6 8 : Zamenjava
- 5 2 4 2 1 6 8 : Napihnite
- 1 2 4 2 5 6 8 : Zamenjava
Koda:
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);
)
)
Izhod:
Ogledate si ga lahko od točke do stopnje grafa, od leve proti desni. Pri tem smo dosegli, da ko imamo kth komponento v polju, je položaj njenih otrok 2 \ * k + 1 in 2 \ * k + 2 (ob predpostavki, da se indeksiranje začne pri 0). To lahko spremljate vi. Položaj nadrejenega je za kth komponento vedno (k-1) / 2. Lahko zlahka "maksimirate" poljuben obseg, ker to veste. Preverite, ali je eden od njegovih otrok nižji kot pri vsaki komponenti. V tem primeru združite enega od staršev in ponovite ta korak z nadrejenim.
Opomba: Ker iteriranje za-zank v celotnem nizu naredi heapSort) (očitno O (N), bi ustvaril splošno kompleksnost Heapsort O (nlog n). Heapsort ima tip na kraju samem, kar pomeni, da potrebuje O ( 1) več prostora kot Merge Sort, vendar ima nekaj pomanjkljivosti, kot so trde vzporednice.Zaključek - Razvrščanje algoritmov v Javi
Razvrščanje je zelo razširjen postopek z nabori podatkov, naj gre za nadaljnjo analizo, pospeševanje iskanja z učinkovitejšimi algoritmi, ki se opirajo na razvrščene informacije, filtriranje informacij itd. Razvrščanje je podprto v več jezikih in pogosto vmesniki zasenčijo, kaj programer počne.
Priporočeni članki
To je vodnik za razvrščanje algoritmov na Javi. Tukaj razpravljamo o različnih vrstah razvrščanja v Javi in njihovih algoritmov. Ogledate si lahko tudi druge naše predlagane članke -
- Združite algoritme razvrščanja v Javi
- JComboBox na Javi
- StringBuffer v Javi
- JTextField v Javi
- Razvrstite v Python
- Hitro razvrščanje algoritmov na Javi
- Celoten vodnik za razvrščanje v C # s primeri
- Razvrščanje algoritmov v JavaScript
- Vodnik po primerih algoritma C ++
- Celoten vodnik za razvrščanje algoritmov v Pythonu