数组洗牌算法

在做拍拍首页改版过程碰到一个需求，抽象出来的意思就是：从一个数组当中随机抽出几个组成一个新的数组，然后思考了一下，代码如下()：

// 判断数组是否包含某个元素
  Array.prototype.contains = function(obj) {
      var i = this.length;
      while (i--) {
          if (this[i] === obj) {
              return true;
          }
      }
      return false;
  };

  // 在min和max之间随机生成一个数字
  var randomNum = function (min, max) {
      if (max == undefined) {
          max = min;
          min = 0;
      }
      return Math.floor(Math.random() * (max - min) + min);
  };

function shuffle (obj, arrLen) {
	var randomArr = [],
            $obj = obj,
            len = $obj.length + 1;

        while ( randomArr.length < arrLen ) {
            var num = randomNum (len);
            if ( randomArr.contains(num) ) {
                continue;
            }
            randomArr.push(num);
        }	
        return randomArr;
}

写完之后，虽然功能实现了，但是发现代码有点多而且逻辑有点复杂，我考虑的是从数组中随机抽出一个元素放入一个新的数组，只要新的数组的个数未到达指定个数，就不断循环从原数组中取元素，同时不能取出跟新数组重复元素，这样一来时间复杂度相对较高。

回到正题，doodle了一下，发现原来这个可以用传说中的洗牌算法来实现，基本原理是：从所有元素中随机选取一个与第一个元素进行交换，然后在第二个之后选择一个元素与第二个交换，直到最后一个元素。这样能确保每个元素在每个位置的概率都是1/n。

于是改进算法，代码如下：

//生成从1到length之间的随机数组

function shuffleArray ( len ) {
	var arr = [], temp, index, i ;
	if ( !len ) {
		return false;
    }
    for ( i = 1; i <= len; i++) {
		arr.push(i-1);
	}

	//利用洗牌算法打乱数组
	for ( i = 1; i <= len; i++ ) {
		//随机生成i到len之间的随机数
		index = parseInt(Math.random() * ( len - i ), 10) + i;
		if ( index != i ) {
			temp = arr[i];
			arr[i] = arr[index];
			arr[index] = temp;
		}
	}

	return arr;
}

思考继续改进中…