1. Bubble sort

1.1 concept

Bubble Sort is a simple sorting algorithm in the field of computer science.

It repeatedly walks through the column of elements to be sorted, comparing two adjacent elements in turn, and swapping them if the order is wrong (from largest to smallest, Z to A). The task of visiting an element is repeated until no neighboring elements need to be swapped, that is, the element column has been sorted.

The algorithm gets its name from the fact that smaller elements slowly “float” to the top of the sequence (ascending or descending) through exchange, just as bubbles of carbon dioxide in a carbonated drink eventually rise to the top.

1.2 Schematic Diagram

1.3 code
const arr = [5.2.7.8.34.7.39.12.56.9.1]

  function bubbleSort(arr) {
    const len = arr.length
    // The outer loop I controls the number of rounds to compare
    for (let i = 0; i < len; i++) {
      // The inner loop controls the number of comparisons in each round j, arr[I] only compares with the rest of the elements len-i
      for (let j = 1; j < len - i; j++) {
        // If the former element is "greater" than the latter, then the two switch places
        if (arr[j - 1] > arr[j]) {
          [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]]}}}return arr
  }

  console.log(bubbleSort(arr))	// [1, 2, 5, 7, 7, 8, 9, 12, 34, 39, 56]
  
Copy the code

Improved bubble sort method:

function bubbleSort(arr) {
    let temp = null, flag = 1
    const len = arr.length
    for (let i = 0; i <= len - 1 && flag === 1; i++) {
      flag = 0
      for (let j = 0; j < len - i; j++) {
        if (arr[j] > arr[j + 1]) {
          temp = arr[j + 1]
          arr[j + 1] = arr[j]
          arr[j] = temp
          flag = 1// Data exchange occurs. Flag is set to 1}}}return arr
  }
Copy the code

2. Insert sort

2.1 concept

It is also commonly known as direct Insert Sort. It is an efficient algorithm for sorting a small number of elements. Insertion sort is one of the simplest sorting methods. Its basic idea is to insert a record into an ordered list that has been sorted, thus creating a new ordered list that increases the number of records by one. In the process of its implementation, the use of a double-layer loop, the outer loop to all elements except the first element, the inner loop to the ordered list in front of the current element to be inserted position search, and move.

Insert sort refers to that in the element to be sorted, assuming that the first n-1 number (where n>=2) has been sorted, insert the NTH number into the previously sorted sequence, and then find the appropriate position so that the sequence of inserting the NTH number is also sorted. The process of inserting all elements until the entire sequence is in order is called insertion sort.

2.2 Schematic Diagram

2.3 code
  const arr = [5.2.7.8.34.7.39.12.56.9.1]

  function insertSort(arr) {
    const handle = [arr[0]], len = arr.length
    for (let i = 1; i <= len - 1; i++) {
      const current = arr[i]
      for (var j = handle.length - 1; j >= 0; j--) {
        if (current > handle[j]) {
          handle.splice(j + 1.0, current)
          break
        }
        if (j === 0) {
          handle.unshift(current)
        }
      }
    }
    return handle
  }

  console.log(insertSort(arr))	// [1, 2, 5, 7, 7, 8, 9, 12, 34, 39, 56]
  
Copy the code

Optimized insertion sort method:

	// Arrange arr[] in ascending order, insert sort
  function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
      // Insert arr[I] into ARr [i-1], arr[i-2], arr[i-3]... Among the
      for (let j = i; j > 0; j--) {
        if (arr[j] < arr[j - 1]) {
          [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]]}}}return arr
  }
Copy the code

3. Quicksort

3.1 concept

Quick Sort is an improvement on bubbling Sort.

Quicksort was proposed by C. A. R. Hoare in 1960. Its basic idea is: by a trip to sort to sort data split into separate two parts, one part of all the data are smaller than the other part of all data, and then of the two parts data respectively according to the method of quick sort, the entire sorting process can be recursive, to achieve the whole data into an orderly sequence.

3.2 Schematic Diagram

3.3 code
  const arr = [5.2.7.8.34.7.39.12.56.9.1]

  function quickSort(arr) {
    // 4. End the recursion (if ary is less than or equal to one term, no processing)
    if (arr.length <= 1) {
      return arr
    }
    // 1. Find the middle item in the array and remove it from the original array
    const middleIndex = Math.floor(arr.length / 2)
    const middle = arr.splice(middleIndex, 1) [0]
    // 2. Prepare the left and right arrays, and loop through the remaining items in the array. The items smaller than the current item are placed in the left array, and vice versa
    const leftArr = [], rightArr = []
    for (let i = 0; i < arr.length; i++) {
      const current = arr[i]
      current < middle ? leftArr.push(current) : rightArr.push(current)

    }
    // 3. Recursively, the left and right arrays continue to do this until the left and right arrays are sorted.
    // (left + middle + right)
    return quickSort(leftArr).concat(middle, quickSort(rightArr))
  }

  console.log(bubbleSort(arr))	// [1, 2, 5, 7, 7, 8, 9, 12, 34, 39, 56]
  
Copy the code

4. Ten kinds of spatial complexity and time complexity: