Johdanto lisäykseen Järjestä Java
Jos olet ohjelmoija, sinun on täytynyt olla jo kuullut paljon lajittelusta. Lajittelu tarkoittaa periaatteessa elementtien järjestämistä joko nousevassa järjestyksessä tai laskevassa järjestyksessä. Elementtien lajitteluun on saatavilla niin paljon lajittelualgoritmeja ja jokaisella algoritmilla on erilaisia tapoja lajitella, erilainen monimutkaisuus. Joten se riippuu tietystä skenaariosta ja elementtien lukumäärästä, mitä algoritmia tulisi käyttää. Lisäys on myös yksi yleisimmin käytetyistä lajittelualgoritmeista, joiden monimutkaisuus on O (n 2), ja se suoritetaan samalla tavalla kuin lajittelemme käsissämme olevat pelikortit. Tässä aiheessa aiomme oppia Java-kielen lisäyslajittelusta.
Kuinka lisäyslajittelu toimii Java-versiossa?
Ymmärretään lisäyslajittelun toiminta esimerkin avulla. Oletetaan, että on olemassa taulukko nimellä arr, jolla on alla mainitut elementit:
10 5 8 20 30 2 9 7
Vaihe # 1 - Lisäyslajittelu alkaa taulukon 2. elementillä, eli 5, ottaen huomioon itsessään lajitelman taulukon 1. elementti. Nyt elementtiä 5 verrataan 10: een, koska 5 on vähemmän kuin 10, joten 10 siirretään yhden asennon eteen ja 5 työnnetään ennen sitä.
Tuloksena oleva taulukko on nyt:
5 10 8 20 30 2 9 7
Vaihe 2 - Nyt elementtiä arr (2), eli 8 verrataan elementtiin arr (1), eli 10. Koska 8 on pienempi kuin edellinen elementti 10, sitä siirretään askeleen eteenpäin asennostaan ja sitten se on verrattuna 5. Koska 8 on suurempi kuin 5, niin se asetetaan sen jälkeen.
Sitten tuloksena oleva taulukko on:
5 8 10 20 30 2 9 7
Vaihe # 3 - Nyt elementtiä 20 verrataan 10: een, koska se on suurempi kuin 10, se pysyy paikoillaan.
5 8 10 20 30 2 9 7
Vaihe 4 - elementtiä 30 verrataan 20: een, ja koska se on suurempi kuin 20, muutoksia ei tehdä ja taulukko pysyy sellaisenaan. Nyt taulukko olisi
5 8 10 20 30 2 9 7
Vaihe 5 - Elementtiä 2 verrataan 30: een, koska se on pienempi kuin 30, sitä siirretään yksi kohta eteenpäin, sitten sitä verrataan kohtaan 20, 10, 8, 5, yksi kerrallaan ja kaikki elementit siirretään 1 asentoon eteenpäin ja 2 lisätään ennen 5: tä.
Tuloksena oleva taulukko on:
2 5 8 10 20 30 9 7
Vaihe 6 - elementtiä 9 verrataan 30: een, koska sitä on pienempi kuin 30, sitä verrataan 20: een, 10: een yksitellen ja elementti siirtyy 1 aseman eteenpäin ja 9 lisätään ennen 10 ja 8. Tuloksena oleva taulukko on:
2 5 8 9 10 20 30 7
Vaihe 7 - elementtiä 7 verrataan 30: een, ja koska se on pienempi kuin 30, sitä verrataan 30, 20, 10, 9, 8: een ja kaikkia elementtejä siirretään yksi sijainti eteenpäin yksi kerrallaan ja 7 lisätään ennen 8 Tuloksena oleva taulukko muuttuisi:
2 5 7 8 9 10 20 30
Tällä tavalla kaikki taulukon elementit lajitellaan lisäyslajittelulla aloittamalla vertailu edelliseen elementtiin.
Esimerkkejä lisäyslaitteiden toteuttamisesta Java-sovelluksessa
Lisäyslajittelu Java-sovelluksessa on yksinkertainen lajittelualgoritmi, joka sopii kaikkiin pieniin tietojoukkoihin.
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);
)
)
lähtö:
12 15 18 21 23 52 61
Selitys:
Yllä olevassa Lisäyslajittelu-ohjelmassa insertionSort () -toimintoa käytetään alkuperäisen taulukon elementtien lajitteluun. Lajittelu alkaa toisesta elementistä, koska ensimmäinen elementti pitää lajitelluna sinänsä. J-silmukka alkaa siis taulukon hakemistosta 1. 'i' on muuttuva hakemisto, joka seuraa indeksiä juuri ennen j: tä arvon vertaamiseksi. ' avain 'on muuttuja, jolla on nykyisen elementin arvo, joka on tarkoitus järjestää lajiteltuun asentoon. kun taas () -silmukka suoritetaan, jos nykyinen arvo on pienempi kuin vasen arvo, jotta elementtien siirtäminen voidaan käsitellä ja nykyisen elementin lisääminen lopussa oikeaan asentoon voidaan suorittaa. printArray () -toimintoa käytetään lajitellyn taulukon lopulliseen tulostamiseen.
1. Paras tapaus
Lisäyslajittelussa paras tapaus olisi, kun kaikki taulukon elementit on jo lajiteltu. Joten kun mitä tahansa elementtiä verrataan sen vasempaan elementtiin, se on aina suurempi, joten elementtien siirtymistä ja asettamista ei käsitellä. Tässä tapauksessa parhaan tapauksen monimutkaisuus olisi lineaarinen, ts. O (n).
2. Pahin tapaus
Yllä olevassa lisäyskoodijärjestyksessä pahin tapaus olisi, kun taulukko on päinvastaisessa järjestyksessä, joten joka kerta kun elementtiä verrataan sen vasempaan elementtiin, se on aina pienempi ja sitä verrataan sitten kaikkiin tapahtuviin ja siirtäviin prosessointielementteihin. ja lisäys tehdään. Tässä tapauksessa lisäyslajittelun monimutkaisuus on O (n 2).
3. Keskimääräinen tapaus
Jopa keskimääräisessä tapauksessa lisäyslajittelulla on O (n 2) monimutkaisuus, jossa jotkut elementit eivät vaadi siirtymistä, kun taas jotkut elementit siirtyvät sijainnistaan ja lisäys oikeaan asentoon suoritetaan.
4. Paras käyttö
Lisäyslajittelu on parasta käyttää, kun taulukon koko ei ole kovin suuri tai lajitellaan vain pieni määrä elementtejä, joissa melkein kaikki elementit on lajiteltu ja vain joitain muutoksia on tehtävä. Lisäyslajittelu on yksi nopeimmista algoritmeista pienikokoisille ryhmille, jopa nopeampaa kuin Pikalajittelu. Itse asiassa quicksort käyttää lisäyslajittelua lajitellessaan taulukon pieniä osia.
johtopäätös
Yllä oleva selitys osoittaa selvästi, että lisäyslajittelu toimii ja toteutetaan Java-sovelluksessa. Myös muilla ohjelmointikielellä lisäyslajittelun logiikka pysyy samana, vain syntaksi muuttuu. Ennen lajittelualgoritmin käyttöönottoa on erittäin tärkeää analysoida skenaario, jossa lajittelu on tehtävä, koska kaikki lajittelualgoritmit eivät sovi kaikkiin skenaarioihin.
Suositellut artikkelit
Tämä on opas Lisäyslajittelu Java-sovellukseen. Tässä keskustellaan siitä, miten lisäyslajittelu toimii Java-sovelluksessa, esimerkkeinä Java-lisäyslajittelun toteuttamiseksi. Saatat myös katsoa seuraavia artikkeleita saadaksesi lisätietoja -
- Neliöjuuri Java
- BorderLayout Java-sovelluksessa
- Käänteinen numero Java
- StringBuffer Java -sovelluksessa
- Neliöjuuri PHP: ssä
- Neliöjuuri JavaScript-muodossa
- Opas kuuteen suosituimpaan lajittelualgoritmiin Pythonissa