常見算法相關的JavaScript實現

• 2019 年 10 月 8 日
• 筆記

編者按：本文作者劉冰晶，奇舞團前端開發工程師。

還有不到半個月就要入秋了，天氣逐漸涼爽起來，訂閱奇舞周刊的你是不是逐漸萌生想要來奇舞團面試下的想法呢？

今天的文章是關於算法相關的JavaScript實現，既然都已經漏題了，你還不過來試試嗎？

位運算相關

計算漢明重量

function hammingWeight(n) {    let num = 0;    while(n !== 0) {      n &= (n - 1);      num++;    }    return num;  }

判斷奇偶

funciton isOdd(n) {    return n & 1 === 1;  }

二分查找

非遞歸方法

function binarySearch(nums, target) {    let low = 0;    let high = nums.length - 1;      while(low <= high) {      let mid = parseInt((low + high) / 2);      if(nums[mid] === target) {        return mid;      }      if(nums[mid] > target) {        high = mid - 1;      }      if(nums[mid] < target) {        low = mid + 1;      }    }    return -1;  }

遞歸方法

function binarySearch(nums, target) {    let low = 0;    let high = nums.length -1;    const binaryWalker = (nums, low, high, target) => {      if(low > high) return -1;      const mid = parseInt((low + high) / 2);      if(nums[mid] === target) return mid;      if(nums[mid] > target) return binaryWalker(nums, low, mid - 1, target);      if(nums[mid] < target) return binaryWalker(nums, mid + 1, high, target);    }    return binaryWalker(nums, low, high, target);    }

常見排序

快速排序

function quickSort(arr) {    if(arr.length <= 1) return arr;      let left = [];    let right = [];      let pivot = arr[0];      for(let i = 1; i < arr.length; i++) {      if(arr[i] >= pivot) {        right.push(arr[i]);      } else {        left.push(arr[i]);      }    }      return [...quickSort(left), pivot, ...quickSort(right)];  }

冒泡排序

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

二叉樹遍歷相關

先序遍歷（中->左->右）

遞歸實現

function preOrderTraverse(root) {    if(root) {      console.log(root);      preOrderTraverse(root.left);      preOrderTraverse(root.right);    }  }

非遞歸實現

function preOrderTraverse(root) {    let stack = [];      if(root) {      stack.push(root);    }      while(stack.length) {      let temp = stack.pop();      console.log(temp);        if(temp.right) stack.push(temp.right);        if(temp.left) stack.pus(temp.left);    }  }

中序遍歷（左->中->右）

遞歸實現

function midOrderTraverse(root) {    if(root) {      midOrderTraverse(root.left);      console.log(root);      midOrderTraverse(root.right);    }  }

非遞歸實現

function midOrderTraverse(root) {    let stack = [];    while(true) {      while(root) {        stack.push(root);        root = root.left;      }        if(!stack.length) break;        let temp = stack.pop();      console.log(temp);      root = temp.right;    }  }

後序遍歷（左->右->中）

遞歸實現

function postOrderTraverse(root) {    if(root) {      postOrderTraverse(root.left);      postOrderTraverse(root.right);      console.log(root);    }  }

非遞歸實現

function postOrderTraverse(root) {    let stack = [];    let rest = [];    if(root)stack.push(root);    while(stack.length) {      let temp = stack.pop();      rest.push(temp);      if(temp.left) stack.push(temp.left);      if(temp.right) stack.push(temp.right);    }    return rest.reverse();  }

層次遍歷

function levelTraverse(root) {    if(!root) return;    let stack = [];    stack.push(root);      while(stack.length) {      let temp = stack.shift();      console.log(temp);      if(temp.left) stack.push(temp.left);      if(temp.right) stack.push(temp.right);    }  }