Review of js implementation of sorting algorithm

1. Time complexity is the number of while. Binary search O(h)=O(log2n)

2. Breadth first traversal of nodes

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. Depth first traversal of DOM tree

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. Bubble sort (O(n^2))

It repeatedly visits the sequence to be sorted, compares two elements at a time, and exchanges them if they are in the wrong order. The work of the visit sequence is repeated until there is no need to exchange, that is to say, the sequence has been sorted.

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)

The data to be sorted is divided into two independent parts by a single sorting. All the data in one part is smaller than all the data in the other part, and then the two parts are sorted rapidly according to this method. The whole sorting process can be recursive, so that the whole data becomes an ordered sequence.

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

Keywords: Javascript

Added by curioadmin on Tue, 31 Mar 2020 08:17:44 +0300