推荐高效的数组重排算法_新疆二域设计网络公司

在程序设计中很多时候我们需要对数组重排，所以探求一种高效的重排算法还是很有必要的。上午逛论坛时看到一个帖子中的“简洁、高效”的重排算法，如下：

function randomsort() {
return Math.random()>.5 ? -1 : 1;
}
function arrRandomSort(arr){
arr.sort(randomsort);
}

仅仅4行代码，当时我那个惭愧啊，自己以前怎么没有想到这么简单的方法了？还绕了一个大圈子来写这个重排。激动之后做了个测试：

使用上面的算法对一个1000个元素的数组进行重排，执行时间是居然是210毫秒，有些恐怖，初步估计是因为sort函数造成的，因此将上面代码里添加了一个计数器来跟踪sort参数中的函数的执行次数。

_global.n = 1;
function randomsort() {
n++;
return 1;
}
function arrRandomSort(arr){
arr.sort(randomsort);
}
_array = [];
for (i = 0;i<1000;i++){
_array.push(Math.random());
}
arr = [];
var t1 = getTimer();
arr = arrRandomSort(_array);
var t2=getTimer();
trace(t2-t1);
trace(n);

看来效率的消耗果然是因为sort函数，对这1000个元素的数组进行排序，运行了7153毫秒，randomsort函数被执行了499501次，显然，这段看似简洁的代码其实并不实用。而sort函数内部到底是使用什么算法来完成的这个排序了？以至于需要执行这么多次比较函数。简单排序？快速排序？我也不太清楚，有空了再做进深入测试，暂且不在此文讨论范围之内。
　　在我搜索Array.sort的内部实现时发现了一个帖子《用array.sort进行随机排序》，原来有关于用sort方法排序已经引起了很大的争议，而此文作者是站在支持sort排序的立场的，通过与别人的代码比较，他最初得出的结论是Array.sort来做数组重排是有利的，而跟帖中又出现了一个更为高效的算法，此算法跟sort方法相比效率要高很多，特推荐出来供大家借鉴。下面是我用此算法和sort算法做的对比，分别对100个元素的数组进行100次重排，比较其总消耗的时间，结果消耗时间分别为70MS和1448MS，其中红色部分为效率更佳算法：

/*算法一 */
Array.prototype.random = function($lim:Number):Array {
var tmp:Array = this.concat();
var len:Number = tmp.length;
//trace(($lim && $lim<(len-1)) ? $lim : (len-1));
for (var i = 0; i<(($lim && $lim<(len-1)) ? $lim : (len-1)); i++) {
//获取最末索引
var n:Number = len-i;
//索引集合中随机一个
var r:Number = random(n);
//将选出来的元素放置到数组后面，以保证不在随机范围之内
var temp = tmp[r];
tmp[r] = tmp[n-1];
tmp[n-1] = temp;
}
return tmp.slice(-$lim);
};
/*算法二*/
function getRandom() {
return Math.random()<0.5 ? 1 : -1;
}
function arrayRandom(arr) {
arr.sort(getRandom);
return arr;
}
//---------------------------------------------------
//测试次数
var times = 100;
//生成测试数据
var _array = [];
for (var i = 0; i<100; i++) {
_array.push(i);
}
//算法一:
var t1 = getTimer();
for (i=0; i<TIMES; i++) {
var arr = new Array();
arr = _array.random();
}
//trace(arr);
var t2 = getTimer();
trace("算法一耗时:"+(t2-t1)+"MS");
//算法二：
var t1 = getTimer();
for (i=0; i<TIMES; i++) {
var arr = new Array();
arr = arrayRandom(_array);
}
//trace(arr);
var t2 = getTimer();
trace("算法二耗时:"+(t2-t1)+"MS");
//Result
//算法一耗时:70MS
//算法二耗时:1448MS

实现原理并不复杂，首先将要重排的数组复制一份来操作，虽然效率上有点消耗但还是值得的，这样保证了原数组的不变动。然后很巧妙地将数组“分为”两个部分，每次从数组左边部分随机取出一个元素，然后将该元素交换到右部分的首元素，而分界线从数组末端往顶端移动，这样就保证了选出来的元素不会再被选出来，对于有N个元素的数组只需要进行N次此类操作就可以实现了数组的重排。
出处：http://www.v-sky.com/blog/index.php/archives/177