Share
În acest sfat rapid, vă voi arăta cum și de ce funcționează algoritmul Bubble Sort și cum să îl implementați în AS3. Veți încheia cu o clasă pe care o puteți utiliza în orice proiect Flash, pentru a sorta orice matrice.
Iată o simplă demonstrație a rezultatului algoritmului de sortare a bulei:
Bineinteles, acest SWF nu se dovedeste mult pe cont propriu! Prindeți fișierele sursă și puteți edita singur matricea de intrări.
Deoarece acest algoritm va fi folosit de mai multe ori, este o idee bună să creați o clasă pentru aceasta, astfel încât să o putem folosi cu ușurință în orice proiect AS3:
Creați un proiect de bază Flash și în interiorul directorului de proiect creați un fișier BubbleSort.as. (Vom crea un fișier de tester și aici, astfel încât să îl putem testa.)
Dacă nu știți cum să lucrați cu clase, consultați acest tutorial: Cum să utilizați o clasă de documente în Flash.
Nu avem nevoie de constructor, așa că scapă de el! Clasa ar trebui să arate astfel:
pachet public class BubbleSort
Acest algoritm nu este metoda cea mai rapidă sau cea mai eficientă de sortare a unei serii de numere, dar este cel mai ușor de înțeles.
Această imagine o însumează; la fiecare etapă, fiecare pereche de numere este comparată, începând de la final, și schimbată (prin intermediul unui "rezervă" temp variabilă) dacă sunt în ordine greșită.
Odată ce toate perechile consecutive au fost verificate, acest lucru garantează că numărul de la început este cel mai mare număr din secvență; apoi repetăm, verificând fiecare pereche de numere cu excepția numărului de la început. Odată ce toate perechile consecutive au fost verificate, știm că prima Două numerele din ordine sunt în ordinea corectă (acestea sunt cele mai mari și cele de-a doua). Continuăm până vom pune fiecare număr în ordinea corectă.
Se numește "sortare cu bule", deoarece, pe fiecare trecere prin matrice, cel mai mare număr "plutește" în partea superioară a matricei, ca un balon în apă.
Să începem să scriem codul. Vom numi funcția principală bsort ():
Accentsconagua
pachet public class BubbleSort funcția publică bsort (arr: Array, sortType: String): Array var temp: String; if (sortType.toLocaleLowerCase () == "descendent") altceva dacă (sortType.toLocaleLowerCase () == "ascendent") altfel aruncați o nouă eroare ("Aveți o greșeală atunci când apelați funcția bsort utilizați "ascendent" sau "descendent" pentru sortType! "); retur arr; Funcția primește doi parametri. Primul parametru, arr, va fi matricea care urmează să fie sortată; al doilea paramter, sortType va fi folosit pentru a decide dacă utilizatorul dorește ca seria să fie sortată în ordine ascendentă sau descendentă.
În funcția pe care o declarăm a temp variabilă care va păstra elementele matricei în cazul în care avem nevoie să schimbați cele două elemente. S-ar putea să te întrebi de ce nu e un număr. Este pentru că clasa noastră va fi capabilă să se ocupe și de retelele String, sortându-le în ordine alfabetică; putem converti numere în siruri de caractere și din nou înapoi, dar nu putem converti șiruri de caractere la numere și înapoi, deci vom folosi un șir pentru această variabilă, doar pentru a fi siguri.
Noi folosim un dacă-altfel blocați pentru a împărți codul nostru în două ramuri, în funcție de direcția în care utilizatorul dorește să sorteze. (Dacă utilizatorul nu oferă o alegere validă, programul va declanșa o eroare.)
Diferența dintre codul din fiecare ramură va fi doar un singur caracter: fie < sau >.
Să scriem algoritmul. Începem cu partea descendentă:
pachet public class BubbleSort funcția publică bsort (arr: Array, sortType: String): Array var temp: String; dacă (sortType.toLocaleLowerCase () == "descendentă") pentru (var i: uint = 0; i < arr.length; i++) for(var j:uint=arr.length-1; j > i; j ") altfel dacă (sortType.toLocaleLowerCase () ==" ascendentă ") altfel aruncați o eroare nouă (" Aveți o greșeală atunci când apelați funcția bsort "pentru tipul de sortare!"); retur arr; După cum puteți vedea, folosim imbricate pentru bucle. Una merge de la primul element la ultimul element al matricei; cealaltă merge înapoi.
Să inspectăm interiorul "j"în primul rând. După cum arată diagrama anterioară, începem prin compararea ultimelor două elemente ale matricei, care sunt arr [j-1] și arr [j] (în prima repetare). Dacă arr [j-1] e mai puțin decât arr [j] acestea trebuie schimbate.
În ambele cazuri, scădem unul j (prin "j--"apel în linia 131), care modifică ce perechi de numere vor fi comparate pe următoarea buclă.
j începe la o valoare de arr.length-1, și se termină cu o valoare de 1, ceea ce înseamnă că interiorul pentru buclă verifică fiecare pereche consecutivă, începând cu ultima pereche (unde j este egală arr.length-1) și se termină cu prima pereche (unde j este egală 1).
Acum să ne uităm la "euDupă ce toate perechile au fost verificate și schimbate după cum este necesar, eu este crescut (prin "eu++"apel în linia 129. Aceasta înseamnă că, data viitoare, j va începe la arr.length-1 din nou, dar se termină 2 de data aceasta - ceea ce înseamnă că prima pereche din secvență nu va fi verificată sau înlocuită. Acesta este exact ceea ce dorim, deoarece știm că primul număr este în poziția corectă.
În continuare, în cele din urmă vor exista doar două elemente care trebuie verificate în bucla interioară. Odată ce au terminat, știm că am sortat matricea!
Iată ce arată în cod:
