Cause: I saw some technical blogs on the Nuggets, often, but I didn’t see many articles on algorithms, so I wanted to summarize them

1. Time complexity: Time complexity describes the running time of the algorithm. The number of operations that the algorithm needs to perform is expressed as a function of input size n, called T(n). Time complexity is usually used to represent O(n), and the formula is T(n)=O(f(n)), where F (n) represents the sum of the execution times of each line of code.

Anyone with some background in algorithms should know what algorithmic complexity is, which is basically f(n) is the maximum number of code operations, right

Common time complexity O(1) console.log

O(n) array operations

O(n2) double for loop

O(log(n)) binary search (nlog(n),2n)

2. Space complexity: Space complexity is the measure of the temporary space occupied during the operation of the algorithm O(1): the temporary space required by the algorithm does not change with the size of a variable N, that is, the space complexity of the algorithm is a constant, which can be expressed as O(1).

O(n) complexity: a for() loop

  • Sorting algorithm is an algorithm that sorts a string of data in a specific order.

One index of sorting algorithm is stability, stability is: if only according to the first number of sorting, the first number is the same and the second number is different, the second number according to the original sorting is stable sorting, not according to the original sorting is unstable sorting.

Stability Bubble sort stable selection sort unstable insert sort stable Hill sort unstable quicksort unstable merge sort stable

Let’s take a look at the Bubble Sort algorithm, which is relatively easy to implement but slow. It’s called bubble sort because with this sort algorithm, it bubbles from one end of the array to the other. Each time you compare the neighboring elements, if the first one is larger than the second, you swap the two elements and do the same thing for each pair of neighboring elements, starting with the first pair and ending with the last pair, so that the last element should be the largest;

code

function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j+1]) {
        const temp = arr[j+1];
        arr[j+1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}
Copy the code

Selection Sort is a simple and intuitive sorting algorithm. Selection sort starts at the beginning of the array, compares the first element to the other elements, checks all the elements and puts the smallest element in the first place of the array, and continues from the second element. This goes all the way to the penultimate position in the array.

function selectionSort(arr) { const len = arr.length; let minIndex; let temp; for (let i = 0; i < len - 1; i++) { minIndex = i; for (let j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; }} temp = arr[I]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr; }Copy the code

Insertion Sort is similar to sorting data by first letter or number. It works by building an ordered sequence, scanning back to front in the sorted sequence for unsorted data, finding the appropriate location and inserting it.

function insertionSort(arr) { const len = arr.length; let preIndex; let current; for (let i = 1; i < len; i++) { preIndex = i - 1; current = arr[i]; While (preIndex >= 0 && arr[preIndex] > current) {arr[preIndex + 1] = arr[preIndex]; preIndex--; } arr[preIndex + 1] = current; } return arr; }Copy the code

The Shell Sort is so called because it was invented by Donald Shell. Hill sort is a big improvement on insertion. The core idea differs from insertion sort in that it compares distant elements in preference to adjacent ones. As you start traversing the data set with this algorithm, the distance between all the elements decreases until you reach the end of the data.

function shellSort(arr) {
  const len = arr.length;
  let gap = Math.floor(len / 2);

  while (gap > 0) {
    for (let i = gap; i < len; i++) {
      const temp = arr[i];

      let j = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }
      arr[j] = temp;
    }
    gap = Math.floor(gap / 2);
  }
  return arr;
}
Copy the code

Quick Sort is usually used to process large data sets and is relatively fast. Quicksort recursively divides the data into subsequences of smaller and larger elements. The algorithm first selects an element in the list as the base value. All elements smaller than the base value are placed in front of the base value, and all elements larger than the base value are placed behind the base value. There are generally 4 ways to take this base value: No-brain take the first element no-brain take the last element no-brain take the middle element take any one of them the following solution is based on taking the last element:

function partition(arr, low, high) { let i = low - 1; // Index of smaller elements const pivot = arr[high]; for (let j = low; j < high; If (arr[j] < pivot) {i++; if (arr[j] < pivot) {i++; [arr[i], arr[j]] = [arr[j], arr[i]] } } [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]] return i + 1; } function quickSort(arr, low, high) { if (low < high) { const pi = partition(arr, low, high) quickSort(arr, low, pi - 1) quickSort(arr, pi + 1, high) } return arr; }Copy the code

Merge Sort is the merging of a series of ordered subsequences into a large, fully ordered sequence. The realization principle divides the input sequence of length N into two sub-sequences of length N / 2, and merges the two sub-sequences respectively. Finally, the two sorted sub-sequences are merged into a final sorted sequence.

Function mergeSort(arr) {const len = arr.length; if (arr.length > 1) { const mid = Math.floor(len / 2); // const L = arr.slice(0, mid); const R = arr.slice(mid, len); let i = 0; let j = 0; let k = 0; mergeSort(L); // Sort the left one mergeSort(R); While (I < L length &&j < r.length) {if (L[I] < R[j]) {arr[k] = L[I]; i++; } else { arr[k] = R[j]; j++ } k++; } while (I < L length) {arr[k] = L[I]; i++; k++; } while (j < R.length) { arr[k] = R[j]; j++; k++; } } return arr; }Copy the code