Front-end sorting algorithm and search algorithm handwriting

You can view various sort animations: visualgo.net/zh

Common sorting algorithms for front-end interviews

Example array: let arr = [9, 7, 6, 4, 7, 3, 4, 8, 12, 43, 76, 32]

Bubble sort

//O(n*2)
function bubbling(arr) {
  var len = arr.length
  for (var i = 0; i < len; i++) {
    for (var j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // Compare adjacent elements in pairs; [arr[j], arr[j +1]] = [arr[j + 1], arr[j]] // Complete the element exchange through deconstruction}}}return arr
}
Copy the code

Selection sort

//O(n*2)
function choice(arr){
  var len = arr.length;
  for(let i=0; i<len; i++){let flag = i
    let min = arr[i]
    for(let j = i+1; j<len; j++){if(min>arr[j]){
        min = arr[j]
        flag = j
      }
    }
    [arr[i],arr[flag]] = [arr[flag],arr[i]]
  }
Copy the code

Insertion sort

//O(n*2)
 function insert(arr) {
  let len = arr.length
  for (let i = 1; i < len; i++) {
    let temp = arr[i]
    let j = i
    while (j >= 0) {
      if (temp < arr[j - 1]) {
        arr[j] = arr[j - 1]}else {
        break
      }
      j--
    }
    arr[j] = temp
  }
  return arr
}
 
Copy the code

Quick sort

//O(nlogn)
function quick(arr) {
  if (arr.length < 2) {
    return arr
  }
  let pivot = arr[0]
  let left = []
  let right = []
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] <= pivot) {
      left.push(arr[i])
    } else if (arr[i] > pivot) {
      right.push(arr[i])
    }
  }
  left = quick(left)
  right = quick(right)

  return [...left, pivot, ...right]
}

console.log(quick(arr))
Copy the code

Merge sort

//O(nlogn)
function merge(left, right) {
  let i = 0
  let j = 0
  let arr = []
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      arr.push(left[i++])
    } else if (left[i] >= right[j]) {
      arr.push(right[j++])
    }
  }
  if(i === left.length) { arr.push(... right.slice(j)) }if(j === right.length) { arr.push(... left.slice(i)) }return arr
}
function mergeSort(array) {
  if (array.length < 2) {
    return array
  }
  let m = Math.floor(array.length / 2)
  let left = mergeSort(array.slice(0, m))
  let right = mergeSort(array.slice(m))
  return merge(left, right)
}

Copy the code

Search algorithm

Sequential search

//O(n)
function sequenal(arr,n){
  for(let i = 0; i<arr.length; i++){if(n == arr[i]){
      return i
    }
  }
  return -1
}
Copy the code

Binary search

//O(logn)
function binary(arr,n){
  arr.sort((a,b) = > a-b)
  let low = 0
  let high = arr.length-1
  while(low<=high){
    const mid = Math.floor((low+high)/2)
    const element = arr[mid]
    if(element < n){
      low = mid+1
    }else if(element > n){
      high = mid-1
    }else{
      return mid
    }
  }
  return -1
}

Copy the code