Různé druhy třídící algoritmy

[reza56]

Jak víte, třídění, je jedním z hlavních algoritmů.
analýza a návrh algoritmu je velmi důležitá a je třeba dobře matematiku.
Vím, že THR hlavní druh třídící algoritmus, ale chci vědět, žádné jiné.
Slyšel jsem něco o žádné jiné druhy třídící algoritmus, který optimalizovaný pro speciální aplikace.
Můžete mi pomoci se dozvědět více o nich?

 

[jimjim2k]

Ahoj

Nejrychlejší třídící algoritmus?
Myslíte si, věřit, že?

Třídění n celých čísel v O (n log (log n))Který třídící algoritmus je nejrychlejší?Zeptejte se na tuto otázku na kteroukoli skupinu programátorů a dostanete animovaný diskuse.Samozřejmě, není jedna odpověď.Záleží nejen na algoritmus, ale také na počítači, data a implementace.Nicméně, pokud si spočítat počet operací potřebných k řazení celých čísel na standardní von Neumann počítač, je jasný vítěz - algoritmus uveden v knize "Třídění v lineárním čase?"A. Andersson, T. Hagerup, S. Nilsson, a Raman R. (Sborník z 27. ročníku ACM symposium na teorii výpočetní, 1995).To druhy n celých čísel v čase v poměru k n log log n.V tomto článku, dám vám kompletní popis tohoto algoritmu.

Může to být provedeno ještě rychlejší?Nikdo neví.Víme jen, že to nemůže být provedeno s použitím menší než n operací: algoritmus, který používá méně operací, než je možné se dívat na každý z n čísel, a proto by mohl opustit některé z čísel ve správném pořadí.

I když n log log n Time-třídící algoritmus vznikla jako teoretická hra, jeho skutečný-život je dobrá.AC provedení jako nloglogn.c (k dispozici v elektronické podobě, viz "Resource Center", str. 5) bez zvláštního optimalizace běží rychleji na typický 32-bit stroj, než mnozí standardní třídící algoritmy učebnice.

1.h ** p: / / www.ddj.com/documents/s=886/ddj0004d/0004d.htm* -> T
tnx

 

[peter-gr]

šek tohoto webu pro nejrychlejší algoritmy pro třídění.

http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

 

[Král]

"The Art of Programming" od Knuth je 3 Svazek soubor knih.Jeden z nich (nepamatuji si které) se věnuje výhradně předměty na třídění a vyhledávání.Velmi doporučuji tuto řadu.

 

[chirkut_iis]

Zdravím všechny,
Svazek 3 je věnována třídění a vyhledávání ... Mám všechny tři svazky a snažil se trochu ze všech.Je to dost komplikované na mnoho otázek - jak triviální a non-triviální.Takže samostatné studium-není problém.
Můžete také zkusit "Design a analýza algoritmů" od Aho, Hopcroft a Ullman nebo "Úvod do algoritmizace" od Cormen, Leicerson a Rivest, ale já jsem si je ještě.

jde,
Chirkut

 

[mail.mbox]

Peter-gr napsal:

šek tohoto webu pro nejrychlejší algoritmy pro třídění.h ** p: / / www.cs.ubc.ca / Spider / Harrison / Java / třídění-demo.html

 

[Arwen148]

Máte nějaké stránky, kde bych mohl najít Ullman kniha??