Dažāda veida šķirošanas algoritmu

[reza56]

kā jūs zināt, šķirošana ir viens no galvenajiem algoritmiem.
analīze un algoritms dizains ir ļoti svarīga un nepieciešama laba matemātika.
Es zinu, THR galvenais veida šķirošanas algoritmu, bet es gribu zināt citu ones.
Es dzirdēju kaut ko par jebkuru citu veidu kārtošanas algoritmu, kas optimizēta īpašās programmas.
Vai jūs varat man palīdzēt uzzināt vairāk par viņiem?

 

[jimjim2k]

Sveiki

Ātrākais Šķirošanas algoritmu?
Vai jūs belive to?

Šķirošana n veseli skaitļi, kas O (n log (log n))Kas šķirošanas algoritms ir ātrākais?Uzdot šo jautājumu uz jebkuru grupu, programmētāju un jūs saņemsiet animācijas diskusija.Protams, nav viena atbilde.Tas ir atkarīgs ne tikai no algoritma, bet arī uz datora, datu un īstenošanu.Tomēr, ja jūs skaits operāciju skaitu, kas vajadzīgi, lai kārtotu skaitlim numurus standarta von Neumann dators, ir skaidrs uzvarētājs - algoritmu iesniegts papīra "šķirošanu Linear laiks?"A. Andersson, T. Hagerup, S. Nilsson, un R. Raman (raksti 27. gada ACM simpozijs par teorija Computing, 1995).Tā kārto n integers laikā proporcionāli n log log n.Šajā rakstā, I'll sniegt jums pilnīgu aprakstu šī algoritma.

To var darīt vēl ātrāk?Neviens nezina.Mēs tikai zinām, ka nav iespējams veikt, izmantojot mazāk par n darbības: algoritms, kas izmanto mazāk operācijām, nekā nevar apskatīt katru n skaitu un, tātad, varētu paredzēt kādu no numuriem no pasūtījuma.

Pat ja n log log n laika šķirošanas algoritmu radās kā teorētisko spēli, tā reālās dzīves sniegums ir labs.AC īstenošanu, piemēram, nloglogn.c (pieejams elektroniski; sk Resource Center ", lapa 5), kurām nav konkrēta pilnveides iet ātrāk par tipisku 32 bitu mašīna, nekā daudzi standarta textbook šķirošanas algoritmu.

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

 

[peter-gr]

pārbaudīt šo vietni ātrākais algoritmus šķirošanu.

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

 

[Kral]

"Knuth māksla Programming", ko ir 3 Sējums kopums grāmatas.Viens no viņiem (es neatceros kurā) ir pilnībā veltīts meklēšanas jautājumiem, šķirošanas un.Es ļoti ieteiktu šo sēriju.

 

[chirkut_iis]

Hi all,
Sējums 3 ir veltīta šķirošanas un meklēšanas ... esmu visu trīs sējumos, un mēģināja mazliet visu.Viņš ir diezgan izstrādāt daudzos jautājumos - gan triviāls un nav triviāla.Tāpēc pašmācības nav problēma.
Jūs varētu arī mēģināt "Dizains un algoritmu analīze", ko Aho, Hopcroft un Ullman vai "Ievads algoritmi" ar Cormen, Leicerson un Rivest, bet man nav lasīt tos yet.

regards,
Chirkut

 

[mail.mbox]

peter-gr rakstīja:

pārbaudīt šo vietni ātrākais algoritmus šķirošanu.h ** p: / / www.cs.ubc.ca / zirnekļa / Harrison / Java / šķirošanas-demo.html

 

[Arwen148]

Vai jums ir kādas vietas, kur es varu atrast Ullman grāmata?