Share
I denne Quick Tip, vil jeg vise deg hvordan og hvorfor Bubble Sort-algoritmen fungerer, og hvordan du implementerer den i AS3. Du vil ende opp med en klasse som du kan bruke i et hvilket som helst Flash-prosjekt, for å sortere hvilken som helst matrise.
Her er en enkel demo av resultatet av boble sorteringsalgoritmen:
Selvfølgelig viser denne SWF ikke mye på egen hånd! Ta tak i kildefilene, og du kan selv redigere innmatingsarrangementet.
Siden denne algoritmen vil bli brukt mer enn en gang, er det en god ide å lage en klasse for det, slik at vi enkelt kan bruke det i ethvert AS3-prosjekt:
Sett opp et grunnleggende Flash-prosjekt, og opprett en fil i prosjektmappen BubbleSort.as. (Vi lager også en testerfil her, så vi kan teste det.)
Hvis du ikke vet hvordan du skal jobbe med klasser, vennligst sjekk denne veiledningen: Slik bruker du en dokumentklasse i Flash.
Vi trenger ikke konstruktøren, så bli kvitt det! Din klasse skal se slik ut:
pakke offentlig klasse BubbleSort
Denne algoritmen er ikke den raskeste eller mest effektive metoden for å sortere en rekke tall, men det er den enkleste å forstå.
Dette bildet oppsummerer det i hvert trinn sammenlignes hvert par tall, begynner fra slutten, og byttes (ved hjelp av en "reserve" temp variabel) hvis de er i feil rekkefølge.
Når alle sammenhengende par er blitt sjekket, garanterer dette at nummeret ved starten er det største nummeret i sekvensen; Vi gjentar deretter, kontrollerer hvert par tall bortsett fra nummeret i starten. Når alle sammenhengende par er blitt sjekket, vet vi at den første to tall i sekvensen er i riktig rekkefølge (de er de største og nest største). Vi fortsetter å gå til vi har satt alle tallene i riktig rekkefølge.
Det kalles "bubblesort" fordi på hver passering gjennom arrayet er det største nummeret "flyter" til toppen av matrisen, som en boble i vann.
La oss begynne å skrive koden. Vi kaller hovedfunksjonen bsort ():
Accentsconagua
pakke offentlig klasse BubbleSort offentlig funksjon bsort (arr: Array, sortType: String): Array var temp: String; hvis (sortType.toLocaleLowerCase () == "descending") annet hvis (sortType.toLocaleLowerCase () == "stigende") annet kaster ny feil ("Du har en skrivefeil når du ringer til bsort () -funksjonen, vær så snill bruk 'stigende' eller 'synkende' for sortType! "); tilbake ar; Funksjonen får to parametere. Den første parameteren, arr, vil være arrayet som skal sorteres; den andre parameteren, sortType vil bli brukt til å bestemme om brukeren vil at arrayet skal sorteres i stigende eller synkende rekkefølge.
I funksjonen erklærer vi en temp variabel som vil holde elementene i arrayet hvis vi trenger å bytte de to elementene. Du lurer kanskje på hvorfor det ikke er et tall. Det er fordi vår klasse vil kunne håndtere String-arrayer, sortere dem alfabetisk; vi kan konvertere tall til strenger og tilbake igjen, men vi kan ikke konvertere strenger til tall og tilbake igjen, så vi bruker en streng for denne variabelen, for å være trygg.
Vi bruker en hvis-ellers blokkere for å dele koden vår i to grener, avhengig av hvilken retning brukeren vil sortere inn. (Hvis brukeren ikke gir et gyldig valg, vil programmet brenne en feil.)
Forskjellen mellom koden i hver gren vil bare være ett tegn: heller < eller >.
La oss skrive algoritmen. Vi starter med den nedstigende delen:
pakke offentlig klasse BubbleSort offentlig funksjon bsort (arr: Array, sortType: String): Array var temp: String; hvis (sortType.toLocaleLowerCase () == "descending") for (var jeg: uint = 0; i < arr.length; i++) for(var j:uint=arr.length-1; j > Jeg; j)) annet hvis (sortType.toLocaleLowerCase () == "stigende") Endre kaste ny feil ("Du har en skrivefeil når du ringer til bsort () -funksjonen, bruk" stigende "eller" synkende 'for sortType! "); tilbake ar; Som du ser, bruker vi nestet til sløyfer. Man går fra det første elementet til det siste elementet i arrayet; den andre går bakover.
La oss inspisere den indre "j"loop først. Som det tidligere diagrammet viser, begynner vi ved å sammenligne de to siste elementene i arrayet, som er arr [j-1] og arr [j] (i den første iterasjonen). Hvis arr [j-1] er mindre enn arr [j] de må byttes.
I begge tilfeller trekker vi en fra j (gjennom "j--"ring i linje 131), som endrer hvilket par tall som skal sammenlignes på neste sløyfe.
j starter til en verdi av arr.length-1, og slutter med en verdi på 1, som betyr at det indre til loop kontrollerer hvert sammenhengende par, starter med det siste paret (hvor j er lik arr.length-1) og slutter med det første paret (hvor j er lik 1).
La oss nå se på den ytre "Jeg"loop. Når alle parene er blitt sjekket og byttet etter behov, Jeg er økt (gjennom "Jeg++"ring i linje 129). Dette betyr at neste gang rundt, j vil starte på arr.length-1 igjen, men slutt på 2 denne gangen - noe som betyr at det første paret i sekvensen ikke blir sjekket eller byttet ut. Dette er akkurat det vi ønsker, siden vi vet at det første nummeret er i riktig posisjon.
Som det skjer, vil det til slutt bare være to elementer som må kontrolleres i indre sløyfe. Når de er ferdige, vet vi at vi har sortert arrayen!
Her ser det ut som i kode:
