Ez a blog az oszd meg és hódítsd megközelítésen alapszik. Az Egyesítés rendezés egy „oszd meg és meghódítsd” algoritmus, ahol a problémát részproblémákra osztják, majd egyesítik a megoldás meghódítására. Ez a blog a Merge-en Rendezés részletesen bemutatja az alábbi témákat -
- Mi az a Merge Sort a Pythonban?
- Az Oszd és hódíts megközelítés
- Merge Sort megvalósítása Pythonban
- Folyamatábra a Merge Sort megvalósításához
- Előnyök és használat
Mi az a Merge Sort a Pythonban?
Az Összevonás rendezése az osztás és meghódítás algoritmuson alapszik, ahol a bemeneti tömböt két részre osztják, majd külön rendezik és visszaolvadnak a megoldás eléréséhez. Az egyesítés () egyesítésével a rendezés összevonható .
Az Oszd és hódíts megközelítés
- A tömböt felére osztjuk, és a folyamatot mindkét féllel megismételjük, amíg mindkét fele 1 vagy 0 méretű lesz.
- Az 1-es méretű tömböt triviálisan rendezik.
- Most a két rendezett tömböt egy nagy tömbbe egyesítik. És ez addig folytatódik, amíg az összes elem össze nem kerül és a tömb rendezésre nem kerül.
Itt olvasható az egyesítés rendezése, hogy tisztázza a képet az Ön számára
Bemeneti tömb = [3,1,4,1,5,9,2,6,5,4]
egyesítés rendezés c ++ példa
Most térjünk át a megvalósításra.
Merge Sort megvalósítása Pythonban
def mergeSort (nlist): print ('Hasadás', nlist), ha len (nlist)> 1: közepes = len (nlist) // 2 baloldali = nlist [: közepes] jobboldali = nlist [közepes:] mergeSort (baloldali) mergeSort (jobboldal) i = j = k = 0, míg iKimenet:
$ python main.py
(„Hasadás”, [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
(„Hasadás”, [3, 1, 4, 1, 5])
(’Hasadás’, [3, 1])
(„Hasadás”, [3])
(’Összeolvad’, [3])
(„Hasadás”, [1])
(’Összeolvad’, [1])
(’Összeolvad’, [1, 3])
(„Hasadás”, [4, 1, 5])
(„Hasadás”, [4])
(’Összeolvad’, [4])
(’Hasadás’, [1, 5])
(„Hasadás”, [1])
(’Összeolvad’, [1])
(„Hasadás”, [5])
(’Összeolvad’, [5])
(’Összeolvad’, [1, 5])
(’Összeolvad’, [1, 4, 5])
(’Összeolvad’, [1, 1, 3, 4, 5])
(„Hasadás”, [9, 2, 6, 5, 4])
(’Hasadás’, [9, 2])
(„Hasadás”, [9])
(’Összeolvad’, [9])
(„Hasadás”, [2])
(’Összeolvad’, [2])
(’Összeolvad’, [2, 9])
(„Hasadás”, [6, 5, 4])
(„Hasadás”, [6])
(’Összeolvad’, [6])
(„Hasadás”, [5, 4])
(„Hasadás”, [5])
(’Összeolvad’, [5])
(„Hasadás”, [4])
(’Összeolvad’, [4])
(’Összeolvad’, [4, 5])
(’Összeolvad’, [4, 5, 6])
(’Összeolvad’, [2, 4, 5, 6, 9])
(’Összeolvad’, [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]
milyen korlátok vannak az sql-benFolyamatábra a Merge Sort megvalósításához
A Merge Sort előnyei és használata
A legtöbb más algoritmus rosszul működik szekvenciális adatstruktúrákkal, például fájlokkal és összekapcsolt listákkal. Ezekben a struktúrákban a véletlenszerű elemhez való hozzáférés lineáris, nem pedig állandó állandó időt vesz igénybe. Az egyesítés rendezésének jellege pedig megkönnyíti és gyorsá teszi az ilyen adatstruktúrákat.Az egyesítés rendezésének egyik legjobb jellemzője az alacsony összehasonlíthatóság. O (n * log (n)) összehasonlítást tesz lehetővé, de az állandó tényező jó a quicksorthoz képest, ami akkor hasznos, ha az összehasonlító függvény lassú művelet.Ezenkívül az egyesítés rendezés megosztása és meghódítása megközelítés megkönnyíti a párhuzamos feldolgozást.
Ezzel véget értünk ennek a blognak a „Hogyan lehet megvalósítani a Merge Sort Python-ban” c. Remélem, hogy a tartalom némi értéket adott hozzá a Pythonban való ismereteihez. Ha részletes ismereteket szeretne szerezni a Pythonról és annak különböző alkalmazásokról, regisztrálhat élőben 24/7 támogatással és élethosszig tartó hozzáféréssel.