Sissejuhatus sisestamisse Sorteeri Java
Kui olete programmeerija, siis olete juba palju kuulnud sorteerimisest. Sorteerimine tähendab elementide paigutamist kas kasvavas või kahanevas järjekorras. Elementide sortimiseks on saadaval nii palju sortimisalgoritme ja igal algoritmil on erinevad sortimisviisid, erinev keerukus. Seega sõltub konkreetsest stsenaariumist ja elementide arvust, millist algoritmi tuleks kasutada. Sisestus on ka üks kõige sagedamini kasutatavaid sortimisalgoritme, mille keerukus on O (n 2) üldiselt ja seda tehakse nii, nagu sorteerime oma käes olevad mängukaardid. Selles teemas õpime Java sisestussorteerimise kohta.
Kuidas sisestamise sortimine Java-keeles töötab?
Saame aru sisestussorteerimise toimimisest näite abil. Oletame, et on olemas massiiv nimega arr, millel on järgmised elemendid:
10 5 8 20 30 2 9 7
1. samm - sisestamise sortimine algab massiivi 2. elemendist, st 5, arvestades massiivi esimest elementi, mis on iseenesest komplekteeritud. Nüüd võrreldakse elementi 5 10-ga, kuna 5 on vähem kui 10, seega liigutatakse 10 1 positsiooni ette ja 5 sisestatakse enne seda.
Nüüd on tulemuseks olev massiiv:
5 10 8 20 30 2 9 7
2. samm - nüüd võrreldakse elementi arr (2), st 8 elementi arr (1), st 10. Kuna 8 on väiksem kui eelnev element 10, nihutatakse seda sammu võrra oma positsioonist ette ja siis võrreldes 5-ga. Kuna 8 on suurem kui 5, sisestatakse see pärast seda.
Siis saadav massiiv on:
5 8 10 20 30 2 9 7
3. samm - nüüd võrreldakse elementi 20 10-ga, kuna see on suurem kui 10, jääb see oma kohale.
5 8 10 20 30 2 9 7
4. samm - elementi 30 võrreldakse 20-ga ja kuna see on suurem kui 20, siis muudatusi ei tehta ja massiiv jääb selliseks, nagu ta on. Nüüd massiiv oleks
5 8 10 20 30 2 9 7
5. samm - elementi 2 võrreldakse 30-ga, kuna see on väiksem kui 30, nihutatakse seda ühe positsiooni võrra ette, siis võrreldakse seda ükshaaval 20, 10, 8, 5-ga ja kõik elemendid nihutatakse 1-asendisse ette. ja 2 lisatakse enne 5.
Saadud massiiv on:
2 5 8 10 20 30 9 7
6. samm - elementi 9 võrreldakse 30-ga, kuna see on väiksem kui 30, võrreldakse seda ükshaaval 20, 10-ga ja element nihkub 1 positsiooni ette ja 9 sisestatakse enne 10 ja pärast 8. Saadud massiiv on:
2 5 8 9 10 20 30 7
7. samm - elementi 7 võrreldakse 30-ga ja kuna see on väiksem kui 30, võrreldakse seda 30-ga, 20-ga, 10-ga, 9-ga, 8-ga ja kõiki elemente nihutatakse üks asend ükshaaval ette ja 7 sisestatakse enne 8 Saadud massiiviks saab:
2 5 7 8 9 10 20 30
Sel viisil sorteeritakse massiivi kõik elemendid sisestussorteerimise teel, alustades võrdlust eelmise elemendiga.
Sisestamise näited Sorteeri Java
Lisamise sortimine Java-s on lihtne sortimisalgoritm, mis sobib kõigi väikeste andmekogumite jaoks.
public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)public class InsertionSort (
public static void insertionSort(int arr()) ( for (int j = 1; j < arr.length; j++) ( int key = arr(j); int i = j-1;
while ( (i > -1) && ( arr(i) > key ) ) ( arr(i+1) = arr(i); i--; )
arr(i+1) = key;
)
)
static void printArray(int arr()) ( int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i System.out.print(arr(i) + " " );
System.out.println();
)
public static void main(String args())( int() arr1 = (21, 18, 15, 23, 52, 12, 61);
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
)
)
Väljund:
12 15 18 21 23 52 61
Selgitus:
Ülaltoodud lisamise sortimise programmis kasutatakse algse massiivi elementide sortimiseks funktsiooni insertionSort (). Sorteerimine algab teisest elemendist, kuna esimene element on iseenesest sorditud. Niisiis algab 'j' silmus massiivi indeksist 1. "i" on muutuja, mis jälgib indeksit vahetult enne "j", et väärtust võrrelda. " võti 'on muutuja, mis hoiab praeguse elemendi väärtust, mis tuleb järjestatud asendisse paigutada. samal ajal kui () silmust teostatakse, kui voolu väärtus on väiksem kui vasakpoolne väärtus, nii et elementide nihutamist saab töödelda ja voolu elemendi lõpus õiges asendis sisestamise saab teha. printArray () funktsiooni kasutatakse sorteeritud massiivi lõplikuks printimiseks.
1. Parim juhtum
Sisestussorteerimise korral oleks parim juhtum, kui massiivi kõik elemendid on juba sorteeritud. Nii et kui mõnda elementi võrreldakse selle vasakpoolseima elemendiga, on see alati suurem ja seega ei töödelda elementide nihutamist ega sisestamist. Sel juhul oleks parimate juhtumite keerukus lineaarne, st O (n).
2. Halvim juhtum
Ülaltoodud sisestuskoodi korral oleks halvim juhtum, kui maatriks on vastupidises järjekorras, nii et iga kord, kui elementi võrreldakse selle kõige vasakpoolsema elemendiga, on see alati väiksem ja seejärel võrrelda seda kõigi toimuvate elementidega, mis toimuvad ja nihkuvad ja sisestamine on tehtud. Sel juhul on sisestamise sorteerimise keerukus O (n 2).
3. Keskmine juhtum
Isegi keskmisel juhul on sisestussorteerimisel O (n 2) keerukus, kus mõned elemendid ei vaja nihutamist, samas kui mõned elemendid nihutatakse oma positsioonidest ja sisestamine õiges asendis toimub.
4. Parim kasutamine
Sissetüüpi on kõige parem kasutada siis, kui massiivi suurus ei ole väga suur või tuleb sortida vaid väike arv elemente, milles on sorteeritud peaaegu kõik elemendid ja teha tuleb vaid mõned muudatused. Sisestussorteerimine on üks kiiremaid algoritme väikese suurusega massiivi jaoks, isegi kiiremini kui kiirsorteerimine. Tegelikult kasutab kiirsortort massiivi väikeste osade sorteerimisel Insertion sortimist.
Järeldus
Ülaltoodud selgitus näitab selgelt sisestussorteerimise toimimist ja rakendamist Java-s. Ka teistes programmeerimiskeeltes jääb sisestuse sortimise loogika samaks, ainult süntaksi muudatused. Enne mis tahes sortimisalgoritmi rakendamist on väga oluline analüüsida stsenaariumi, kus sorteerimine tuleb läbi viia, kuna mitte kõik sortimisalgoritmid ei sobi kõigi stsenaariumide jaoks.
Soovitatavad artiklid
See on Java-sisestuse sortimise juhend. Siin arutleme, kuidas sisestussorteerimine javas toimib, koos Java-sisestussorteerimise juurutamise näidetega. Võite lisateabe saamiseks vaadata ka järgmisi artikleid -
- Ruutjuur Java-s
- BorderLayout Java-s
- Pöördnumber Java-s
- StringBuffer Java-s
- Ruutjuur PHP-s
- Ruutjuur JavaScriptis
- Juhend 6 populaarseima algoritmi sortimiseks Pythonis