Bevezetés
Szia! Sanjula vagyok, és ebben az útmutatóban remélem, hogy megtanítok egy kicsit az Insertion Sort algoritmusra, beleértve:
- Mi az a beszúrás?
- Miért fontos a beszúrás rendezése?
- A beszúrási rendezés teljesítménye
- Hogyan működik a Beszúrás rendezése?
- Java Az Insertion sort végrehajtása
Kezdjük el!
Mi az a beszúrás?
Ez egy egyszerű rendezési algoritmus, amely egy tömböt egyenként rendez.
Miért fontos a beszúrás rendezése?
A beillesztés rendezésének számos előnye van, többek között:
- Az algoritmus tiszta egyszerűsége.
- Az egyenlő kulcsú elemek relatív sorrendje nem változik.
- A lista rendezésének lehetősége annak fogadásakor.
- Hatékony kis adathalmazoknál, különösen a gyakorlatban, mint más másodfokú algoritmusok - azaz O (n²).
- Csak állandó mennyiségű további memóriaterületre van szükség - O (1).
A beszúrási rendezés teljesítménye
- A beillesztés rendezésének legrosszabb esete az O (n²) összehasonlítás és a swap.
- A legjobb eset az O (n) összehasonlítás és az O (1) swap.
- Az átlagos eset teljesítmény O (n²) összehasonlítás és csereügylet.
Hogyan működik a Beszúrás rendezése?
Minden egyes iterációban a beszúrás rendezése összehasonlítja az aktuális elemet a következő elemmel és meghatározza, hogy az aktuális elem nagyobb-e, mint amihez hasonlították.
Ha ez igaz , akkor az elemet a helyén hagyja, és továbblép a következő elemre. Ha hamis , akkor megtalálja a helyes helyzetét a rendezett tömbben, és áthelyezi abba a helyzetbe azáltal, hogy az összes rendezett tömbben nagyobb elemet egy pozícióval elé tolja.
Java Az Insertion sort végrehajtása
PS - Próbáld meg először saját erőből megvalósítani!
Gratulálunk!!! Most már elsajátította az alapvető, de alapvető tudnivalókat a Insertion Sort működéséről.
A fenti kóddal kapcsolatos referencia- vagy jelentési problémákhoz használja a következő nyilvános GitHub Gist linket.
Remélem, ez hasznos volt. Köszönöm, hogy elolvasta! :)