В этом кратком совете я покажу вам, как и почему работает алгоритм Bubble Sort, и как реализовать его в AS3. Вы получите класс, который вы можете использовать в любом проекте Flash для сортировки любого массива.
Окончательный результат предварительного просмотра
Вот простая демонстрация результата алгоритма пузырьковой сортировки:
Конечно, этот SWF сам по себе мало что дает! Возьмите исходные файлы, и вы можете редактировать входной массив самостоятельно.
Шаг 1: Создание класса BubbleSort
Поскольку этот алгоритм будет использоваться более одного раза, рекомендуется создать для него класс, чтобы его можно было легко использовать в любом проекте AS3:
Настройте базовый проект Flash и в папке проекта создайте файл BubbleSort.as . (Мы также создадим здесь файл тестера, чтобы мы могли его протестировать.)
Если вы не знаете, как работать с классами, обратитесь к этому руководству: Как использовать класс документа во Flash .
Нам не нужен конструктор, так что избавьтесь от него! Ваш класс должен выглядеть так:
|
01
02
03
04
05
06
07
08
09
10
|
package
{
public class BubbleSort
{
}
}
|
Шаг 2: Как работает алгоритм
Этот алгоритм не является самым быстрым или наиболее эффективным методом сортировки серии чисел, но его проще всего понять.
Это изображение подводит итог; на каждом этапе каждая пара чисел сравнивается, начиная с конца, и заменяется (с помощью «резервной» temp переменной), если они находятся в неправильном порядке.
После проверки всех последовательных пар это гарантирует, что число в начале является наибольшим числом в последовательности; затем мы повторяем, проверяя каждую пару чисел, кроме числа в начале . После проверки всех последовательных пар мы знаем, что первые два числа в последовательности расположены в правильном порядке (они являются самыми большими и вторыми по величине). Мы продолжаем, пока мы не поместим каждый номер в правильном порядке.
Это называется «пузырьковая сортировка», потому что при каждом проходе через массив наибольшее число «плавает» на вершине массива, как пузырь в воде.
Давайте начнем писать код. Мы вызовем основную функцию bsort() :
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
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
throw new Error(«You have a typo when Calling the bsort() function, please use ‘ascending’ or ‘descending’ for sortType!»);
return arr;
}
}
}
|
Функция получает два параметра. Первый параметр, arr , будет массивом для сортировки; второй параметр, sortType будет использоваться для определения, хочет ли пользователь сортировать массив в порядке возрастания или убывания.
В функции мы объявляем temp переменную, которая будет содержать элементы массива на случай, если нам нужно поменять местами два элемента. Вы можете удивиться, почему это не число. Это потому, что наш класс сможет обрабатывать и строковые массивы, сортируя их по алфавиту; мы можем преобразовать числа в строки и обратно, но мы не можем преобразовать строки в числа и обратно, поэтому мы используем String для этой переменной, просто для безопасности.
Мы используем блок if — else чтобы разделить наш код на две ветви, в зависимости от того, в каком направлении пользователь хочет отсортировать. (Если пользователь не предоставит правильный выбор, программа выдаст ошибку.)
Разница между кодом в любой ветви будет всего один символ: либо < либо > .
Давайте напишем алгоритм. Начнем с нисходящей части:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
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 > i; j—)
{
}
}
}
else if(sortType.toLocaleLowerCase() == «ascending»)
{
}
else
throw new Error(«You have a typo when Calling the bsort() function, please use ‘ascending’ or ‘descending’ for sortType!»);
return arr;
}
}
}
|
Как видите, мы используем вложенные циклы. Один идет от первого элемента к последнему элементу массива; другой идет назад.
Давайте сначала проверим внутренний цикл » j «. Как показывает предыдущая диаграмма, мы начнем со сравнения двух последних элементов массива, которые являются arr[j-1] и arr[j] (в первой итерации). Если arr[j-1] меньше arr[j] их необходимо поменять местами.
В любом случае мы вычитаем одно из j (через вызов « j-- » в строке 131), что меняет, какая пара чисел будет сравниваться в следующем цикле.
j начинается со значения arr.length-1 и заканчивается значением 1 , что означает, что внутренний цикл for проверяет каждую последовательную пару, начиная с последней пары (где j равна arr.length-1 ) и заканчивая первая пара (где j равно 1 ).
Теперь давайте посмотрим на внешний цикл « i ». После того, как все пары были проверены и заменены по мере необходимости, i увеличивается (через вызов « i++ » в строке 129). Это означает, что в следующий раз j будет снова начинаться с arr.length-1 , но на этот раз заканчивается на 2 это означает, что первая пара в последовательности не будет проверена или заменена. Это именно то, что мы хотим, так как мы знаем, что первое число находится в правильном положении.
По ходу дела, в конечном итоге во внутреннем цикле нужно будет проверить только два элемента. Как только они закончили, мы знаем, что отсортировали массив!
Вот как это выглядит в коде:
|
01
02
03
04
05
06
07
08
09
10
11
12
|
for(var i:uint=0; i<arr.length;i++)
{
for(var j:uint=arr.length-1; j > i; j—)
{
if (arr[j-1] < arr[j])
{
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
|
И алгоритм готов!
Теперь мы можем использовать ту же логику для создания сортировки по возрастанию:
Нам нужно только изменить оператор сравнения в блоке if внутреннего цикла:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
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 > i; j—)
{
if (arr[j-1] < arr[j])
{
temp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
}
}
else if(sortType.toLocaleLowerCase() == «ascending»)
{
for(var k:uint=0; k<arr.length;k++)
{
for(var l:uint=arr.length-1; l > k; l—)
{
if (arr[l-1] > arr[l])
{
temp = arr[l-1];
arr[l-1] = arr[l];
arr[l] = temp;
}
}
}
}
else
{
throw new Error(«You have a typo when Calling the bsort() function, please use ‘ascending’ or ‘descending’ for sortType!»);
}
return arr;
}
}
}
|
Шаг 3: Создание приложения для тестирования
Создайте новый флэш-файл tester.fla в той же папке, что и BubbleSort.as . Создайте два динамических текстовых поля, назовите одно input_arr, а другое output_arr .
После создания внешнего вида мы должны создать и связать класс документа.
Создайте файл Tester.as и свяжите его с tester.fla.
Теперь мы можем наконец использовать наш класс в Tester.as:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
|
package
{
import BubbleSort;
import flash.display.MovieClip;
public class Tester extends MovieClip {
private var bs:BubbleSort = new BubbleSort();
public function Tester() {
var ar:Array = [5,7,9,8,1,3,6,2,4,5,0];
input_arr.text = ar.toString();
ar = bs.bsort(ar,»descending»);
output_arr.text = ar.toString();
}
}
}
|
В этой строке мы вызываем bsort() нашей переменной bs (которая является экземпляром BubbleSort ):
|
1
|
ar = bs.bsort(ar,»ascending»);
|
Эта функция возвращает массив, поэтому мы можем назначить его как новое значение нашего исходного входного массива.
Сохраните все и попробуйте свою работу.
Вывод
В этом уроке мы создали функцию, которая поможет нам отсортировать массив. Мы могли бы улучшить эффективность; подробнее об этом вы можете прочитать в Википедии — Bubble Sort
Если вы действительно хотите увидеть, насколько быстро этот алгоритм сравнивается с другими параметрами (например, быстрой сортировкой), посмотрите на sorting-algorithms.com .