May 22, 2007

恶搞 qsort 测试代码

//Array类的交换和判断是否有序的方法
Array.prototype.swap = function (a, b) {
var tmp = this[a];
this[a] = this[b];
this[b] = tmp;
}

Array.prototype.isInOrder = function () {
for (var i =0; i <> this[i+1]) return false;
return true;
}

//简短的快速排序,只需一个数组作参数
function qsort (arr, l, u) {
l = l || 0;
u = ((u != 0) &&amp; (u == undefined)) ? arr.length : u;
if (l >= u) return;
var m = l;
for (var i = l+1; i <= u; i++)
if (arr[i] < arr[l])
arr.swap(++m, i);
arr.swap(l, m);
qsort(arr, l, m-1);
qsort(arr, m+1, u);
}

Math.rand = function (start, end) {
if (end == undefined) {
end = start;
start = 0;
}
return start+Math.random()*(end-start);
}

Math.randInt = function (start, end) {
return Math.round(Math.rand(start, end));
}

//生成待排序的大规模随机整数数组
function randRange (len, start, end) {
var range = new Array(len);
for (var i = 0; i < len; i++)
range[i] = Math.randInt(start, end);
return range;
}

//把测试代码绑定在qsort()函数上
qsort.test = function (len, start, end) {
var tmpArr = randRange(len, start, end);
this(tmpArr);
return tmpArr.isInOrder();
}

PS: 我一个同学在电脑课上用Firefox玩randRange(10000)之类的东西玩了半节课……

No comments: