bubbleSort

• Compare all adjacent elements and swap their positions if the first is larger than the second
• After one round, I guarantee that the last number is the largest
• Do n-1 rounds to complete the sorting

Array.prototype.bubbleSort = function () {
  for (let i = 0; i < this.length - 1; i++) {
    // The last bit of the array is the largest after the first loop, and the next loop is up to the first I bit of the last bit, all -i, so that each bubble sort subtracts the sorted interval
    for (let j = 0; j < this.length - 1 - i; j++) {
      // Compare the first and second places. If the first place is larger than the second place, swap places
      if (this[j] > this[j + 1]) {
        const temp = this[j];
        this[j] = this[j + 1];
        this[j + 1] = temp; }}}return this;
};
const arr = [5.4.3.2.1];
console.log(arr.bubbleSort());
Copy the code

function bubbleSort(arr) {
  let length = arr.length;
  for (let i = 0; i < length - 1; i++) {
    // The last bit of the array is the largest after the first loop, and the next loop is up to the first I bit of the last bit, all -i, so that each bubble sort subtracts the sorted interval
    for (let j = 0; j < length - 1 - i; j++) {
      // Compare the first and second places. If the first place is larger than the second place, swap places
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp; }}}return arr;
}
const arr = [5.5.7.2.8.1.0.4.5.1];
console.log(bubbleSort(arr));
Copy the code

Time complexity: O(n^2) Space complexity: O(1) Stability: Bubble sort is a stable sorting algorithm because it can achieve constant relative positions of elements with equal values

Ii. Selection Sorting (selecttionSore)

• Find the smallest value in the array, select it and place it first.
• Then find the second smallest value, select it and place it second.
• And so on, perform the N-1 round

Array.prototype.selecttionSore = function() {
  // Complete the sorting after performing the n-1 round
  for (let i = 0; i < this.length - 1; i++) {
    // Declare a minimum subscript, default is 0, the first round is the first element, the second round is the second element
    let indexMin = i;
    // Do a loop, if the current element is less than the minimum, then the minimum subscript is replaced by the current element subscript
    // For each loop, the first I elements are sorted, so the sorting interval starts at I
    for (let j = i; j < this.length; j++) {
      if (this[j] < this[indexMin]) { indexMin = j; }}// Go through the loop to find the minimum index
    // Swap the minimum with the first element of the array
    const temp = this[i]; // The first value of the array
    this[i] = this[indexMin]; // Set the first value of the array to the minimum value
    this[indexMin] = temp; // Set the minimum subscript element to the first value of the array
  }
  return this;
};

const arr = [6.5.4.3.2.1];
console.log(arr.selecttionSore());
Copy the code

const arr = [6.5.4.3.2.1];
function selectionSort(arr) {
  let length = arr.length;
  for (let i = 0; i < length - 1; i++) {
    let indexMIn = i;
    for (let j = i; j < length; j++) {
      if(arr[j] < arr[indexMIn]) { indexMIn = j; }}const temp = arr[i];
    arr[i] = arr[indexMIn];
    arr[indexMIn] = temp;
  }
  return arr;
}

console.log(selectionSort(arr));
Copy the code

Stability: Selection sort is an unstable sorting algorithm because there is no guarantee that the relative positions of elements with equal values remain the same. For example, the array [3, 4, 3, 1, 5] is swapped for the first time, and the relative positions of the original two 3’s change.

Insert sort

• Think of the left side of the array as an ordered sequence, and insert one digit at a time into that ordered sequence;
• Start with the second book and move forward, and if there is anything larger, move back, and compare the second number with the third, and compare the third number with the previous one;
• The comparison starts at the far right of the sorted array. If it is larger than the number being compared, the number being compared moves back one bit and the number being compared is inserted
• And so on down to the last number

Array.prototype.insertionSort = function() {
  // Start the loop from the second, so I =1
  for (let i = 1; i < this.length; i++) {
    let temp = this[i]; // Find the first unsorted number on the right. The first loop defaults to the second number
    let j = i; // The number that has been sorted on the left
    while (j > 0) {
      // Compare the numbers to be inserted with the sorted array on the left
      // If the number to be inserted is smaller than the number to be compared, move the compared number back one bit
      Exit if the number to be inserted is larger than the number being compared
      if (temp < this[j - 1]) {
        this[j] = this[j - 1]; // Move the first number back one bit
      } else {
        break;
      }
      j--;
    }
    // At the end of the loop, the value of j is the position to insert temp
    this[j] = temp;
  }

  return this;
};

const arr = [6.5.4.3.2.1];
console.log(arr.insertionSort());
Copy the code

const arr = [1.8.5.2.13.7.42.64.2];
function insertionSort(arr) {
  // Start from the second part of the array and compare to the left, so I =1
  for (let i = 1; i < arr.length; i++) {
    let target = i; // This is the first unsorted number on the right. The first loop defaults to the second number
    for (let j = i - 1; j >= 0; j--) {
      // Compare target to the sorted number on the left or, if smaller, switch places with the number being compared
      if (arr[target] < arr[j]) {
        [arr[target], arr[j]] = [arr[j], arr[target]];
        // After the exchange, target inserts one bit forward
        target = j;
      } else {
        // If there is no previous number smaller than target, exit the loop
        break; }}}return arr;
}

console.log(insertionSort(arr));
Copy the code

The first idea is more consistent with the concept of insertion time complexity :O(n^2) space complexity :O(1) Stability: insertion sort stable sorting algorithm, swap only meets the condition arr[target] < arr[j], this condition can ensure that the relative position of the elements with equal value is unchanged.

mergeSort

Using the idea of merging to achieve the sorting method. This algorithm is a very typical application of Divide and Conquer. (Divide-and-conquer breaks the problem into smaller problems and solves them recursively, while the conquer stage “tinks” together the answers from the divide stage, i.e. divide and conquer.)

• Divide: Divide an array into left and right arrays, and recursively divide subarrays until the length of the array is less than2, into individual numbers
• Combine: Combine two numbers into an ordered array, and then combine the ordered arrays until all subarrays are combined into a complete array. If necessary, the left and right arrays are already ordered.

Add the smaller element to the temporary array. If both arrays still have values, repeat the operation. If either array is empty, the other array must be greater than all the elements in the RES

Merge sort process

The process of merging two ordered arrays

Array.prototype.mergeSort = function () {
  // The first step is to divide the array into arrays of length less than 2, which means the array is sorted
  const rec = (arr) = > {
    if (arr.length < 2) {
      return arr;
    }
    const mid = Math.floor(arr.length / 2); // Get the middle index of the array and divide the array into left and right arrays
    const left = arr.slice(0, mid); // Left array
    const right = arr.slice(mid, arr.length); // The right array
    // The call recursively splits the left and right arrays until the array length is less than 2
    const orderLeft = rec(left); // An ordered left array with a length of 1 returned
    const orderRight = rec(right); // The ordered right array
    const res = [];
    // When the left or right arrays have values
    while (orderLeft.length || orderRight.length) {
      // When both the left and right arrays have values, compare the first number in the left and right arrays and push the smaller number into the res
      if (orderLeft.length && orderRight.length) {
        res.push(
          orderLeft[0] < orderRight[0]? orderLeft.shift() : orderRight.shift() ); }// If the right array is empty and the left array is not empty, push all the left values into res
      else if (orderLeft.length) {
        res.push(orderLeft.shift()); // Remove and return the first element of the array
      } else if(orderRight.length) { res.push(orderRight.shift()); }}// Returns the merged ordered array as the result of recursion
    return res;
  };
  const res = rec(this);
  // console.log(res);
  res.forEach((n, i) = > {
    this[i] = n;
  });
  return this;
};
const arr = [5.8.4.3.2.1];
console.log(arr.mergeSort());
Copy the code

Function calls are implemented through the data structure stack, which adds a layer of stack frames each time a function call is entered, and subtracts a layer of stack frames each time the function returns. So when you recursively call itself it’s on the stack, and when you return it’s off the stack so the idea of merge sort is to keep breaking itself up, adding elements to the top of the stack, until the array is less than 2, and you start merging the top of the stack and you return the merged array

Another recursive call

const arr = [9.8.7.6.5.4.3.2.1.0];

function mergeSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const midIndex = Math.floor(arr.length / 2);
  const left = arr.slice(0, midIndex);
  const right = arr.slice(midIndex, arr.length);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let temp = [];
  while (left.length && right.length) {
    temp.push(left[0] < right[0]? left.shift() : right.shift()); }while (left.length) {
    temp.push(left.shift());
  }
  while (right.length) {
    temp.push(right.shift());
  }
  return temp;
}
console.log(mergeSort(arr));
Copy the code

Time complexity :O(nlogn), recursively split into two logn, loop n times, so Nlogn space complexity :O(n) Stability: merge sort is a stable sorting algorithm

5. QuickSort

Quicksort is also divide-and-conquer

• Partition: Select a “base” from the array (usually the first number), all the elements smaller than the base in front of the base, the elements larger than the base behind the base, at this point the base element has found the appropriate position, the number in front of the base is smaller than it, the number behind it is larger than it
• Recursion: recursively partition the subarray before and after the base, so that you can find a “base” in the subarray and put it in the appropriate position, recurse to the length of the array is less than 2, end the recursion, and so on all the subarrays sorted, sorted

Array.prototype.quickSort = function () {
  // a recursive function
  const rec = (arr) = > {
    If the element length is less than 2, there is no need to sort
    if (arr.length < 2) {
      return arr;
    }
    const left = []; // An array smaller than the base
    const right = []; // An array larger than the baseline
    const mid = arr[0]; // The first digit of the array is the baseline
    // Start the loop at the second position of the array to compare with the baseline
    for (let i = 1; i < arr.length; i++) {
      // If it is smaller than the baseline, insert left, otherwise insert y
      if (arr[i] < mid) {
        left.push(arr[i]);
      } else{ right.push(arr[i]); }}// Return the left array + the base element + the right array
    return [...rec(left), mid, ...rec(right)];
  };
  const res = rec(this);
  res.forEach((n, i) = > {
    this[i] = n;
  });
  return this;
};
const arr = [9.4.9.21.56.1.74.8.98.2.97.0];
console.log(arr.quickSort());
Copy the code

    function quickSort(array) {
      if (array.length < 2) {
        return array;
      }
      const mid = array[0];
      const left = [];
      const right = [];
      for (let i = 1; i < array.length; i++) {
        if (array[i] < mid ) {
          left.push(array[i]);
        } else{ right.push(array[i]); }}return [...quickSort(left), mid, ...quickSort(right)];
    }
Copy the code

Time complexity: average O(nlogn), worst O(n2), actually less than O(nlogn) in most cases Spatial complexity :O(logn) (recursive call consumption) Stability: unstable, unable to guarantee that the relative positions of equal elements remain the same

Binary search

Is an algorithm that finds elements in an ordered array

• Start with the middle element of the array. If the middle element is the target value, the search ends and the subvalue of the middle element is returned
• If the target value is greater than or less than the middle element, the half of the array that is greater than or less than the middle element is searched
• Recursively repeat the first step until the element is found, otherwise -1 is returned

Array.prototype.binarySearch = function (item) {
  let low = 0; // The smallest index of the array
  let high = this.length - 1; // The maximum index of the array
  // If the minimum subscript is less than the maximum subscript
  while (low < high) {
    const mid = Math.floor((low + high) / 2);
    const element = this[mid]; // The intermediate element
    if (element < item) {
      // In the larger half of the target element, the smallest lower part is mid+1
      low = mid + 1;
    } else if (element > item) {
      // The target element is in the smaller half, with the maximum lower part being mid-1
      high = mid - 1;
    } else {
      returnmid; }}return -1;
};

const arr = [1.2.3.4.5.6];
console.log(arr.binarySearch(5));

Copy the code