【抛砖引玉】AS与算法设计的学习与讨论

一、很少展开来讲的【排序】
因为AS自带sort函数，所以排序对我们来说，只是一个sort的事
如果从算法角度分析排序，排序的算法可是很多的

1.1选择排序
时间复杂度O(n^2)
做法：每一次元素中选出最小的一个元素，顺序放在已排好序的数列的最后(或最前)，直到全部元素排完
变量：
数组a
循环变量i和j
辅助交换变量t
代码：
for (i=0; i<a.length-1; i++)
{
for (j=i+1; j<a.length; j++)
{
if (a[i] > a[j])
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}

选择排序的做法详解：
比如数组元素为-5,5,1,3,2
i=0时
j=1 to 4找出最小的与a[1]交换
此时最小为1，所以数组变为-5,1,5,3,2
i=1时
j=2 to 4找出最小的与a[2]交换
此时最小为2，所以为-5,1,2,3,5


i=2时
j=3 to 4找出最小的与a[3]交换
此时最小3，为-5,1,2,3,5


以此类推，循环完毕，数组为 -5,1,2,3,5

大神咖喱味 必须马克之

1.2插入排序
时间复杂度：最坏O(n^2)，最好O(n)
时间上与选择排序差不多
做法：把未排序的数组逐个放入已排序数组的适当位置
就像插扑克牌。
一堆杂乱无章的扑克牌（未排序数组），
你需要每次拿出一张，插入手牌（已排序数组）的合适位置。
为了方便看，这里给出一段比较好理解的代码
var i:int,j:int,t:int;
var a:Array = [1,5,3,2,4,9,7,6,8];
var b:Array = [];
b.push(a.shift());//拿出未排序的第一个数（此时b是有序的）
while (a.length>0)//反复做，直到a数组被拿完
{
t = a.shift();//拿出一个
for (j=0; j<b.length; j++)
{
if (b[j] < t)//找到第一个比t小的
{
b.splice(j,0,t);//插入
break;//停止
}
}
}
trace(b);
上面这一段代码的特点是很典型，插入过程比较形象，但是并不是实际使用的
实际使用的是下面这一种：
var i:int,j:int,t:int;
var a:Array = [1,5,3,2,4,9,7,6,8];
for (i=1; i<a.length; i++)
{
t = a[i];//拿出
j = i - 1;
while (j>=0 && a[j]<t)
{
a[j + 1] = a[j];//滚动
j--;
}
a[j + 1] = t;//插入
}
trace(a);
这一种才是真正使用的，如果看不出哪里有“插入”，下面我就告诉你
这一段代码其实是：已排序和未排序处在同一个数组
以i为分界，
0~(i-1) 为已排序，
i~总长度 为未排序
每一次的寻找位置，过程中实现了数组元素的滚动，
插入只要一步就行了
如果你能理解第二种方法，相信你也能渐渐体会到算法的神奇之处

1.3冒泡排序
时间复杂度：最坏O(n^2)，最好O(n)
时间上与插入排序一样
做法：拿出数组中某个元素，如果后一个元素比它小，那么就与后一个元素交换位置
就像泡泡向上冒出一样。
和插入排序很类似，对吧？而且在时空复杂度上都一样，它们的区别在哪呢？
答案是，插入排序是基于“插入”的，而冒泡排序是基于“交换”的
代码如下：
var i:int,j:int,t:int;
var a:Array = [1,5,3,2,4,9,7,6,8];
for (j=0; j<a.length; j++)
{
for (i=0; i<a.length-j; i++)//冒泡
{
if (a[i + 1] < a[i])
{
t = a[i + 1];
a[i + 1] = a[i];
a[i] = t;//交换
}
}
}
trace(a);

1.4快速排序QuickSort
时间复杂度：最好O(n*log2(n))，最坏O(n^2)
十分快速，所以叫快速排序
同样是基于交换的排序，也有人理解为两方向的冒泡排序
代码：
var a:Array = [3,5,1,2,4,7,6];
function qs(b:int,e:int):void//这里指从b到e之间进行快速排序
{
if (b>=e)//当开始端与结束端重合时停止
{
return;
}
var i:int=b,j:int=e,mid:int=a[int(b/2+e/2)],t:int;//mid变量为待排序数列的中间
do
{
while (a[i]<mid)
{
i++;//i向右推进，直到a[i]>=mid，不符合规定时停止
}
while (a[j]>mid)
{
j--;//同上，j向左推进
}
if (i<=j)//为了防止误交换，加入的一个判断
{
t = a[i];
a[i] = a[j];
a[j] = t;//交换左右两边不符合规定的元素，这样就能满足规定（这一点是精髓所在）
i++;
j--;//继续开始推进
}
} while (i<=j);//到i>j时停止
qs(b,j);//对左半边再次快排（递归）
qs(i,e);//对右半边再次快排
}
qs(0,a.length-1);
trace(a);
快排的思想相对复杂，整体思想是：
选定一个元素mid，使得mid以左的元素都小于mid，右边的元素都大于mid
注意此时，mid以左的元素不一定有序，mid右边的同样如此
假如，mid是5，数组可能是 1,3,0,2,5,8,6,9,7
所以，对mid左边和右边分别再进行一次快排（递归）
最后，会完全满足快排的规定，此时，数组就是一个有序状态

【一、排序】小结
排序算法除此之外还有很多，如：
希尔（shell）排序，堆排序，桶排序，归并排序，基数排序……
这里就不再逐个说明（归并排序很有说明价值，但打算说到分治策略时再说）
实际上，实用性最高的就是快速排序QuickSort。
针对排序，接下来还要稍作补充：

【一、排序】补充：
多关键字排序
在实用上，往往出现多关键字排序：
如：
若干学生，按总分排名，若总分相同，则按数学成绩排名
又或者：
招聘员工，按(学历*0.7+外貌*0.3)的录用价值排名
这时，难道要进行多次排序吗？
如果你足够聪明，你就能意识到，
实际上，只要改变“判断大小”这一部分就行了
AS自带的sort也有这个功能，就是“比较函数”
实质就是，把a>b这个表达式，变成f(a,b)这个函数
按上面学生的例子，定义函数
function 大于(a:int,b:int):int;
{
若(a.总分>b.总分){返回1;}
若(a.总分<b.总分){返回-1;}
若(a.数学>b.数学){返回1;}
若(a.数学<b.数学){返回-1;}
返回0;
}
按上面招聘的例子，定义函数
function 大于(a:int,b:int):int;
{
若(a.学历*0.7+a.外貌*0.3>b.学历*0.7+b.外貌*0.3){返回1;}
若(a.学历*0.7+a.外貌*0.3<b.学历*0.7+b.外貌*0.3){返回-1;}
返回0;
}
排序部分就拿快排来说
function qs(b:int,e:int):void
{
if (b>=e)
{
return;
}
var i:int=b,j:int=e,mid:int=arr[int(b/2+e/2)],t:int;
do
{
while (大于(arr[i],mid)==-1)
{
i++;
}
while (大于(arr[j],mid)==1)
{
j--;
}
if (i<=j)
{
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
i++;
j--;
}
} while (i<=j);
qs(b,j);
qs(i,e);
}
qs(0,arr.length-1);
只需小改动就可完成多关键字排序

【二、逻辑】
逻辑是离散数学的一个分支，也是各位平时运用得最多的一个，
相比排序，逻辑的运用之广泛不言而喻。
基本内容：
定义：var a:Boolean = true;
运算：
逻辑和(and)写作 &&
逻辑非(not)写作 !
逻辑或(and)写作 ||
按位异或(xor)写作 ^
逻辑异或(xor)用 !=
这里只有异或是不常用到的，实际上a xor b可以转化为a != b，
所以异或的作用不是很大。