Max—— 前端攻城狮 's Blog

A Simple pure blog generated by jekyll

Javascript实现快排算法的性能测试

<< Back

JS快速排序算法性能测试

1.首先写一个生成随机数组的方法

function createRandomArray(random, length){
	var  arr = [],
	     len = length - 1;
	for(var i = 0; i < len; i++){
		arr[i] = Math.floor(Math.random() * (random + 1));
		arr.push(arr[i]);
	}
	return arr;
}
	

2.再实现快排算法(平衡快排)

function quickSort(arr){
	// 如果数组只有一项,就返回原数组
	if(arr.length <= 1){
		return arr;
	} else {
		    // 取数组中间项数
		var pivotIndex = Math.floor(arr.length / 2),
		    // 取到剔除数组的中间改项数
		    pivot = arr.splice(pivotIndex, 1),
		    leftArray = [],
		    rightArray = [];
		for(var i = 0, len = arr.length; i < len; i++){
			// 如果该循环项小于“基准”项,放进左边数组,否则放进右边数组
			if(arr[i] < pivot){
				leftArray.push(arr[i]);
			} else {
				rightArray.push(arr[i]);
			}
		}
		// 不断递归调用,然后把结果拼接成最后的结果数组
		return arguments.callee(leftArray).concat(pivot, arguments.callee(rightArray));
	}
}
	

3.然后测试效率

(function(){
	var start = new Date();
	var targetArray = createRandomArray(10000,50000);
	var arrOver = new Date();
	var result = quickSort(targetArray);
	var end = new Date();
	console.log('随机生成50000个数组,耗时' + (arrOver - start )/ 1000 + '秒' + '\n' + '将此50000个数组进行快速排序,耗时' + (end - arrOver) / 1000 + '秒');
	console.log(targetArray);
	console.log(result);
})()
	

控制台如下: 快排算法性能

可以看出,由于在递归调用中不断地迭代数组计算,其性能有显著下降。

发表于: 04 Dec 2014