Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
Dôležitá poznámka: Pseudokód je určený ako reprezentácia na vysokej úrovni, nie priamo spustiteľná. Zameriava sa na * logiku * algoritmu. Skutočná implementácia kódu sa bude líšiť v závislosti od programovacieho jazyka a konkrétnych požiadaviek.
1. Bublinové triedenie
* koncept: Opakovane postupuje v zozname, porovnáva susedné prvky a vymení ich, ak sú v nesprávnom poradí. Ťažšie prvky „bublina“ až do konca.
* pseudocode:
`` `
Postup bublinsort (zoznam:pole položiek)
n =dĺžka (zoznam)
pre i =0 až n-1 do
pre j =0 až n-i-1 do
Ak zoznam [j]> zoznam [j+1] potom
Zoznam swap [j] a zoznam [j+1]
skončiť
skončiť
skončiť
koncový postup
`` `
* Účinnosť:
* Najlepší prípad: O (n) (keď je zoznam už triedený. Optimalizovaná verzia to dokáže zistiť.)
* Priemerný prípad: O (n
2
)
* Najhorší prípad: O (n
2
)
* Vesmírna zložitosť: O (1) (zoradenie na mieste)
* implementácia: Veľmi jednoduché implementácia.
* Prípady použitia: Väčšinou vzdelávacie. Nie je vhodné pre veľké súbory údajov z dôvodu slabého výkonu. Môže byť užitočné pre malé, takmer zoradené zoznamy, ak sú optimalizované.
2. Výber triedenia
* koncept: Nájde minimálny prvok v netriedenej časti zoznamu a vymení ho prvkom na začiatku netriedenej časti.
* pseudocode:
`` `
výber postupu (zoznam:pole položiek)
n =dĺžka (zoznam)
pre i =0 až n-1 do
// Nájdite index minimálneho prvku v netriedenej časti
min_index =i
pre j =i+1 až n-1 do
Ak zoznam [j]
skončiť
skončiť
// vymeniť nájdený minimálny prvok za prvý prvok
Zoznam swap [i] a zoznam [min_index]
skončiť
koncový postup
`` `
* Účinnosť:
* Najlepší prípad: O (n
2
)
* Priemerný prípad: O (n
2
)
* Najhorší prípad: O (n
2
)
* Vesmírna zložitosť: O (1) (zoradenie na mieste)
* implementácia: Relatívne jednoduché.
* Prípady použitia: V niektorých prípadoch funguje o niečo lepšie ako triedenie bubliny, ale stále nie je vhodný pre veľké súbory údajov. Počet swapov je obmedzený na O (n), čo môže byť užitočné, ak sú pamäťové zápisy drahé.
3. Inzercia zoradenie
* koncept: Zostavuje zoradený zoznam jeden prvok naraz. Iteruje cez vstupné údaje, odstraňuje jeden prvok súčasne, nájde správnu pozíciu v zoradenom zozname a vloží ich tam.
* pseudocode:
`` `
Postup insertionsort (zoznam:pole položiek)
n =dĺžka (zoznam)
pre i =1 až n-1 do
key =zoznam [i]
j =i - 1
// Presuňte prvky zoznamu [0..i-1], ktoré sú väčšie ako kľúč,
// na jednu pozíciu pred ich súčasnou pozíciou
zatiaľ čo j> =0 a zoznam [j]> kľúč
Zoznam [j+1] =zoznam [j]
j =j - 1
skončiť
Zoznam [j+1] =kľúč
skončiť
koncový postup
`` `
* Účinnosť:
* Najlepší prípad: O (n) (keď je zoznam už triedený)
* Priemerný prípad: O (n
2
)
* Najhorší prípad: O (n
2
)
* Vesmírna zložitosť: O (1) (zoradenie na mieste)
* implementácia: Jednoduché a efektívne pre malé súbory údajov alebo takmer zoradené údaje.
* Prípady použitia: Dobré pre malé zoznamy alebo keď očakávate, že vstupné údaje budú väčšinou triedené. Je to tiež algoritmus * online *, čo znamená, že môže zoradiť zoznam tak, ako ho prijíma.
4. Zlúčiť triedenie
* koncept: Algoritmus rozdelenia a konania. Rozdeľuje zoznam na menších sublistov, rekurzívne triedia subristov a potom ich spája späť k sebe.
* pseudocode:
`` `
Postup Mergesort (zoznam:pole položiek)
n =dĺžka (zoznam)
ak n <=1 potom
návratový zoznam // už zoradený
skončiť
// Rozdeľte zoznam na dve polovice
Mid =N / 2
ľavicový zoznam =zoznam [0 až Mid-1]
RightList =Zoznam [MID až N-1]
// rekurzívne triedte každú polovicu
ľavicový zoznam =mergesort (ľavý zoznam)
rightlist =mergesort (rightlist)
// Zlúčiť triedené polovice
návrat zlúčenia (ľavý zoznam, pravý zoznam)
koncový postup
Postup zlúčenie (ľavý zoznam:pole položiek, pravý zoznam:pole položiek)
Výsledky =nové pole
Zatiaľ čo ľavý zoznam nie je prázdny a pravý zoznam nie je prázdny
Ak ľavica [0] <=pravý zoznam [0] potom
Pripojte ľavicu [0] na výsledky zoznamu
Odstráňte ľavý zoznam [0] z ľavého zoznamu
inak
Príspevok pravého zoznamu [0] na výsledky
Odstrániť pravý zoznam [0] z pravého zoznamu
skončiť
skončiť
// Pripojte všetky zostávajúce prvky z ľavého zoznamu alebo pravého zoznamu
Pripojte všetky zostávajúce prvky ľavicového zoznamu na výsledky
Pripojte všetky zostávajúce prvky RightList na výsledky zoznamu
zoznam výsledkov návratu
koncový postup
`` `
* Účinnosť:
* Najlepší prípad: O (n log n)
* Priemerný prípad: O (n log n)
* Najhorší prípad: O (n log n)
* Vesmírna zložitosť: O (n) (vyžaduje ďalší priestor na zlúčenie)
* implementácia: Zložitejšie ako predchádzajúce algoritmy, ale poskytuje dobrý výkon pre veľké súbory údajov.
* Prípady použitia: Vhodný na triedenie veľkých zoznamov, kde je dôležitý konzistentný výkon.
5. Rýchle triedenie
* koncept: Tiež algoritmus priepasti a konania. Vyberie prvok ako otočenie a rozdelí dané pole okolo vybraného čapu.
* pseudocode:
`` `
postup Quicksort (zoznam:pole položiek, nízka:int, vysoká:int)
Ak je nízka
p =oddiel (zoznam, nízky, vysoký)
// osobitne zoradiť prvky pred oddielom a po oddiele
Quicksort (List, Low, P-1)
Quicksort (zoznam, p+1, vysoký)
skončiť
koncový postup
Oddiel v postupe (zoznam:pole položiek, Low:Int, High:Int)
pivot =zoznam [vysoké] // Vyberte posledný prvok ako pivot
i =nízky - 1 // index menšieho prvku
pre j =nízka až vysoká 1
// Ak je aktuálny prvok menší alebo rovný Pivot
Ak zoznam [j] <=pivot potom
i =i + 1 // Index prírastkov menšieho prvku
Zoznam swap [i] a zoznam [j]
skončiť
skončiť
Zoznam swap [i + 1] a zoznam [High]
návrat i + 1
koncový postup
`` `
* Účinnosť:
* Najlepší prípad: O (n log n) (keď je pivot vždy medián)
* Priemerný prípad: O (n log n)
* Najhorší prípad: O (n
2
) (Keď je pivot vždy najmenším alebo najväčším prvkom)
* Vesmírna zložitosť: O (log n) (v dôsledku rekurzívnych hovorov môže byť v najhoršom prípade O (n))
* implementácia: V praxi sa vo všeobecnosti rýchlo rýchlo stane, ale jeho najhorší výkon môže byť problémom. Výber Pivot významne ovplyvňuje jeho výkon.
* Prípady použitia: Najrýchlejší triediaci algoritmus v praxi pre veľké súbory údajov. Je však potrebné zvážiť jeho najhorší výkon. Mnoho implementácií používa randomizáciu alebo iné techniky, aby sa predišlo najhoršiemu prípadu.
6. Halda triedenie
* koncept: Zostavuje maximálnu haldu (alebo haldu min.) Zo vstupných údajov a potom opakovane extrahuje koreňový prvok (najväčší alebo najmenší prvok) a umiestni ju na koniec triedeného poľa.
* pseudocode:
`` `
Procedúra Heapsort (zoznam:pole položiek)
n =dĺžka (zoznam)
// Zostavte maximálnu hromadu
pre i =n/2 - 1 až 0 do
Heapify (List, n, i)
skončiť
// jeden po druhom extrahovať prvok z haldy
pre i =n-1 až 0 do
Zoznam swap [0] a zoznam [i] // Presuňte aktuálny koreň do konca
// volajte max
Heapify (zoznam, i, 0)
skončiť
koncový postup
Postup hepapify (zoznam:pole položiek, n:int, i:int)
Najväčší =i // Inicializujte najväčšiu ako koreň
vľavo =2*i + 1
vpravo =2*i + 2
// Ak je ľavé dieťa väčšie ako koreň
ak je v ponuke
Najväčší =vľavo
skončiť
// Ak je správne dieťa doteraz väčšie ako najväčšie
Ak je právo
Najväčší =právo
skončiť
// ak najväčší nie je korene
Ak je najväčší! =Ja potom
Zoznam swap [i] a zoznam [najväčší]
// rekurzívne nahromadiť postihnutý čiastkový stromček
Heapy (List, n, najväčší)
skončiť
koncový postup
`` `
* Účinnosť:
* Najlepší prípad: O (n log n)
* Priemerný prípad: O (n log n)
* Najhorší prípad: O (n log n)
* Vesmírna zložitosť: O (1) (zoradenie na mieste)
* implementácia: Zložitejšie ako jednoduchšie algoritmy, ale zaručuje výkon O (n log N).
* Prípady použitia: Dobrá voľba, keď potrebujete zaručené O (n log n) výkon a triedenie na mieste, je žiaduce. Používa sa pri implementáciách prioritných frontov.
Súhrnná tabuľka efektívnosti
| Algoritmus Najlepší prípad Priemerný prípad Najhorší prípad Zložitosť priestoru
| ------------------- | ----------- | -------------- | ------------ | ------------------- |
| Triedenie bubliny O (n) | O (n
2
) | O (n
2
) | O (1) |
| Zoradiť výber | O (n
2
) | O (n
2
) | O (n
2
) | O (1) |
| Zoradiť vkladanie | O (n) | O (n
2
) | O (n
2
) | O (1) |
| Zlúčiť triedenie | O (n log n) | O (n log n) | O (n log n) | O (n) |
| Rýchle triedenie | O (n log n) | O (n log n) | O (n
2
) | O (log n) |
| Zoradenie haldy | O (n log n) | O (n log n) | O (n log n) | O (1) |
Kľúčové rozdiely v efektívnosti a implementácii:
* kvadratické vs. logaritmic: Algoritmy s O (n
2
) Účinnosť (bublina, výber, vloženie) sú vhodné iba pre malé súbory údajov. Algoritmy s účinnosťou O (n log N) (zlúčenie, rýchle, halda) sú oveľa efektívnejšie pre väčšie súbory údajov.
* Rozdeľte a dobyť: Zlúčiť zoradenie a rýchle zoradenie Použite stratégiu rozdelenia a konania, ktorá umožňuje efektívnejšie triedenie veľkých súborov údajov.
* triedenie na mieste: Bublinové triedenie, triedenie výberu, triedenie vloženia a triedenie haldy sú algoritmy triedenia na mieste, čo znamená, že nevyžadujú významnú ďalšiu pamäť. Zlúčenie si vyžaduje O (n) ďalšie miesto na zlúčenie. Rýchle triedenie vyžaduje O (log n) v priemere, ale O (n) priestor v najhoršom prípade v dôsledku rekurzívnych hovorov.
* stabilita: Algoritmus triedenia je * stabilný * Ak prvky s rovnakými hodnotami udržiavajú po triedení relatívny poradie. Zlúčenie zoradenia a inzercie sú stabilné, zatiaľ čo halda triedenia a rýchle zoradenie (v základnej podobe) nie sú. Stabilita môže byť v určitých aplikáciách dôležitá.
* PIVOT COMEWORE (Rýchle zoradenie): Výkon rýchleho druhu silne závisí od výberu prvku otočného prvku. Zlé voľby na čele sa môžu viesť k najhoršiemu prípadu O (n
2
* zložitosť implementácie: Triedenie bubliny a triedenie vloženia sú najjednoduchšie na implementáciu. Zlúčiť zoradenie, rýchle zoradenie a triedenie hromady sú zložitejšie.
* adaptivita: Zoradenie vloženia je adaptívne, čo znamená, že jeho výkon sa zlepšuje, ak sú vstupné údaje už čiastočne zoradené.
Výber správneho algoritmu:
Najlepší algoritmus triedenia na použitie závisí od konkrétnej aplikácie a charakteristík údajov. Zvážte tieto faktory:
* veľkosť súboru údajov: V prípade veľmi malých súborov údajov môže stačiť jednoduchosť triedenia bublín alebo inzercie. Pre väčšie súbory údajov sú zlúčenie zoradenia, rýchle zoradenie alebo triedenie hromady vo všeobecnosti lepšou voľbou.
* Úroveň triedenia: Ak sú údaje už väčšinou zoradené, môže byť najrýchlejšou možnosťou triedenie vloženia.
* Pamäťové obmedzenia: Ak je pamäť obmedzená, uprednostňujú sa algoritmy triedenia na mieste, ako sú triedenie bubliny, triedenie výberu, triedenie vloženia a triedenie haldy.
* Požiadavky na stabilitu: Ak je potrebná stabilita, vyberte stabilný algoritmus triedenia, ako je zlúčenie zoradenia alebo triedenie vloženia.
* Výkon najhoršieho prípadu: Ak potrebujete zaručený výkon, vyhnite sa rýchlemu triedeniu (pokiaľ nie je implementovaná s náhodnou náhodou otočeného alebo inými stratégiami na zmiernenie najhoršieho správania).
* jednoduchosť implementácie a údržby: Zvážte kompromis medzi výkonom a zložitosťou implementácie.
Dúfam, že toto podrobné vysvetlenie pomôže! Dajte mi vedieť, ak máte ďalšie otázky.