Share
In deze snelle tip laat ik zien hoe en waarom het bellen-sorteeralgoritme werkt en hoe het in AS3 moet worden geïmplementeerd. U krijgt een klasse die u in elk Flash-project kunt gebruiken om elke array te sorteren.
Hier is een eenvoudige demo van het resultaat van het bellen-sorteeralgoritme:
Natuurlijk, deze SWF bewijst niet veel op zichzelf! Pak de bronbestanden en u kunt de invoerarray zelf bewerken.
Aangezien dit algoritme meer dan eens zal worden gebruikt, is het een goed idee om er een klasse voor te maken, zodat we het gemakkelijk in elk AS3-project kunnen gebruiken:
Stel een eenvoudig Flash-project op en maak een bestand in de projectmap BubbleSort.as. (We zullen hier ook een testerbestand maken, zodat we het kunnen testen.)
Als u niet weet hoe u met klassen moet werken, raadpleegt u deze zelfstudie: Een documentklasse in Flash gebruiken.
We hebben de constructeur niet nodig, dus doe het weg! Je klas zou er als volgt uit moeten zien:
pakket openbare klasse BubbleSort
Dit algoritme is niet de snelste of meest efficiënte methode om een reeks getallen te sorteren, maar het is de gemakkelijkste om te begrijpen.
Deze afbeelding somt het op; in elke fase wordt elk paar getallen vanaf het einde vergeleken en uitgewisseld (door middel van een "reserve" temp variabele) als ze in de verkeerde volgorde staan.
Nadat alle opeenvolgende paren zijn gecontroleerd, garandeert dit dat het nummer aan het begin het grootste aantal in de reeks is; we herhalen het en controleren elk paar nummers afgezien van het nummer aan het begin. Nadat alle opeenvolgende paren zijn gecontroleerd, weten we dat de eerste twee nummers in de reeks zijn in de juiste volgorde (ze zijn de grootste en de tweede grootste). We gaan door totdat we elk nummer in de juiste volgorde hebben geplaatst.
Het wordt 'bellen sorteren' genoemd omdat bij elke passage door de array het grootste aantal naar de top van de array 'zweeft', zoals een bubbel in water.
Laten we beginnen met het schrijven van de code. We zullen de hoofdfunctie noemen bsort ():
Accentsconagua
package public class BubbleSort public function bsort (arr: Array, sortType: String): Array var temp: String; if (sortType.toLocaleLowerCase () == "descending") else if (sortType.toLocaleLowerCase () == "ascending") else gooi een nieuwe fout ("Je hebt een typfout bij het aanroepen van de bsort () -functie, alstublieft gebruik 'oplopend' of 'aflopend' voor sortType! "); terugkeer arr; De functie krijgt twee parameters. De eerste parameter, arr, wordt de array die moet worden gesorteerd; de tweede paramter, sorttype wordt gebruikt om te beslissen of de gebruiker wil dat de array in oplopende of aflopende volgorde wordt gesorteerd.
In de functie verklaren we a temp variabele die de elementen van de array bevat voor het geval we de twee elementen moeten verwisselen. Je vraagt je misschien af waarom het geen nummer is. Het komt omdat onze klas ook String-arrays kan verwerken, alfabetisch sorteren; we kunnen getallen converteren naar strings en weer terug, maar we kunnen strings niet naar getallen en weer terug converteren, dus gebruiken we een String voor deze variabele, alleen om veilig te zijn.
We gebruiken een als-anders blok om onze code in twee takken te splitsen, afhankelijk van de richting waarin de gebruiker wil sorteren. (Als de gebruiker geen geldige keuze geeft, zal het programma een foutmelding geven.)
Het verschil tussen de code in een van beide filialen is slechts één teken: één van beide < of >.
Laten we het algoritme schrijven. We beginnen met het dalende gedeelte:
package public class BubbleSort public function bsort (arr: Array, sortType: String): Array var temp: String; if (sortType.toLocaleLowerCase () == "descending") for (var i: uint = 0; i < arr.length; i++) for(var j:uint=arr.length-1; j > ik; j--) else if (sortType.toLocaleLowerCase () == "oplopend") anders gooi een nieuwe fout ("Je hebt een typfout bij het aanroepen van de bsort () functie, gebruik alsjeblieft 'oplopend' of 'aflopend' 'voor sortType! "); terugkeer arr; Zoals u kunt zien, gebruiken we genest voor loops. Eén gaat van het eerste element naar het laatste element van de array; de andere gaat achteruit.
Laten we de binnenkant inspecteren "j"loop eerst. Zoals het eerdere diagram laat zien, beginnen we met het vergelijken van de laatste twee elementen van de array, welke zijn arr [j-1] en arr [j] (in de eerste iteratie). Als arr [j-1] is minder dan arr [j] ze moeten worden geruild.
In beide gevallen trekken we er een af van j (door het "j--"oproep in lijn 131), die verandert welk paar nummers zal worden vergeleken in de volgende lus.
j begint bij een waarde van arr.length-1, en eindigt met een waarde van 1, wat betekent dat de innerlijke voor lus controleert elk opeenvolgend paar, te beginnen met het laatste paar (waar j is gelijk aan arr.length-1) en eindigend met het eerste paar (waar j is gelijk aan 1).
Laten we nu naar de buitenwereld kijken "ik"lus. Nadat alle paren zijn gecontroleerd en verwisseld zoals nodig, ik wordt verhoogd (door de "ik++"oproep in lijn 129) Dit betekent dat, de volgende keer, j begint om arr.length-1 opnieuw, maar eindig met 2 deze keer - wat betekent dat het eerste paar in de reeks niet zal worden gecontroleerd of verwisseld. Dit is precies wat we willen, omdat we weten dat het eerste nummer in de juiste positie staat.
Als het doorgaat, zullen er uiteindelijk maar twee elementen zijn die gecontroleerd moeten worden in de binnenste lus. Als ze klaar zijn, weten we dat we de array hebben gesorteerd!
Dit is hoe dat eruit ziet in de code:
