/**
原理：节点的子节点先遍历，再遍历同级节点
node:一个节点
fn:每个节点需要执行的操作
**/
async deep(node,fn){
  await fn(node);
  if(node.children){
    for(let i=0;i<node.children.length;i++){
      await this.deep(node.children[i],fn);
    }
  }
}

/**
原理：节点的同级节点先遍历，再遍历子节点
node:一个节点
fn:每个节点需要执行的操作
**/
async wide(node,fn){
  let queue = [];
  queue.push(node);
  while (queue.length != 0) {
    let item = queue.shift();
    await fn(item);
    for (let j = 0; j < item.children.length; j++) {
      queue.push(item.children[j])
    }
  }
}

function run(fn,ms){
  let tm=null;
  return function(){
    clearTimeout(tm);
    tm=setTimeout(()=>{
      fn.apply(this, arguments);
    },ms)
  }
}

function run(fn,ms){
  let canrun=true;
  return function(){
    if(!canrun)return;
    canrun=false;
    tm=setTimeout(()=>{
      fn.apply(this, arguments);
      canrun=true;
    },ms)
  }
}

/**
 特点:优化后遍历次数可以较小，基本满足前端常见排序要求了
 **/
function bubbleSort(arr) {
  let len = arr.length;
  let k = len - 1;
  let isSwap = false;//是否交换标记
  let pos = 0;//最后一次交换位置
  let temp = null;
  for (let i = 0; i < len; i++) {
    isSwap = false;
    pos = 0;
    for (let j = 0; j < k; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
        pos = j;
        isSwap = true;
      }
    }
    if (!isSwap) { return arr; }
    k = pos;
  }
  return arr;
}

/**
特点：最大数据交换次数是固定的数组长度相等，遍历次数永远固定
 **/
function selectionSort(arr) {
  let len = arr.length;
  let minIndex, temp;
  for (let i = 0; i < len - 1; i++) {
    minIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {   //寻找最小的数
        minIndex = j;         //将最小数的索引保存
      }
    }
    if(i!=minIndex){
      temp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = temp;
    }
  }
  return arr;
}

function quickSort(arr){  
  if (arr.length <= 1) {  
    return arr;  
  }  

  //取出数组中间的一位作为比较对象 如 [5,0,6,3,8] 则取出6，数组变为[5,0,3,8]
  var povitIndex = Math.floor(arr.length/2);  
  var povit = arr.splice(povitIndex, 1)[0];  

  //接下来就是遍历[5,0,3,8]将比6小的数放入到leftArr,相反放入rightArr
  var leftArr = [], rightArr = [];  
  for (var i = arr.length - 1; i >= 0; i--) {  
    if (arr[i] < povit) {  
        leftArr.push(arr[i]);  
    } else {  
        rightArr.push(arr[i]);  
    }  
  }  
  //遍历下来后生成了 leftArr[5,0,3],rightArr[8]

  //接下来递归调用，继续将leftArr和rightArr这2个数组重复以上的操作
  //最终将leftArr+povit+rightArr 合并为一个数组即得最终排序后结果
  return quickSort(leftArr).concat([povit], quickSort(rightArr));  
}