Sortarea digitală (sortare radix)
Sortarea digitală se bazează pe observația că, dacă numărul deja sortat de ranguri Jr. L. L -1, ..., 1, acestea pot fi complet sortate, sortare cifre mai mari P. P -1, ..., L +1, cu condiția ca sortarea este realizată astfel încât să nu perturbe numerele de ordine relative cu aceleași numere în MSBs. Această idee se întemeiază pe dispozitivele mecanice de sortare pentru cartelele de perforare.
În cartelele perforate din carton au fost găurite perforate speciale. Figurile 0-9 au fost codificate prin găuri unice în liniile 0-9 ale coloanei corespunzătoare. Mașina de sortare a fost indicată de coloana pe care trebuia să se facă sortarea și ea a întins pachetul de cărți cu pumn pentru 10 stive, în funcție de care dintre găurile 0-9 a fost lovit în coloana indicată.
Cel mai bine este să începeți cu cel mai puțin semnificativ, extinderea cu 10 stive în funcție de locul în care gaura perforată în coloana „Junior“. Rezultante 10 stive trebuie apoi îndoite una în această ordine: .. Primul card cu 0, atunci cartela 1 etc. Puntea rezultată rassortiruem din nou 10 stive, dar în conformitate cu descărcarea zecilor, adăugați stiva rezultând într-o singură punte, și așa mai departe; când cartele perforate au fost scrise numărul -digit d, va fi nevoie de timp d folosi o mașină de sortare.
Este important ca acest algoritm de sortare să difere de cele mai multe tipuri în sensul că nu se bazează pe o comparație între numere, ci pe reprezentarea numerelor.
Exemplu: Să fie indicate numerele 439, 432, 120, 065.
După cum puteți vedea din exemple, cel mai mare număr este format din 3 cifre, prin urmare, este necesar să sortați după prima, a doua și a treia categorie:
pe primul: 120, 432, 065, 439,
pe al doilea: 120, 432, 439, 065,
pe al treilea: 065, 120, 432, 439.
În problemele practice, este convenabil să se aleagă baza sistemului numeric cu valoarea 2 n, deoarece în acest caz, detectarea descărcării necesare se efectuează numai prin operațiile de schimbare și mascare, ceea ce accelerează semnificativ activitatea algoritmului.
Cupă sortare
Sortarea prin scooparea lucrărilor pentru timpul mediu liniar. Ideea algoritmului este ca intervalul [0, 1) este împărțit în părți n egale, și apoi pentru numerele fiecărei părți i se atribuie o „cutie-lingura“ (găleată), și n întregi care urmează să fie sortate sunt afișate pe aceste casete. Deoarece numărul uniform distribuite pe intervalul [0, 1), este de așteptat ca fiecare cutie vor fi mici. Acum sorta numerele din fiecare cutie separat și du-te prin casetele în ordine crescătoare, scriind prins în fiecare număr, în ordine crescătoare.
Numărarea sorții
Sortarea Calculul algoritm se aplică în cazul în care fiecare dintre n sortat elemente de secvență - un întreg pozitiv într-un anumit interval (care să nu depășească o anumită pre-k). Dacă k = O (n), atunci algoritmul de sortare prin numărătoare funcționează în timp O (n).
Ideea acestui algoritm este de a calcula mai întâi pentru fiecare element x câte elemente ale secvenței de intrare sunt mai mici decât x. apoi scrieți x direct conform acestui număr (dacă, de exemplu, 9 elemente ale matricei de intrare sunt mai mici decât x, atunci matricea de ieșire x trebuie să fie scrisă cu numărul 10). Această schemă este ușor modificată, deoarece în secvența sortată pot exista numere egale, astfel încât să nu se scrie mai multe numere într-un singur loc.
Algoritmul de sortare pentru un contor are o proprietate importantă numită stabilitate (este stabilă). Mai precis, dacă există mai multe numere egale în matricea de intrare, atunci în matricea de ieșire ele sunt în aceeași ordine ca și în matricea de intrare.
Trimiteți-le prietenilor: