这是一个比起前两个排速算法效率高的多的算法
首先看下该算法的原理
由于偶表达能力实在是....... 咱还是用图片来表达吧.

通过上面的这张图片应该不难看出，该算法是先将数组分成4对(array.length/2)然后对每一对进行合并，成为2个元素的排序序列，接着将每两个连续的2元素的序列合并成一个4元素的排序序列，依此类推.....
这里还用到了以前说到的合并有序列表的算法，不过要把上次的合并算法稍微改一下，改成合并一个数组中的2个有序子数组(详见下面的代码块)
欢迎指教:wink:

[as]
/*
* 《算法设计技巧与分析》
* page 9-11
* 自底向上合并排序
*/
function bottomUpSort(ary:Array):Array {
var len:Number = ary.length-1;
var t:Number = 1;
var s:Number;
var i:Number;
while (t<=len) {
s = t;
t = 2*s;
i = -1;
trace("\n**********\n"+["s="+s, "t="+t, "i="+i]);
trace("**内部循环开始**");
while (i+t<=len) {
trace("i="+i);
trace("merge( "+[i+1, i+s, i+t]+" )");
merge(ary, i+1, i+s, i+t);
i += t;
trace("i="+i);
trace("i+t="+i+"+"+t+"="+(i+t)+"\n-");
}
// end while
trace("**内部循环结束**");
trace("i+s="+i+"+"+s+"="+(i+s));
if (i+s trace("::::merge( "+[i+1, i+s, len]+" )");
merge(ary, i+1, i+s, len);
}
trace(ary+"\n------------------------------\n");
}
// end while
return ary;
}
/*
* 《算法设计技巧与分析》
* page 6-7
* 合并两个已排序的子数组
* 0 <= begin <= mid *
* //test:
* var a:Array = [0,2,5,6,10,1,3,4,8,9];
* trace(merge(a, 1, 4, a.length-1));
*/
function merge(ary:Array, begin:Number, mid:Number, end:Number):Array {
var ind1:Number = begin;
var ind2:Number = mid+1;
var i:Number = 0;
var temp:Array = [];
while (ind1<=mid && ind2<=end) {
if (ary[ind1]<=ary[ind2]) {
temp[i] = ary[ind1];
ind1++;
} else {
temp[i] = ary[ind2];
ind2++;
}
i++;
}
if (ind1 == mid+1) {
for (var k = ind2; k<=end; k++) {
temp.push(ary[k]);
}
} else {
for (var k = ind1; k<=mid; k++) {
temp.push(ary[k]);
}
}
for (var k = begin; k<=end; k++) {
ary[k] = temp.shift();
}
return ary;
}
//test:
var a:Array = [];
trace("~~~~~~~~~~~~~~~~~奇数个元素测试[9]~~~~~~~~~~~~~~~~~");
for (var i = 1; i<=9; i++) {
a.push(Math.round(Math.random()*100));
}
trace("<>: "+a);
trace("<<: "+bottomUpSort(a));
trace("\n=========================================\n~~~~~~~~~~~~~~~~~偶数个元素测试[10]~~~~~~~~~~~~~~~~~");
a = [];
for (var i = 1; i<=10; i++) {
a.push(Math.round(Math.random()*100));
}
trace("<>: "+a);
trace("<<: "+bottomUpSort(a));
[/as]