Share
I den här snabba tipsen visar jag hur och varför Bubble Sort-algoritmen fungerar och hur man implementerar den i AS3. Du kommer att sluta med en klass som du kan använda i något Flash-projekt, för att sortera vilken matris som helst.
Här är en enkel demonstration av resultatet av bubbelsortalgoritmen:
Självklart bevisar detta SWF inte mycket på egen hand! Ta tag i källfilerna och du kan själv redigera ingångssystemet.
Eftersom denna algoritm kommer att användas mer än en gång är det en bra idé att skapa en klass för den, så att vi enkelt kan använda den i något AS3-projekt:
Skapa ett grundläggande Flash-projekt, och skapa en fil i projektmappen BubbleSort.as. (Vi kommer också att skapa en testerfil här, så vi kan testa det.)
Om du inte vet hur du ska arbeta med klasser, kolla här handledningen: Så här använder du en dokumentklass i Flash.
Vi behöver inte konstruktören, så bli av med det! Din klass ska se så här ut:
paket public class BubbleSort
Denna algoritm är inte den snabbaste eller mest effektiva metoden för att sortera en serie siffror, men det är det enklaste att förstå.
Denna bild summerar den upp; vid varje steg jämförs varje par tal, från och med slutet och bytts (med hjälp av en "reserv" temp variabel) om de är i fel ordning.
När alla på varandra följande par har kontrollerats, garanterar detta att antalet i början är det största numret i sekvensen; Vi upprepar då och kontrollerar varje par nummer förutom antalet i början. När alla på varandra följande par har kontrollerats, vet vi att den första två siffrorna i sekvensen är i rätt ordning (de är störst och näst störst). Vi fortsätter tills vi har satt varje nummer i rätt ordning.
Den kallas "bubbelsort" eftersom varje enskild passagerare passerar det största antalet "floats" till toppen av matrisen, som en bubbla i vatten.
Låt oss börja skriva koden. Vi ringer huvudfunktionen bsort ():
Accentsconagua
paket public class BubbleSort public function bsort (arr: Array, sortType: String): Array var temp: String; om sortType.toLocaleLowerCase () == "descending") annars om (sortType.toLocaleLowerCase () == "stigande") annars kasta nytt fel ("Du har ett typsnitt när du ringer till bsort () använd "stigande" eller "nedstigande" för sortType! "); återvändande ar; Funktionen får två parametrar. Den första parametern, arr, kommer att vara arrayen som ska sorteras; den andra parametern, sortType kommer att användas för att bestämma om användaren vill att arrayen ska sorteras i stigande eller fallande ordning.
I funktionen förklarar vi en temp variabel som kommer att hålla elementen i arrayen om vi behöver byta de två elementen. Du kanske undrar varför det inte är ett nummer. Det beror på att vår klass också kommer att kunna hantera String-arrays, sortera dem alfabetiskt; vi kan konvertera tal till strängar och tillbaka igen, men vi kan inte konvertera strängar till nummer och tillbaka igen, så vi använder en sträng för denna variabel, bara för att vara säker.
Vi använder en om-annan blockera för att dela upp vår kod i två grenar, beroende på vilken riktning användaren vill sortera in. (Om användaren inte anger ett giltigt val, kommer programmet att branda ett fel.)
Skillnaden mellan koden i endera filialen är bara ett tecken: antingen < eller >.
Låt oss skriva algoritmen. Vi börjar med den nedstigande delen:
paket public class BubbleSort public function bsort (arr: Array, sortType: String): Array var temp: String; om (sortType.toLocaleLowerCase () == "descending") for (var i: uint = 0; i < arr.length; i++) for(var j:uint=arr.length-1; j > jag; j)) annars om (sortType.toLocaleLowerCase () == "stigande") annars kasta nytt fel ("Du har ett typsnitt när du ringer till bsort () -funktionen, använd" stigande "eller" nedåtgående "för sortType!"); återvändande ar; Som ni kan se använder vi kapslade för loopar. Man går från det första elementet till det sista elementet i matrisen; den andra går bakåt.
Låt oss inspektera det inre "j"loop första. Som det tidigare diagrammet visar börjar vi genom att jämföra de två sista elementen i arrayen, som är arr [j-1] och arr [j] (i den första iterationen). Om arr [j-1] är mindre än arr [j] de måste bytas ut.
I båda fallen subtraherar vi en från j (genom "j--"ring i rad 131), vilket ändrar vilket antal tal som ska jämföras på nästa slinga.
j börjar till ett värde av arr.length-1, och slutar med ett värde av 1, vilket betyder det inre för slingan kontrollerar varje efterföljande par, börjar med det sista paret (var j är lika med arr.length-1) och slutar med det första paret (var j är lika med 1).
Låt oss nu titta på det yttre "jag"slinga. När alla par har kontrollerats och bytts ut efter behov, jag ökas (genom "jag++"ring i rad 129). Det betyder att nästa gång runt, j kommer att börja på arr.length-1 igen, men sluta vid 2 den här gången - vilket betyder att det första paret i sekvensen inte kommer att kontrolleras eller bytas. Det är precis vad vi vill ha, eftersom vi vet att det första numret är i rätt läge.
När det går så småningom kommer det bara att finnas två element som måste kontrolleras i inre slingan. När de är färdiga vet vi att vi har sorterat arrayen!
Det här ser ut som i kod:
