2020前端面试（数据结构）

常见排序算法

冒泡排序

function bubbleSort(arr) {
  for(let i = 0; i < len-1; i++) {
    let len = arr.length
    for(let j=  0; j < len-i-1; j++) {
      if(arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }
  return arr
}

快速排序

let quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　let pivotIndex = Math.floor(arr.length / 2);
　　let pivot = arr.splice(pivotIndex, 1)[0];
　　let left = [];
　　let right = [];
　　for (let i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot)  {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
}

选择排序

const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];

function swap(arr, i, j){
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function selectionSort(arr){
  for(let i = 0; i < arr.length - 1; i++){
    let index = i;
    for(let j = i+1; j < arr.length; j++){
      if(arr[index] > arr[j]){
        index = j;
      }
    }
    swap(arr, i, index);
  }
  return arr;
}

console.log(selectionSort(arr)); //[ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100 ]

插入排序

const arr = [1, 20, 10, 30, 22, 11, 55, 24, 0, 31, 88, 12, 100, 50 ,112];

function insertSort(arr){
  for(let i = 0; i < arr.length; i++){
    let temp = arr[i];
    for(let j = 0; j < i; j++){
      if(temp < arr[j] && j === 0){
        arr.splice(i, 1);
        arr.unshift(temp);
        break;
      }else if(temp > arr[j] && temp < arr[j+1] && j < i - 1){
        arr.splice(i, 1);
        arr.splice(j+1, 0, temp);
        break;
      }
    }
  }
  return arr;
}

console.log(insertSort(arr));  //[ 0, 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100, 112 ]

数组扁平化

递归

function flatten(arr){
    let res = [];
    for(let i = 0; i < arr.length; i++){
        if(Array.isArray(arr[i])){
            res = res.concat(flatten(arr[i]));
        }else{
            res.push(arr[i]);
        }
    }
    return res;
}

reduce

function flatten(arr){
    return arr.reduce(function(prev,item){
        return prev.concat(Array.isArray(item)?flatten(item):item);
    },[]);
}

toString

function flatten(arr){
    return arr.toString().split(',').map(function(item){
        return item;
    })
}

树的遍历

深度优先遍历

function deepTraversal(node){
    let nodes=[];
    if(node!=null){
        nodes.push[node];
        let childrens=node.children;
        for(let i=0;i<childrens.length;i++)
            deepTraversal(childrens[i]);
    }
    return nodes;
}

广度优先遍历

function wideTraversal(node){
    let nodes=[],i=0;
    if(node!=null){
        nodes.push(node);
        wideTraversal(node.nextElementSibling);
        node=nodes[i++];
        wideTraversal(node.firstElementChild);
    }
    return nodes;
}

URL获取参数

正则表达式

function getUrlParam(name) {
            var reg = new RegExp("(^|&)" + name + "=([^&]*)(&|$)");
            var r = window.location.search.substr(1).match(reg);
            if (r != null) {
                return unescape(r[2]);
            } else {
                return null;
            }
}