Home-theater-designers
A Beszúrás rendezés egy olyan technika, amely egy rendezett allistát használ, és folyamatosan hozzáad egy értéket a nem rendezett listától a teljes lista rendezéséig.
Az algoritmus az első listaelemmel kezdődik, mint rendezett allista. Ezután összehasonlítja a következő számot az elsővel. Ha nagyobb, akkor az első indexbe kerül. Ellenkező esetben az indexben marad.
A harmadik értéket ezután összehasonlítják a másik kettővel, majd beillesztik a megfelelő indexbe. Ez a folyamat addig tart, amíg a teljes lista rendezésre nem kerül.
Közelebbről a beillesztés rendezése
Lehet, hogy a fenti leírás nem volt értelmes számodra. Egy példa segít jobban megérteni.
Tegyük fel, hogy van egy listája: [39, 6, 2, 51, 30, 42, 7].
Az algoritmus a 39 -et azonosítja a rendezett allista első értékeként. Az értékelés ezután a második pozícióba lép.
Kapcsolódó: Dinamikus programozás: példák, gyakori problémák és megoldások
A 6 -ot ezután a 39 -gyel hasonlítjuk össze. Mivel a 6 kevesebb, mint 39, a 6 beillesztésre kerül az első pozícióba, a 39 pedig a másodikba. Az új lista sorrendje az első menet után van:
[6, 39, 2, 51, 30, 42, 7]
Az értékelés most a harmadik pozícióba kerül. A 2. ábrát összehasonlítjuk az utolsó két számmal, majd behelyezzük a megfelelő pozícióba. Az új lista sorrendje a második menet után van:
[2, 6, 39, 51, 30, 42, 7]
A harmadik lépésnél a lista sorrendje a következő:
[2, 6, 39, 51, 30, 42, 7]
A folyamat addig ismétlődik, amíg a teljes lista rendezésre nem kerül.
Tekintse meg az alábbi diagramot, amely összefoglalja ezeket a műveleteket:
Algoritmus elemzés
A beszúrási rendezés időbeli összetettsége O (n2), akárcsak buborék rendezés . Az összehasonlítások száma a legrosszabb esetben az összes egész szám összege 1-től (n-1), ami másodfokú összeget eredményez.
Kód implementáció
Az alábbi Python és Java kód bemutatja, hogyan valósíthatja meg a Beszúrás rendezési módszert.
Piton:
def insertionSort(mylist):
for step in range(1, len(mylist)):
current_element = mylist[step]
position = step
while position > 0 and mylist[position - 1] > current_element:
mylist[position] = mylist[position - 1]
position = position - 1
mylist[position] = current_elementJáva:
void insertionSort(int[] myarray) {
int n = myarray.length;
for (int x = 1; x int key = myarray[x];
int y = x-1;
while ( (y > -1) && ( myarray [y] > key ) ) {
myarray [y+1] = myarray [y];
y--;
}
myarray[y+1] = key;
}
} Jobb kódolás pszeudokóddal
A fenti kódpéldákat pszeudokód nélkül adtuk meg, amelyre hivatkozva más nyelveken is megírhatja ezt az algoritmust. A legtöbb programozó (a szerzőt is beleértve) szeret a billentyűzetükhöz futni, miután „suttogva” elmondták a program működéséről.
Ez a megközelítés sajnos hajlamos a hibákra, mivel a program logikája bonyolultabbá válik. Hogyan szeretné szintre emelni programozási játékát az álkód használatának elsajátításával?
Részvény Részvény Csipog Email Mi az álkód és hogyan tesz jobb fejlesztővé?Nehezen tanul programozni? Ismerje meg a kódot az álkód tanulásával. De mi az álkód és valóban segíthet?
Olvassa tovább Kapcsolódó témák- Programozás
- Jáva
- Piton
- Kódolási oktatóanyagok
Jerome a MakeUseOf munkatársa. A programozásról és a Linuxról szóló cikkekkel foglalkozik. Ő is kriptorajongó, és mindig figyelemmel kíséri a kriptoipart.
ingyenes e -könyvek letöltése és olvasásaTovábbi Jerome Davidson
Iratkozzon fel hírlevelünkre
Csatlakozz hírlevelünkhöz, ahol technikai tippeket, véleményeket, ingyenes e -könyveket és exkluzív ajánlatokat találsz!
Feliratkozáshoz kattintson ide