Sortering af arrays er en af de mest almindelige operationer, som en Java-begynder bør vide, hvordan man gør. Selvom arrays ikke altid er den mest bekvemme måde at arrangere data på, og dette gælder for det meste små tal, har konceptet bag array-sortering tonsvis af applikationer inden for kompleks software og datavidenskab. I dette indlæg vil vi se nærmere på, hvad indsættelsessort er. Vi inkluderede nogle eksempler og øvelsesproblemer for at hjælpe dig med at få styr på dette koncept.
Hvad er indsættelsessortering?
Dybest set er insertion sort en algoritme, som udviklere bruger til at organisere strenge med små tal. Den deler alle værdier i to stakke - en sorteret og en usorteret. Et efter et bliver tallene i den "usorterede" stak plukket ud og sat i den rigtige rækkefølge. Lad os se nærmere på input og output af indsættelsessort:
Input: en matrix A med usorterede numeriske elementer: A[0,1, n, n-2...].
Output: et array, der indeholder de samme tal, men fuldt sorteret. Denne omtales typisk som B: B[0]B[1]...B[n-1].
Der er en håndfuld måder at bruge indsættelsessortering på - her er de mest populære:
Bemærk: hvis du har et tomt array eller en singleton, anses disse for at være sorteret som standard.
Forstå Theory of Insertion Sort
Før vi udforsker koden bag indsættelsessortering, lad os nedbryde algoritmen ved hjælp af ikke-teknisk sprog. Fordi vi vil vise koden til sortering i stigende rækkefølge, giver det mening at forklare algoritmen trin for trin i dette indlæg. Trin 1. Iteration mellem arr[1]og arr[n]hvor ner en numerisk værdi, der typisk er mindre end 10. Trin 2. Sammenlign det element, du valgte (kendt som key) med det foregående tal i sekvensen ved hjælp af sort()metoden. Trin 3. Hvis alle elementerne er mindre end deres efterfølgere, gentag sammenligningen, indtil du finder en større værdi. Trin 4. Byt en større værdi en position ud over den mindre for at skabe en ordnet sekvens. Trin 5. Gentag processen, indtil du får en sorteret streng af tegn
Sortering af primitive arrays
Da algoritmen er en af de mest ligetil Java-operationer, burde selv helt nybegyndere ikke have store problemer med at implementere den. Her er en trin-for-trin guide til sortering af et array
1. Angiv et array til sorteringen
Til at starte med, lad os oprette en række værdier, som vi senere vil vise ved hjælp af Java. For at bruge indsættelsessortering skal du oprette en matrix. Til det, brugint[]
int[] arrayA = {10, 14, 20, 30};
2. Brug sort_arr til at implementere algoritmen
Sort_arr-metoden er en af de mest almindelige måder at implementere indsættelsessortering på. I praksis ser det sådan ud:
for(int i=0; i< sort_arr.length; ++i){
int j = i;
3. Opret en loop og en iterator
Ved at bruge en løkke i indsættelsessorteringsalgoritmen behøver udviklere ikke at gentage logikken for hvert element. Selvom det virker komplekst at lave loops, er det ret simpelt - her er et eksempel:
for(int i=0; i< sort_arr.length; ++i){
Nu hvor du har en fungerende loop, er det tid til at oprette en iterator, der vil sortere alle elementerne i den ønskede rækkefølge. Fra nu af vil vi referere til iteratoren som " j".
int j = i;
4. Oprettelse af en "while loop"
Når det kommer til indsættelsessortering, er en "mens"-løkke essentiel for et nyt, sorteret array. For at konfigurere det til en sortering i stigende rækkefølge skal en udvikler overholde to betingelser:
Værdien tildelt til j skal være større end 0
Den værdi, der tildeles, j-1skal være større end jindekset
Så snart begge betingelser i while-løkken er sande, vil arrayets nøgleværdi svare til indekset j.
5. Sortering af arrayet
Når du har konfigureret while-løkken, vil værdierne jog j-1blive byttet om, indtil en eller begge betingelser i while-løkken mislykkes. Tilsvarende vil sorteringen blive gentaget for hver værdi i for-løkken, indtil for-løkke-betingelserne også fejler. Her er, hvordan processen med indsættelsessortering fungerer i praksis:
Selvom det er vigtigt at forstå matematikken bag indsættelsessortering, når det kommer til softwareudvikling i det virkelige liv, vil du sortere ArrayLists meget mere end sekvenser i primitive arrays. Her er en trin-for-trin guide til sortering af en ArrayList:
Opret en ny Elementklasse for de elementer, der hører til samlingen.
public class Element {
private int id;
public Element(int id) {
this.id = id;
}
Inden for en samling er der en compareTo()metode - vi vil bruge denne til at sammenligne id'erne for to elementer.
public int compareTo(Element element) {
int res = 0;
if (this.id < element.getId()) {
res = -1;
}
if (this.id > element.getId()) {
res = 1;
}
return res;
}
}
Anvend algoritmen og opret nogle sløjfer for at sortere objekterne i en ArrayListi stedet for at sammenligne dem.
public static void insertionSortArrayList(List<element> list) {
for (int j = 1; j < list.size(); j++) {
Element current = list.get(j);
int i = j-1;
while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
list.set(i+1, list.get(i));
i--;
}
list.set(i+1, current);
}
}
Du kan også tilføje flere elementer til den ArrayList, som vist nedenfor:
List<element> list = new ArrayList<>();
// Create elements w/ IDs 0-24
for (int i = 0; i < 25; i++) {
list.add(new Element(i));
}
// To use insertion sort, shuffle the values
Collections.shuffle(list);
Nu er det tid til at sortere:
// This helps print values before sorting
list.forEach(e -> System.out.print(e.getId() + ", "));
// Sort the list
insertionSortArrayList(list);
System.out.println();
// Display a sorted array
list.forEach(e -> System.out.print(e.getId() + ", "));
Lad os nu sammenligne input og output for at sikre, at vi ikke lavede fejl. Her er sammenligningen af strengen, vi brugte som eksempel.
Nu hvor du har styr på denne sorteringsalgoritme, er det tid til at prøve dine teoretiske og praktiske færdigheder. Teoriquiz #1 Du får et array [1, 4, 6, 8] og tilføjer et nyt element n = 7 til det. Hvor mange sammenligninger skal du lave for at få en sorteret talrække? Angiv den endelige værdi af indeks n i arrayet. Teoriquiz #2 Ved en jobsamtale beder en teamleder dig om at bevise, at sorteringsindsættelse er en ineffektiv metode. Givet en talstreng på [0, 3, 6, 8, 9], hvad skal rækkefølgen af din inputsekvens være for at maksimere den køretid, der kræves til sortering? Øvelsesproblem Sorter [0, 1, 4, 5, 2, 3, 7, 9, 8] arrayet i dets stigende rækkefølge ved hjælp af indsættelsessortering for Java.
Konklusion
Den største udfordring ved at forstå indsættelsessortering er at forstå, hvordan processen fungerer. Når du først har styr på det, er det et stykke kage at omdanne skabelonen til kode. Så længe du øver og gentager relevante praksisproblemer over tid, vil du hurtigt forbedre din indsættelsessorteringshastighed.
Lad os se nærmere på input og output af indsættelsessort:
GO TO FULL VERSION