Stabilus sveikųjų skaičių rikiavimas skaičiavimu
Turint n įrašų su sveikaisiais raktais 0≤k<U, pagal raktą pridėti įrašus į U krepšelių galus, išlaikant įterpimo tvarką, tada sujungti krepšelius raktų didėjimo tvarka.
Esminės žinios
Turint n įrašų su sveikaisiais raktais 0≤k<U, pagal raktą pridėti įrašus į U krepšelių galus, išlaikant įterpimo tvarką, tada sujungti krepšelius raktų didėjimo tvarka. Taip stabiliai surikiuojama per O(n+U) laiko, naudojant O(n+U) atminties, kai indeksavimo ir pridėjimo į galą operacijų sąnaudos yra vienetinės. Įrašai su vienodais raktais išlaiko pradinę tvarką.
Sąlygos ir taikymo ribos
- U≥1; į sąnaudas įtraukti inicializavimą ir visus įrašus.
- Šis įvertis remiasi prieiga pagal sveikąjį raktą ir nėra vien palyginimais grindžiamo rikiavimo įvertis.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
5 paskaita „Rikiavimas skaičiavimu“, spausdinti puslapiai 3–4, įterpimo tvarką išlaikančių krepšelių sudarymas ir sąnaudų lentelė.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi glaustai suformuluoti teiginiai (241), hipotezės, pateiktos lygtys ir susitarimai bei visos kilmės semantinės sąsajos (596); peržiūrėta visa autoriaus sudaryta 241 įrašo tikslių šaltinių patikros matrica ir deklaruoti apribojimai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tikslingai ir nepriklausomai peržiūrėti pirminių šaltinių skyriai; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atlikta informacinio turinio peržiūra, o ne žmogaus eksperto patvirtinimas atitinkamoje mokslo srityje, išsamus vadovėlio atkūrimas ar eksperimentinis pakartojimas. Peržiūros įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-stable-counting-sort
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra