javascript shuffle(随机打乱数组)

想做一个算法的演示工具,需要随机对一个有序的数据随机打乱。
那么先想到的就是在数组中随机选择两个不同的下标,并对其中的元素进行交换,
实现起来很简单,代码如下。

function shuffle(aArr){
	var iLength = aArr.length,
		i = iLength,
		mTemp,
		iRandom;

	while(i--){
		if(i !== (iRandom = Math.floor(Math.random() * iLength))){
			mTemp = aArr[i];
			aArr[i] = aArr[iRandom];
			aArr[iRandom] = mTemp;
		}
	}

	return aArr;
}

有了这种实现之后,又想到Array有个sort方法,我们不妨利用一下,
于是就有了以下实现:

function shuffleUseSort(aArr){
	return aArr.sort(function(a, b){
		return (0.5 - Math.random());
	});
}

那么对此做一些性能测试,

		function shuffle(aArr){
			var iLength = aArr.length,
				i = iLength,
				mTemp,
				iRandom;

			while(i--){
				if(i !== (iRandom = Math.floor(Math.random() * iLength))){
					mTemp = aArr[i];
					aArr[i] = aArr[iRandom];
					aArr[iRandom] = mTemp;
				}
			}

			return aArr;
		}

		function shuffleUseSort(aArr){
			return aArr.sort(function(a, b){
				return (0.5 - Math.random());
			});
		}

		function Profiler(){
			var iStart;
			this.start = function(){
				iStart = (new Date()).getTime();
			};
			this.stop = function(){
				return (new Date()).getTime() - iStart;
			};
		}

		function createArr(){
			var i = 1000000, aArr = [];
			while(i--){
				aArr[i] = i;
			}
			return aArr;
		}
		var aArr1 = createArr(),
			aArr2 = createArr();

		var oProfiler = new Profiler();
		oProfiler.start();
		shuffle(aArr1);
		var iTimeShuffle = oProfiler.stop();


		oProfiler.start();
		shuffleUseSort(aArr2);
		var iTimeShuffleUseSort = oProfiler.stop();

		alert(['shuffle \t: ', iTimeShuffle, '\n' + 'shuffleUseSort : ', iTimeShuffleUseSort].join(''));

结果很明显,shuffle的效率高一些。

Post a Comment

Your email is never shared. Required fields are marked *

*
*