【9RIA—沐枫】—【基础小知识】第21节（选择排序、插值排序、二分法排序）

9RIA-沐枫

转载：9RIA游戏开发者社区（天地会）
作者：沐枫（原天地会大神）


【基础小知识】系列教程（总目录）——沐枫大神出品

[Actionscript3] 纯文本查看 复制代码

ar arr:Array=[2,22,11,3,33,44,4];
var k:uint=0;
var len:uint=arr.length;
var temp:uint=0;
for(var i:uint=0;i<len-1;i++)
{
for(var j:uint=i+1;j<len;j++)
{
k=i;
if(arr[k]>arr[j])
{
k=j;
}
if(i!=k)
{
temp=arr[i];
arr[i]=arr[k];
arr[k]=temp;
}
}
}
trace(arr);//2,3,4,11,22,33,44

原理如下：
当第一个与第二个比较大小时，如果第二个比上一个小，那么就把相对较小的索引值传给k，最后在看看k是不是等于i如果不等于就把他们交换下值，然后再把i=k，接着往下比较。you Know?

[Actionscript3] 纯文本查看 复制代码

//——————————插值排序———————————————
var arr:Array=[15,3,7,2,12,6,8,1,9];
var krr:Array=[];
krr[0]=arr[0];
var len:uint=arr.length;
for(var i:uint=0;i<len;i++)
{
var ken:uint=krr.length;
for(var j:uint=0;j<ken;j++)
{
if(arr[i]<krr[j])
{
krr.splice(j,0,arr[i]);
break;//一旦比较一次立马跳出循环，免得最后插入好几个数。
}
}
}
trace(krr);//1,2,3,6,7,8,9,12,15
//————————————————————————————
//原理很简单，就是不停地比大小，然后往新数组里插入最小值。
//不知大家有没有试过把15换成0看看，结果是肯定的，没错，这种排序法也是美中不足。

[Actionscript3] 纯文本查看 复制代码

//——————————二分法排序———————————————
var arr:Array=[15,3,7,2,12,6,8,1,9];
var krr:Array=[];
krr[0]=arr[0];
var len:uint=arr.length;
var l:uint=0;
var r:uint=0;
var p:uint=0;
var n:uint=0;
for(var i:uint=1;i<len;i++)
{
n=krr.length;
l=0;
r=n;
for(var j:uint=0;j<n;j++)
{
p=Math.floor(l+(r-l)/2);
if(krr[p]<arr[i])
{
l=p+1;
}
else
{
r=p;
}
if(l==r)
{
krr.splice(l,0,arr[i]);
break;
}
}
}
trace(krr);//1,2,3,6,7,8,9,12,15
//————————————————————————————
//二分法，顾名思义，高中数学，不，初中数学上我们就接触过，所以在这不多加解释

感谢：感谢 samchow 提的意见是代码得到优化。

本人正在努力更新中，请各位多多支持，据说该是圣诞节了，祝大家节日愉快！