1. Why does the front end learn algorithms

Here are some straightforward reasons that one cannot refute

  1. All kinds of big factory interview requires interview algorithm
  2. Proficient in algorithms can better read the source code of some frameworks, such as React, Vue diff calculation
  3. Algorithms can make your mind more flexible
  4. Do you want to do a lifetime of add, delete, change and check

Two, bubble, insert, select

Bubble sort

  • Concept: Bubble sort only operates on two adjacent pieces of data. Each bubbling operation compares two adjacent elements to see if they meet the size relationship requirements. If you don’t, switch them. One bubble moves at least one element to its proper position, n times, and n numbers are sorted.
  • Time complexity O(N2)
  • Space complexity O(1)
  • Code implementation (from small to large), two layers for loop, the first layer represents the number of bubbles, the second layer compares adjacent elements, the second traversal need to pay attention to is already bubbling elements do not need to traversal
function bubbleSort(target) { if (! target || ! Target instanceof Array | | target. Length < 2) {return target | | []} let len = target. Length / / traverse len, For (let I =0; i<len; I ++) {let isDone = false // j < len-i -1 because len-i -1 is bigger than before for(let j=0; j<len - i - 1; If (target[j] < target[j]) {if (target[j] < target[j]) { Let tem = target[j] target[j] = target[j + 1] target[j + 1] = tem isDone = true}} isDone) break } }Copy the code

Insertion sort

  • Concept: Divide the array into space and unordered space. The initial value of the ordered space is the first item in the array. Take out an unordered space and insert it into the appropriate position in the ordered space
  • Time complexity O(N2)
  • Space complexity O(1)
  • Code implementation (from small to large), a two-layer for loop, the first traverses the unordered space, the second traverses the ordered space, inserts elements into the appropriate position (including movement and insert)
function insertSort(target) { if (! target || ! Target instanceof Array | | target. Length < 2) {return target | | []} let len = target. Length / / traverse unordered space for (let I = 1; i<len; i++) { let value = target[i] let j = i - 1 for(; j>=0; If (target[j] > value) {// If (target[j] < target[j], target[j] = target[j]} else Break} target[j + 1] = value} return targetCopy the code

Selection sort

  • Concept: The implementation of selection sort algorithm is somewhat similar to insertion sort, also divided into ordered space and unordered space. But the selection sort will find the smallest element from the unordered space every time, and put it at the end of the ordered space, that is, find the smallest element and I element swap position.
  • Time complexity O(N2)
  • Space complexity O(1)
  • Code implementation (from small to large), a two-layer for loop, the first layer through all the elements, swap positions, the second layer, find the smallest element
function selectSort(target) {
    if (!target || !target instanceof Array || target.length < 2) {
    	return target || []
    }
    for(let i=0; i<target.length; i++){
        let minIndex = i
        // 循环找出最小元素
        for(let j=i+1; j<target.length; j++){
            if(target[j] < target[minIndex]){
                minIndex = j
            }
        }
        let tem = target[i]
        target[i] = target[minIndex]
        target[minIndex] = tem
    }
    return target
}
Copy the code