Introducere

Salut! eu sunt Sanjulași, în acest ghid, sper să vă învăț puțin despre algoritmul de sortare a inserției, inclusiv:

  • Ce este sortarea Insertion?
  • De ce este importantă inserția?
  • Performanța sortării prin inserție
  • Cum funcționează sortarea prin inserție?
  • Implementarea Java a sortării inserției

Să începem!

Ce este sortarea Insertion?

Este un algoritm simplu de sortare care sortează o matrice câte un articol la un moment dat.

De ce este importantă inserția?

Sortarea prin inserție are mai multe avantaje, printre care:

  • Simplitatea pură a algoritmului.
  • Ordinea relativă a articolelor cu taste egale nu se modifică.
  • Capacitatea de a sorta o listă pe măsură ce este primită.
  • Eficient pentru seturi de date mici, mai ales în practică decât alți algoritmi pătratici – adică O (n²).
  • Necesită doar o cantitate constantă de spațiu de memorie suplimentar – O (1).

Performanța sortării prin inserție

  • Performanța în cel mai rău caz al sortării inserției este comparațiile și swap-urile O (n²).
  • Performanța în cel mai bun caz este comparațiile O (n) și swapurile O (1).
  • Performanța medie a cazului este O (n²) comparații și swap-uri.

Cum funcționează sortarea prin inserție?

În fiecare iterație, sortarea prin inserție compară elementul curent cu elementul următor și determină dacă elementul curent este mai mare decât cel cu care a fost comparat.

Dacă aceasta este Adevărat, apoi lasă elementul la locul său și trece la următorul element. Dacă este fals, apoi își găsește poziția corectă în matricea sortată și o mută în acea poziție mutând toate elementele care sunt mai mari în matricea sortată într-o poziție înainte.

Implementarea Java a sortării inserției

PS – Încearcă mai întâi să-l implementezi singur!


Felicitări!!! Acum ați absorbit cunoștințele de bază, dar esențiale, despre modul în care funcționează Sortarea prin inserție.

Pentru referință sau raportarea problemelor referitoare la codul de mai sus, utilizați următorul GitHub Gist public legătură.


Sper că acest lucru a fost de ajutor. Mulțumesc pentru lectură! 🙂