Alt hvad du behøver at vide om Insertion Sort algoritme

Introduktion

Hej! Jeg er Sanjula, og i denne vejledning håber jeg at lære dig en smule om Insertion Sort-algoritmen, herunder:

  • Hvad er indsættelsessortering?
  • Hvorfor er det vigtigt at indsætte?
  • Udførelse af indsættelsessortering
  • Hvordan fungerer sortering af indsættelse?
  • Java-implementering af indsætningssortering

Lad os komme igang!

Hvad er indsættelsessortering?

Det er en simpel sorteringsalgoritme, der sorterer en matrix et element ad gangen.

Hvorfor er det vigtigt at indsætte?

Indsættelsessortering har flere fordele, herunder:

  • Den rene enkelhed af algoritmen.
  • Den relative rækkefølge på emner med lige nøgler ændres ikke.
  • Evnen til at sortere en liste, når den modtages.
  • Effektiv til små datasæt, især i praksis end andre kvadratiske algoritmer - dvs. O (n²).
  • Det kræver kun en konstant mængde ekstra hukommelsesplads - O (1).

Udførelse af indsættelsessortering

  • Worst-case ydeevne ved indsætningssortering er O (n²) sammenligninger og swaps.
  • Bedste ydeevne er O (n) sammenligninger og O (1) swaps.
  • Gennemsnitlig case-ydeevne er O (n²) sammenligninger og swaps.

Hvordan fungerer sortering af indsættelse?

I hver iteration sammenligner indsættelsessorter det aktuelle element med det næste element og bestemmer, om det aktuelle element er større end det, det blev sammenlignet med.

Hvis dette er sandt , efterlader det elementet på sin plads og går videre til det næste element. Hvis den er falsk , finder den sin korrekte position i det sorterede array og flytter det til denne position ved at flytte alle de elementer, der er større i det sorterede array til en position foran.

Java-implementering af indsætningssortering

PS - Prøv først at implementere det alene!

Tillykke!!! Du har nu absorberet den grundlæggende, men vigtige viden om, hvordan indsættelsessortering fungerer.

Brug følgende offentlige GitHub Gist-link til reference- eller rapporteringsproblemer vedrørende ovenstående kode.

Håber dette var nyttigt. Tak for læsningen! :)