bubble sort java java sorting algorithms code examples
Tento tutoriál vysvetlí bublinové triedenie v Jave spolu s hlavným algoritmom triedenia v jazyku Java, implementáciou bublinového triedenia a príkladmi kódu:
aplikácia na naplánovanie príspevkov na instagrame zadarmo
Algoritmus triedenia je možné definovať ako algoritmus alebo postup na zoradenie prvkov kolekcie v konkrétnom poradí. Napríklad, ak máte číselnú zbierku ako ArrayList celých čísel, možno budete chcieť usporiadať prvky ArrayList vzostupne alebo zostupne.
Podobne môžete usporiadať reťazce z kolekcie reťazcov v abecednom alebo lexikografickom poradí. To je miesto, kde prichádzajú na rad triediace algoritmy v Jave.
Čo sa dozviete:
Hlavné triediace algoritmy v Jave
Algoritmy triedenia sa zvyčajne hodnotia v závislosti od časovej a priestorovej zložitosti. Java podporuje rôzne triediace algoritmy, ktoré sa používajú na triedenie alebo usporiadanie kolekcií alebo dátových štruktúr.
Nasledujúca tabuľka zobrazuje hlavné triediace algoritmy podporované v Jave spolu s ich najlepšími / najhoršími zložitosťami.
| Časová zložitosť | ||||
|---|---|---|---|---|
| Radix Sort | Algoritmus lineárneho triedenia. | O (nk) | O (nk) | O (nk) |
| Algoritmus triedenia | Popis | Najlepší prípad | V najhoršom prípade | Priemerný prípad |
| Triedenie bublín | Opakovane porovnáva aktuálny prvok so susednými prvkami. Na konci každej iterácie prebubláva najťažší prvok na správnom mieste. | O (n) | O (n ^ 2) | O (n ^ 2) |
| Triedenie vloženia | Vloží každý prvok kolekcie na správne miesto. | O (n) | O (n ^ 2) | O (n ^ 2) |
| Zlúčiť zoradenie | Sleduje prístup rozdeliť a panovať. Rozdelí zbierku na jednoduchšie čiastkové zbierky, zoradí ich a potom všetko zlúči | O (neprihlásiť sa) | O (neprihlásiť sa) | O (neprihlásiť sa) |
| Rýchle triedenie | Najefektívnejšia a optimalizovaná technika triedenia. Na triedenie zbierky sa používa rozdelenie a dobývanie. | O (neprihlásiť sa) | O (n ^ 2) | O (neprihlásiť sa) |
| Výber Zoradiť | Nájde najmenší prvok v zbierke a na konci každej iterácie ho umiestnite na správne miesto | O (N ^ 2) | O (N ^ 2) | O (N ^ 2) |
| Hromadné triedenie | Prvky sa triedia podľa minimálnej alebo maximálnej hromady. | O (neprihlásiť sa) | O (neprihlásiť sa) | O (neprihlásiť sa) |
Okrem techník triedenia uvedených v tabuľke vyššie podporuje Java aj nasledujúce techniky triedenia:
- Triedenie vedra
- Počítanie Triedenie
- Shell Sort
- Hrebeň triediť
Ale tieto techniky sa v praktických aplikáciách používajú striedmo, takže tieto techniky nebudú súčasťou tejto série.
Poďme si predstaviť techniku bublinového triedenia v Jave.
Bublinové triedenie v Jave
Bubble sort je najjednoduchšia zo všetkých triediacich techník v Jave. Táto technika triedi kolekciu opakovaným porovnávaním dvoch susedných prvkov a ich výmenou, ak nie sú v požadovanom poradí. Na konci iterácie teda prebubláva najťažší prvok, aby získal svoju právoplatnú pozíciu.
Ak je v zozname A n prvkov daných A [0], A [1], A [2], A [3],… .A [n-1], potom sa A [0] porovnáva s A [1 ], A [1] sa porovnáva s A [2] atď. Po porovnaní, ak je prvý prvok väčší ako druhý, sú dva prvky vymenené, ak nie sú v poriadku.
Algoritmus triedenia bublín
Všeobecný algoritmus pre postup triedenia bublín je uvedený nižšie:
Krok 1: Pre i = 0 až N-1 opakujte krok 2
Krok 2: Pre J = i + 1 až N - opakujem
aký je najlepší softvér na odstránenie škodlivého softvéru
Krok 3: ak A [J]> A [i]
Zamieňajte A [J] a A [i]
[End of Inner for loop]
[Koniec, ak je vonkajší pre slučku]
Krok 4: Východ
Teraz si ukážeme techniku Bubble Sort na ilustračnom príklade.
Vezmeme pole s veľkosťou 5 a ilustrujeme algoritmus triedenia bublín.
Zoradenie poľa pomocou bublinového triedenia
Nasledujúci zoznam je potrebné zoradiť.
Ako vidíte vyššie, pole je úplne zoradené.
Vyššie uvedenú ilustráciu je možné zhrnúť do tabuľky, ako je uvedené nižšie:
| Prejdite | Netriedený zoznam | porovnanie | Zoradený zoznam |
|---|---|---|---|
| {3,6,11,4,15} | {11.4} | {3,6,4,11,15} | |
| 1 | {11, 3, 6,15,4} | {11.3} | {3,11,6,15,4} |
| {3,11,6,15,4} | {11,6} | {3,6,11,15,4} | |
| {3,6,11,15,4} | {11.15} | {3,6,11,15,4} | |
| {3,6,11,15,4} | {15.4} | {3,6,11,4,15} | |
| dva | {3,6,11,4,15} | {3,6} | {3,6,11,4,15} |
| {3,6,11,4,15} | {6.11} | {3,6,11,4,15} | |
| 3 | {3,6,4,11,15} | {3,6} | {3,6,4,11,15} |
| {3,6,4,11,15} | {6.4} | {3,4,6,11,15} | |
| {3,4,6,11,15} | Triedené |
Ako je uvedené v predchádzajúcom príklade, najväčší prvok pri každej iterácii / prechode prebubláva do svojej správnej polohy. Všeobecne platí, že keď dosiahneme N-1 (kde N je celkový počet prvkov v zozname), prejde to; budeme mať celý zoznam zoradený.
Príklad kódu bublinového triedenia
Nasledujúci program zobrazuje implementáciu algoritmu bublinového triedenia v prostredí Java. Tu udržiavame pole čísel a pomocou dvoch cyklov prechádzame susednými prvkami poľa. Ak dva susedné prvky nie sú v poriadku, potom sa vymenia.
import java.util.*; class Main{ // Driver method to test above public static void main(String args[]) { //declare an array of integers int intArray[] = {23,43,13,65,11,62,76,83,9,71,84,34,96,80}; //print original array System.out.println('Original array: ' + Arrays.toString(intArray)); int n = intArray.length; //iterate over the array comparing adjacent elements for (int i = 0; i intArray[j+1]) { int temp = intArray[j]; intArray[j] = intArray[j+1]; intArray[j+1] = temp; } //print the sorted array System.out.println('Sorted array: ' + Arrays.toString(intArray)); } } Výkon:
Pôvodné pole: [23, 43, 13, 65, 11, 62, 76, 83, 9, 71, 84, 34, 96, 80]
Zoradené pole: [9, 11, 13, 23, 34, 43, 62, 65, 71, 76, 80, 83, 84, 96]
často kladené otázky
Otázka 1) Aké sú triediace algoritmy v Jave?
ako porovnať dva súbory v unixe -
Odpoveď: Algoritmus triedenia je možné definovať ako algoritmus alebo postup, pomocou ktorého je možné prvky v kolekcii zoradiť alebo usporiadať požadovaným spôsobom.
Ďalej uvádzame niektoré z algoritmov triedenia podporovaných v prostredí Java:
- Triedenie bublín
- Triedenie vloženia
- Zoradenie výberu
- Zlúčiť triedenie
- Quicksort
- Radix triediť
- Heapsort
Otázka č. 2) Aký je najlepší triediaci algoritmus v Jave?
Odpoveď: Merge Sort má byť najrýchlejším algoritmom triedenia v Jave. V skutočnosti Java 7 interne používala triedenie zlúčenia na implementáciu metódy Collections.sort (). Rýchle triedenie je tiež ďalším najlepšie triediacim algoritmom.
Otázka č. 3) Čo je to Bubble sort v Jave?
Odpoveď: Bublinové triedenie je najjednoduchší algoritmus v Jave. Bublinové triedenie vždy porovnáva dva susedné prvky v zozname a zamieňa ich, ak nie sú v požadovanom poradí. Na konci každej iterácie alebo prejdenia teda najťažší prvok prebubláva na svoje správne miesto.
Otázka č. 4) Prečo je Bubble druh Ndva?
Odpoveď: Na implementáciu triedenia bublín používame pre slučky dve.
Celková vykonaná práca sa meria pomocou:
Množstvo práce vykonanej vnútornou slučkou * celkový počet spustení vonkajšej slučky.
Pre zoznam n prvkov pracuje vnútorná slučka pre O (n) pre každú iteráciu. Vonkajšia slučka beží pre O (n) iteráciu. Preto je celková vykonaná práca O (n) * O (n) = O (ndva)
Otázka č. 15) Aké sú výhody druhu Bubble?
Odpoveď: Výhody Bubble Sort sú nasledujúce:
- Ľahko kódovateľné a zrozumiteľné.
- Na implementáciu algoritmu je potrebných niekoľko riadkov kódu.
- Triedenie sa vykonáva na mieste, to znamená, že nie je potrebná ďalšia pamäť, a teda ani žiadna pamäť nad hlavou.
- Triedené údaje sú okamžite k dispozícii na spracovanie.
Záver
Doteraz sme diskutovali o algoritme triedenia Bubble Sort v Jave. Preskúmali sme tiež algoritmus a podrobnú ilustráciu triedenia poľa pomocou techniky bublinového triedenia. Potom sme implementovali program Java do Bubble Sort.
V nasledujúcom tutoriále budeme pokračovať ostatnými technikami triedenia v Jave.
=> Skontrolujte VŠETKY návody Java tu.
Odporúčané čítanie
- Výberové triedenie v Jave - Algoritmus a výberové triedenie výberu
- Insertion Sort In Java - Algoritmus a príklady na triedenie vloženia
- Bublinové triedenie v C ++ s príkladmi
- Ako zoradiť pole v Jave - návod s príkladmi
- Výukový program Java Array Length s príkladmi kódu
- Metóda MongoDB Sort () s príkladmi
- Unixový príkaz na triedenie so syntaxou, možnosťami a príkladmi
- Java „toto“ kľúčové slovo: Výukový program s príkladmi kódu