Bubble sorting

Bubble sorting is a process of comparison
There are two layers of loops. The outer layer actually controls the number of times. Each cycle will have a maximum value exchanged to the tail
Then you don't need to bring it on the next cycle
Each inner layer cycle will be compared from the beginning to the end
Only the latter of the exchanged elements will be re compared with the next one at a time
For example, if i and i+1 are exchanged, i+1 and i+2 will be compared next time, and i will be placed in the next round of comparison regardless of the size of the exchange and subsequent exchange
This round of comparison will only determine a maximum value and move it backward all the time, regardless of the order other than the maximum value, which will be placed in the next comparison
Stable sorting, if a = b, the former will still be the first, and the algorithm is stable
In the best case, O(n) is in positive order. It will only be compared and will not be sorted
Worst case, O(n) ²), That is, in reverse order, all have to be compared and exchanged
The average, that is, the actual bubble sorting is O(n ²)

code

function bubbsort(nums) {
      for(let i = 0; i < nums.length; i++){
        for(let j = 0; j < nums.length - i; j++) {
          let temp = arr[j]
          if(arr[j] > arr[j + 1]) {
            arr[j] = arr[j + 1]
            arr[j + 1] = temp
          }
        }
      }
    }

Select sort

Selective sorting is also a method relative to violence and direct sorting
Starting from the first, traverse the array to find a minimum value, remember the index, and then exchange the first and minimum positions
Then, start traversing the array from the second bit, find the minimum value, remember the index, and then exchange the second bit and the minimum position
...
Each cycle determines a minimum value, which is placed in front until the end of the traversal
Because it is inserted into the front after direct selection, it is an unstable algorithm
The best and worst average is O(n ²)

code:

function selectSort(nums) {
       for (let i = 0; i < nums.length; i++) {
         let min = nums[i]
         let index = i
         for (let j = i + 1; j < nums.length; j++) {
          if (nums[j] < min) {
            min = nums[j] 
            index = j
          }
         }
         let temp = nums[index]
         nums[index] = nums[i]
         nums[i] = temp
       }
     }

Insert sort

The insertion sort is different from the violent insertion like the selection sort
Instead, it is inserted into the appropriate position in the ordered sequence
What is an ordered sequence, that is, a sequence constructed in the process of circulation
By default, the first one is an ordered sequence, and the subsequent elements will be compared with the previous ones. If it is smaller than the compared elements, the previous elements need to be moved back
Move back until you reach a rear that is not less than the element, and insert the element
At this time, the following elements are still orderly because they are constantly moving backward
A stable sorting algorithm, thanks to the process of comparison, will only move elements larger than itself to its back
Best case O(n)
Worst case O(n) ²)

function insertSort(nums) {
      for (let i = 1; i < nums.length; i++) {
        let temp = nums[i]
        let j = i - 1
        while (j >= 0 && nums[j] > temp) {
          nums[j + 1] = nums[j]
          j --
        }
        nums[j + 1] = temp
      }
    }

Shell Sort

Hill sort is an optimization of insertion sort
Because insertion sorting needs to move a large number of elements every time, Hill sorting is to group the array and insert sorting within the group
Gradually decrease the step size. Finally, when the step size is 1, that is, each element is a group, but the elements are basically in order
Insert sorting within a group does not need to move a large number of elements every time, which is where optimization is
Unstable sorting will result in instability due to the step size of the group
Best case O(nlog2 n)
Worst case O(nlog2 n)
Average O(nlog n)

code:

    function shellSort(nums) {
      // Each large cycle is divided by different steps until the step is 0
      let step = Math.floor(nums.length / 2)
      for (step; step > 0; step = Math.floor(step / 2)) {
        for(let j = step; j < nums.length; j++){ // j is equivalent to starting from the second element of each group, looking back and comparing with the elements of the previous group
          let temp = nums[j]
          let k = j - step  // Compare with the elements of the previous group, and insert sorting within the group
          while(k >=0 && nums[k] > temp){
            nums[k + step] = nums[k]
            k -= step
          }
          nums[k + step] = temp
        }
      }
    }

Merge sort

Merge sort adopts the idea of divide and conquer, that is, an array is divided into many small arrays, and then the small arrays are divided, and then merged orderly
The final result is an ordered array
Let's take the two-way divide and conquer as an example, that is, it is divided into two ways to merge
Using recursive method, large array to small array to solve
Small arrays ask small groups for solutions
The bottom layer is an array with two lengths of 1. At this time, merge and call the merge method
The merging method will put a result array, and put the two arrays according to their size
Finally, the two minimum arrays are merged into an ordered array and returned upward. The upper stack continues to call the merge method to merge the two ordered arrays into a large ordered array
Finally, to the top stack, the two paths are combined to return an ordered array
See notes below for details
Stable sorting, because it is always the comparison between two adjacent channels
Sacrificing space for time, sacrificing recursive space, and changing the time complexity from n * n to n * log n

code:

    function mergeSort(nums) {
      let len = nums.length
      if (len < 2) {// When the partition is the smallest, the recursion ends and returns upward
        return nums
      }
      let mid = Math.floor(len / 2)
      // merge receives two parameters, one of the two arrays, then merges them in order, and returns the ordered array up to the upper stack call
      return merge(mergeSort(nums.slice(0, mid)), mergeSort(nums.slice(mid, len)))
    }
    function merge(arr1, arr2) {
      let res = []
      let i = 0, j = 0
      while (i < arr1.length && j < arr2.length) {
        // Add the two arrays to the result array in an orderly manner. Whoever is young will be added, and the pointer will move back. Any one of them may end up traversing first
        if (arr1[i] < arr2[j]) {
          res.push(arr1[i])
          i++
        } else {
          res.push(arr2[j])
          j++
        }
      }
      // Two while arrays are executed only once, because one of the first two arrays must end, and both arrays are ordered arrays
      // At this time, you only need to add the unfinished to the result array
      while(i < arr1.length) {
        res.push(arr1[i])
        i++
      }
      while(j < arr2.length){
        res.push(arr2[j])
        j++
      }
      return res
    }

Quick sort

Quick sort still adopts the idea of divide and conquer
Select a reference value (according to the stored data structure, take the first of the array as an example). The one smaller than the reference value is arranged on the left, otherwise on the right, and the reference value is in the middle
At the same time, the above methods are called recursively on the left and right sides
The exit of recursion is when there is no value on the left and right sides, that is, when there is only one value
In this way, a value returned from the lowest stack is combined with the middle value upward to form a left, middle and right ordered array structure
Continue to return the left, middle and right ordered array structure upward
The top stack is an ordered array
Unstable sorting because of movement compared with the benchmark value
Sacrificing recursive space for time, the time complexity is n * log n

code:

function quickSort(arr) {
        if (arr.length < 2) return arr
        let base = arr[0]
        let left = arr.filter((val, index) => {
          return val <= base && index !== 0
        })
        let right = arr.filter((val, index) => {
          return val > base && index !== 0
        })
        return [...quickSort(left), base, ...quickSort(right)]
      }

Heap sort

Heap sorting, taking the large top heap as an example (positive array, the largest after sorting is the last)
An array is used to simulate a heap. The array subscript * 2 + 1 is the left node and + 2 is the right node
The parent node of the large top heap is greater than two child nodes
Maintain the heap, that is, the method required to create the heap. See the following notes
In the sorting function, the father of the last leaf node starts to call the method of maintaining the heap to create a heap
Then start from the last node and exchange with the top node (the maximum value) every time. The maximum value is placed at the end. At this time, the length is - 1
Call the method of maintaining the heap and pass in a length to maintain the heap except for the ordered heap
Loop through the top and maintain the heap until there is only one element left
Unstable algorithm, time complexity n * log n

code:

      function adjust(arr, len, index) {
        // Note that this len length is required, because when maintaining a heap, it is not necessary to maintain all. There will be ordered ones in subsequent sorting, so the length needs to be changed
        /*
          Functions that maintain the heap are compared downward recursively, regardless of the upper layer. The upper layer will be compared downward during its own call
          You need a variable to save the maximum index. If it is still itself, it will be returned
          If it is not itself, the target and index positions are exchanged
          At this time, the index position is the original target. Use the index to continue the recursive downward comparison, because the target may be smaller than the following
        */
        let end = -1
        if (index * 2 + 1 >= len) return
        // Find the index of the largest one
        if (arr[index * 2 + 1] > arr[index * 2 + 2]) end = index * 2 + 1
        else end = index * 2 + 2
        if (arr[index] > arr[end]) return
        let temp = arr[index]
        arr[index] = arr[end]
        arr[end]  = temp
        adjust(arr, len, end)
      }
      function heapSort(arr) {
        /*
          Build the heap first, starting from the parent node of the last leaf node, not layer by layer, because the above function of maintaining the heap is to directly compare yourself with your left and right children
        */
        for(let i = Math.floor(arr.length/2) - 1; i >= 0; i--) {
          adjust(arr, arr.length, i)
        }
        /*
          After the heap is built, the top element of the heap is a maximum value, which is exchanged with the tail as a member of the order
          At this time, the tail is the first. Maintain the heap, but the length needs to be reduced by 1 because one has been arranged
        */
        for(let i = arr.length - 1; i > 0; i--) {
          let temp = arr[0]
          arr[0] = arr[i]
          arr[i] = temp
          adjust(arr, i - 1, 0)
        }
      }