欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

排序算法之js实现回顾

程序员文章站 2022-03-18 16:02:14
1. 时间复杂度就是while的次数,二分查找O(h)=O(log2n) 2. 节点的广度优先遍历 3. DOM树的深度优先遍历 4. 冒泡排序(O(n^2)) 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该 ......

 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));
}