乱序.md

乱序

sort实现乱序有问题，乱序的概率不平均

v8实现sort方法：

1. 当目标数组长度小于 10 时：使用插入排序；
2. 反之，使用快速排序和插入排序的混合排序

插入排序

插入排序的算法中，当待排序元素跟有序元素进行比较时，一旦确定了位置，就不会再跟位置前面的有序元素进行比较，所以就乱序的不彻底

function sort1(arr) {
  for (var i = 0; i < arr.length; i++) {
    for (var j = i; j >= 0; j--) {
      if (arr[j] < arr[j - 1]) {
        var temp = arr[j]
        arr[j] = arr[j - 1]
        arr[j - 1] = temp
      } 
    } 
  }
  
  return arr
}

function sort2(arr, cb){
	for(var i = 1; i < arr.length; i++) {
		var val = arr[i]
		for(var j = i - 1; j >= 0; j--) {
		  var order = cb(arr[j], val)
			if(order > 0) {
				arr[j + 1] = arr[j]
			}else {
				break
			}
		}
		arr[j + 1] = val
	}
	return arr
}

sort2([5, 4, 3, 2, 1], function (a, b){
  return a > b
})

乱序实现

遍历数组元素，然后将当前元素与以后随机位置的元素进行交换

function shuffle(a) {
  for (let i = a.length; i; i--) {
    let j = Math.floor(Math.random() * i);
    [a[i - 1], a[j]] = [a[j], a[i - 1]];
  }
  return a;
}