常见算法相关的JavaScript实现
编者按：本文作者刘冰晶，奇舞团前端开发工程师。
还有不到半个月就要入秋了，天气逐渐凉爽起来，订阅奇舞周刊的你是不是逐渐萌生想要来奇舞团面试下的想法呢？
今天的文章是关于算法相关的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); } }本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-09-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录