Algoritmas | |
Tipas | Rikiavimo algoritmai |
Pavadinimas | Skaitmeninis (Radix sort) |
Sudėtingumas | Vidutinis - N; blogiausias - N |
Greitos nuorodos |
Skaitmeninis rikiavimas (angl. radix sort) – vienas iš rikiavimo algoritmų, skirtas atvejams, kai duomenų reikšmės yra skaitmeninės ir priklauso kokiam nors skaitiniam intervalui ar išsiskiria panašiomis savybėmis. Skaitmeninio rikiavimo algoritmuose duomenų reikšmės interpretuojamos kaip skaičiai M-tainėje (dažniausiai – dvejetainėje) skaičiavimo sistemoje. Algoritmas stabilus ir labai greitas, sudėtingumas – O(N·k) (k – rakto ilgis). Pirmasis skaitmeninio rikiavimo algoritmas kompiuteriui parašytas 1954 metais.
Dažniausiai naudojamos skaitmeninio rikiavimo procedūros: skaitmeninio keitimo (radix exchange sort) ir tiesioginio skaitmeninio rikiavimo (straight radix sort). Skaitmeninio keitimo metodas naudoja apie N·logN bitų lyginimų. Abu skaitmeniniai metodai, rikiuodami N skaičių, kurių kiekvienas yra b bitų ilgio, naudoja mažiau negu N·b bitų lyginimų.
Skaitmeninis rikiavimo algoritmas jau buvo naudojamas 1887 m., kai amerikietis Hermanas Holeritas (Herman Hollerith) dirbo su tabuliatoriumi.
Šaltiniai
- US 395781 ir UK 327
vikipedija, wiki, lietuvos, knyga, knygos, biblioteka, straipsnis, skaityti, atsisiųsti, nemokamai atsisiųsti, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, pictu , mobilusis, telefonas, android, iOS, apple, mobile telefl, samsung, iPhone, xiomi, xiaomi, redmi, honor, oppo, Nokia, Sonya, mi, pc, web, kompiuteris