preface

Algorithm for the front-end programmers may not have the back-end application programmers, but we also have to master some basic algorithm thought, that whether it is for us to find a job or work at ordinary times has a great help, now more and more companies will review the algorithm ability of front-end programmers, so it is necessary for us to learn the front-end common basic idea of the algorithm.

If this article helps you, ❤️ follow + like ❤️ to encourage the author, the article public account first, followThe front nine southGet the latest articles for the first time

Github welcome to Star

Bubble sort

Algorithm description

Bubble sort believe for many students is not strange, it should be our most classic algorithm, no matter what language, can see it. The basic idea: iterate through the array to be sorted, comparing the size of two elements at a time, and swapping the order of the two elements if the order is wrong. The comparison is repeated through the array until the sorting is complete.

Algorithm implementation

Basic steps

  • Compare two adjacent elements. If the first is larger than the second, switch places;
  • Repeat the first step for each pair of adjacent elements, starting with the first pair and ending with the last pair, so that the last element should be the largest;
  • Repeat for all elements except the last one;
  • Repeat steps 1 to 3 until the sorting is complete.

The demo

Code implementation

/** * The outer loop controls which elements need to be compared. For example, after the first sorting, the last element does not need to be compared. The inner loop compares two elements and puts them in the correct position
function bubbleSort(arr) {
    const len = arr.length
    for(let i=0; i<len; i++) {
        for(let j=0; j<len-1-i; j++) {
          // Note the boundary values
            if(arr[j] > arr[j+1]){
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]] // Switch places}}}return arr
}

console.log(bubbleSort([3.44.15.36.26.27.2.46.4.19.50.48]))
/ /,3,4,15,19,26,27,36,44,46,48,50 [2]
Copy the code

Time complexity: O(n^2)

Quick sort

Algorithm description

Quicksort, an improved algorithm for bubbling sort, is one of the fastest sorting algorithms for big data. ** Basic idea: ** It is a divide-and-conquer algorithm to find a reference value and recursively decompose the data into different subsequences containing smaller elements and larger elements. The algorithm repeats this process until all the data is in order.

Algorithm implementation

Basic steps

  • Select a reference element and split the list into two subsequences;

  • Reorder the list so that all elements less than the base value are placed in front of the base value and all elements greater than the base value are placed behind the base value;

  • Repeat steps 1 and 2 for subsequences of smaller and larger elements, respectively

The demo

Code implementation


function quickSort(arr) {
    if(arr.length<=1) return arr
    const left = [],right = [],current = arr.splice(0.1)
    for(let i=0; i<arr.length; i++) {
        if(arr[i]<current) {
            // Less than the reference value to the left
            left.push(arr[i]) 
        }else{
            // If not, put it to the right
            right.push(arr[i])
        }
    }
    // Recurse the above steps
    return quickSort(left).concat(current,quickSort(right))
}

console.log(quickSort([3.44.15.36.26.27.2.46.4.19.50.48]))
//[2, 3, 4, 15, 19, 26, 27, 36, 44, 46, 48, 50]
Copy the code

Time complexity: O(nlogn)

Insertion sort

Algorithm description

Insertion sort is a simple and intuitive sorting algorithm. ** Basic idea: ** By building an ordered sequence, for unsorted data, scan from back to front in the sorted sequence, find the corresponding position and insert. In the implementation of insertion sort, in-place sort is usually adopted (that is, the sort only needs to use O(1) extra space). Therefore, in the process of scanning from back to front, the sorted elements need to be moved backward step by step repeatedly to provide insertion space for the latest elements.

Algorithm implementation

Basic steps

  • Starting with the first element, the element can be considered sorted;

  • Fetch the next element and scan back to front in the sorted element sequence;

  • If the element (sorted) is larger than the new element, move the element to the next position;

  • Repeat step 3 until you find a place where the sorted element is less than or equal to the new element;

  • After inserting a new element into that position;

  • Repeat steps 2 to 5.

The demo

Code implementation


/** Double loop, the outer loop controls the unsorted elements, the inner loop controls the sorted elements, sets the unsorted elements as a benchmark, and compares them with the sorted elements. If the value is less than, the position is changed, and if the value is greater than, the position is not moved */
function insertSort(arr) {
    let tem
    for(let i=0; i<arr.length; i++) {
        tem = arr[i]
        for(let j=i; j>=0; j--){
            if(arr[j-1] > tem){
                arr[j] = arr[j-1]}else {
                arr[j] = tem
                break}}}return arr
}
console.log(insertSort([3.44.15.36.26.27.2.46.4.19.50.48]))
//[2, 3, 4, 15, 19, 26, 27, 36, 44, 46, 48, 50]
Copy the code

Time complexity O(n^2)

Selection sort

Algorithm description

Select sort is a simple and intuitive sorting algorithm, ** basic idea: ** First select the minimum or maximum in the sequence to be sorted, stored in the beginning of the sorted sequence, and then continue to look for the minimum or maximum elements from the remaining unsorted elements, put in the end of the sorted sequence. And so on until all the elements are sorted.

Algorithm implementation

Basic steps

  • Initial state: the disordered region is R[1..n], and the ordered region is empty.

  • Th order (I =1,2,3… N-1), the current ordered region and disordered region are R[1..i-1] and R(I.. N). This sorting selects the record R[k] with the smallest keyword from the current unordered region and exchanges it with the first record R in the unordered region, so that R[1.. I] and R[I +1..n) become the new ordered region with 1 more records and the new unordered region with 1 less records, respectively.

  • N minus one is done, and the array is sorted.

The demo

Code implementation

/** * assume that the first element is the smallest, then loop to find the smallest element, * then swap with the first element, then assume the second element, and repeat the same process */

function selectSort(arr) {
    let len = arr.length, minIndex, tem
    for(let i=0; i<len-1; i++) {
        minIndex = i // Minimum subscript
        for(let j=i+1; j<len; j++) {
            if(arr[j] < arr[minIndex]){
                // Find the minimum value
                minIndex = j // Replace the minimum subscript}}// Switch places
        tem = arr[i]
        arr[i] = arr[minIndex]
        arr[minIndex] = tem
    }
    return arr
}

console.log(selectSort([3.44.15.36.26.27.2.46.4.19.50.48]))
//[2, 3, 4, 15, 19, 26, 27, 36, 44, 46, 48, 50]
Copy the code

Time complexity O(n^2)

Merge sort

Algorithm description

Merge sort is a method of sorting by means of “merge”, which means the process of merging two or more ordered sequences into one ordered sequence. ** Basic idea: ** merges several ordered sequences step by step, and finally merges them into one ordered sequence. Like selection sort, merge sort performs independently of the input data, but performs much better than selection sort because it is always O(n log n) time. The trade-off is extra memory.

Algorithm implementation

Basic steps

  • The input sequence of length N is divided into two subsequences of length N /2.
  • Merge sort is used for these two subsequences respectively.
  • Combine two sorted subsequences into a final sorted sequence.

The demo

Code implementation

// Divide the array and merge it
function merge(left, right) {
    let tem = []
    while(left.length && right.length) {
        if(left[0] < right[0]) {
            tem.push(left.shift())
        }else{
            tem.push(right.shift())
        }
    }
    return tem.concat(left,right)
}
function mergeSort(arr) {
    const len = arr.length
    if(len<2) return arr
    let mid = Math.floor(len / 2), left = arr.slice(0,mid), right = arr.slice(mid)
    return merge(mergeSort(left),mergeSort(right))
}
console.log(mergeSort([3.44.15.36.26.27.2.46.4.19.50.48]))
// [2, 3, 4, 15, 19, 26, 27, 36, 44, 46, 48, 50]
Copy the code

Time complexity O(nlogn)

Hill sorting

Algorithm description

Hill sort is a type of insertion sort. Also known as reduced incremental sort, it is a more efficient and improved version of the direct insert sort algorithm. Hill sort is an unstable sort algorithm. ** Basic idea: ** is to group the records by a certain increment of the index, and sort each group using the direct insertion sort algorithm; As the increments decrease, each group contains more and more keywords, and when the increments decrease to 1, the entire file is exactly grouped and the algorithm terminates.

Algorithm implementation

Basic steps

  • Select a delta sequence T1, T2… , where Ti >tj, tk=1;
  • Sort the sequence k times according to the number of incremental sequences k;
  • In each sort, the sequence to be sorted is divided into several sub-sequences of length M according to the corresponding increment TI, and each sub-table is sorted by direct insertion. Only when the increment factor is 1, the whole sequence is treated as a table, and the length of the table is the length of the whole sequence.

The demo

Code implementation


function shellSort(arr) {
    var len = arr.length;
    for(var gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
        for(vari = gap; i < len; i++) {var j = i;
            var current = arr[i];
            while (j - gap >= 0&& current < arr[j - gap]) { arr[j] = arr[j - gap]; j = j - gap; } arr[j] = current; }}return arr;
}

console.log(shellSort([50.70.60.80.61.84.83.88.87.99]))
//[50, 60, 61, 70, 80, 83, 84, 87, 88, 99]
Copy the code

Time complexity: O(nlogn)

Count sorting

Algorithm description

Counting sort is a stable sorting algorithm. ** Basic idea: ** uses an extra array C, where the ith element is the number of elements in array A whose value is equal to I. We then arrange the elements in A into the correct position according to array C. It can only sort integers.

Algorithm implementation

Basic steps

  • Find the largest and smallest elements in the array to be sorted;
  • Count the number of occurrences of each element of value I in the array and store it in the i-th entry of array C;
  • Add up all the counts (starting with the first element in C, adding each term to the previous one);
  • Reverse populating the target array: place each element I in the C(I) item of the new array, subtracting C(I) by 1 for each element.

The demo

Code implementation

function countingSort(arr) {
    let len = arr.length, b = [], c = [], min = max = arr[0]
    for(let i=0; i<len; i++) {
        min = min <= arr[i] ? min : arr[i]
        max = max >= arr[i] ? max : arr[i]
        c[arr[i]] = c[arr[i]] ? c[arr[i]] + 1 : 1 / / count
    }

    for(let i=min; i< max; i++) {
        c[i+1] = (c[i+1] | |0) + (c[i] || 0)}for(let i=len-1; i>=0; i--) {
        b[c[arr[i]] - 1] = arr[i]
        c[arr[i]]--
    }
    return b
}
console.log(countingSort([2.3.8.7.1.2.2.2.7.3.9.8.2.1.4]))
//[1, 1, 2, 2, 2, 2, 2, 3, 3, 4, 7, 7, 8, 8, 9]
Copy the code

Time complexity: O(n+k), k indicates that the input elements are n integers between 0 and k

Radix sort

Algorithm description

Radix sort is also non-comparison sort algorithm, ** basic idea: ** according to the low first sort, then collect; And then sort it in order, and then collect it; And so on, all the way to the highest place. Sometimes some attributes are prioritized, first by low priority, then by high priority. The final order is that the higher-priority ones come first, and the lower-priority ones come first. Radix sort is based on sorting separately, collecting separately, so it’s stable.

Algorithm implementation

Basic steps

  • Get the largest number in the array and get the number of digits;
  • Arr is the original array, and each bit is taken from the lowest level to form the RADIX array.
  • The radix is sorted by counting (taking advantage of the fact that counting sorting is suitable for small range numbers);

The demo

Code implementation

function radixSort(arr, maxDigit) {
    let counter = [], mod = 10, dev = 1;
    for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(let j = 0; j < arr.length; j++) {
            let bucket = parseInt((arr[j] % mod) / dev)
            if(counter[bucket]==null) {
                counter[bucket] = []
            }
            counter[bucket].push(arr[j])
        }
        let pos = 0
        for(let j = 0; j < counter.length; j++) {
            let value = null
            if(counter[j]! =null) {
                while((value = counter[j].shift()) ! =null) {
                      arr[pos++] = value
                }
          }
        }
    }
    return arr;
}
console.log(radixSort([3.44.15.36.26.27.2.46.4.19.50.48].2))
// [2, 3, 4, 15, 19, 26, 27, 36, 44, 46, 48, 50]
Copy the code

Time complexity: O(n*k), k indicates that the input elements are n integers between 0 and k

conclusion

Sorting algorithm Average time complexity Worst time complexity Spatial complexity Is stable
Bubble sort O(n^2) O(n^2) O(1) is
Quick sort O(nlogn) O(n^2) O(long) not
Insertion sort O(n^2) O(n^2) O(1) is
Selection sort O(n^2) O(n^2) O(1) not
Merge sort O(nlogn) O(nlogn) O(n) is
Hill sorting O(nlogn) O (n ^ 1.5) O(1) not
Count sorting O(n+k) O(n+k) O(n+k) is
Radix sort O(n*k) O(n*k) O(k) is

Recommended reading

  • Common front-end security problems and preventive measures
  • Why are big factories using GIF as a burying point?
  • Don’t just know about KFC, you should know about BFC, IFC, GFC and FFC
  • What is the difference between Promise, Generator, and Async?
  • In 2022, don’t you know the difference between an arrow function and a normal function?
  • From how to use to how to implement a Promise
  • Explains the page loading process in great detail

The original address point here, welcome everyone to pay attention to the public number “front-end South Jiu”, if you want to enter the front-end exchange group to learn together, please click here

I’m Nan Jiu, and we’ll see you next time!!