Lisäyslajittelu on yksinkertainen lajittelualgoritmi, joka toimii samalla tavalla kuin lajittelemme käsissämme olevat pelikortit.
Python-ohjelma lisäyslajitteluun
InsertionSort-funktio ottaa syötteeksi taulukon arr. Se laskee ensin taulukon pituuden (n). Jos pituus on 0 tai 1, funktio palauttaa välittömästi, koska taulukko, jossa on 0 tai 1 alkio, katsotaan jo lajiteltuna.
Jos taulukossa on useampi kuin yksi elementti, funktio etenee iteroimaan taulukon yli alkaen toisesta elementistä. Se ottaa nykyisen elementin (jota kutsutaan avaimeksi) ja vertaa sitä sitä edeltävien taulukon lajiteltujen osien elementteihin. Jos avain on pienempi kuin lajitellun osan elementti, funktio siirtää elementin oikealle luoden avaimelle tilaa. Tätä prosessia jatketaan, kunnes avaimen oikea asento löytyy, ja sitten se asetetaan tähän asentoon.
Esitetty esimerkki havainnollistaa lajitteluprosessia lisäyslajittelualgoritmilla. Alkutaulukko [12, 11, 13, 5, 6] alistetaan insertionSort-funktiolle. Lajittelun jälkeen taulukon tulee olla [5, 6, 11, 12, 13]. Koodi tulostaa lajitellun taulukon lopullisena tulosteena.
käänteinen merkkijono java
Python
lajitteluun arraylist java
def> insertionSort(arr):> >n>=> len>(arr)># Get the length of the array> > >if> n <>=> 1>:> >return> # If the array has 0 or 1 element, it is already sorted, so return> >for> i>in> range>(>1>, n):># Iterate over the array starting from the second element> >key>=> arr[i]># Store the current element as the key to be inserted in the right position> >j>=> i>->1> >while> j>>> and> key # Move elements greater than key one position ahead arr[j+1] = arr[j] # Shift elements to the right j -= 1 arr[j+1] = key # Insert the key in the correct position # Sorting the array [12, 11, 13, 5, 6] using insertionSort arr = [12, 11, 13, 5, 6] insertionSort(arr) print(arr)> |
>
>
Lähtö:
Sorted array is: [5, 6, 11, 12, 13]>
Aika monimutkaisuus: O(N2)
Aputila: O(1)
Katso täydellinen artikkeli aiheesta Lisäys Lajittele Lisätietoja!