IT虾米网

算法之js实现回顾

mate10pro 2018年05月27日 编程语言 1198 0

 1. 时间复杂度就是while的次数,二分查找O(h)=O(log2n)

2. 节点的广度优先遍历

function traverse(root){ 
  const queue = [root]; 
  while(queue.length){ 
    const node = queue.shift(); 
    printInfo(node); 
    if(!node.children.length){ 
      continue; 
    } 
    Array.from(node.children).forEach(x=>queue.push(x)); 
  } 
} 
function printInfo(node){ 
  console.log(node.nodeName, node.className) 
} 
traverse(root)

3. DOM树的深度优先遍历

function printInfo(node, layer){ 
  var str = '' 
  for (let i = 1; i < layer; i++) { 
    str += ' ' 
  } 
 console.log(`${layer}:${str}${node.tagName}.${node.className}`); 
} 
function dfs = (rootNodes, rootLayer) => { 
  const roots = Array.from(rootNodes) while (roots.length) { 
      const root = roots.shift(); 
      printInfo(root, rootLayer); 
      if (root.children.length) { 
        dfs(root.children, rootLayer + 1) 
      } 
    } 
} 

4. 冒泡排序(O(n^2))

      它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

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

5. 快排(O(nlogn))

      通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

var quickSort = function(arr){ 
  if(arr.length <= 1) {return arr;} 
  const midIndex = Math.floor(arr.length / 2); 
  const mid = arr.splice(midIndex, 1)[0]; 
  const left = [], right = []; 
  arr.forEach(function(item){ if(item < mid){ 
      left.push(item); 
    }else{ 
      right.push(item); 
    } 
  }) 
  return quickSort(left).concat([mid], quickSort(right)); 
}

6. 折半查找(logn)

function halfSearch(target, arr){ 
  let start = 0, 
      end = arr.length - 1; 
  while(start <= end){ 
    let mid = parseInt(start + (end - start) / 2); if(target == arr[mid]){ 
      return mid; 
    }else if(target > arr[mid]){ 
      start = mid+1; 
    }else{ 
      end = mid-1; 
    } 
  } 
  return -1; 
}

 

评论关闭
IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!