The simplest algorithm is the sorting algorithm

Find the minimum subscript minIndex

Two ways to write it: “recursion” and “loop”

Recursive writing

Use the helper function min to get the minimum value to find the subscript

let minIndex= (numbers) = > numbers.indexOf(min(numbers)) 
let min = (numbers) = > {
  if(numbers.length > 2) {return min( [numbers[0], min( numbers.slice(1)))/ / recursion
  }else{
    return numbers[0] < numbers[1]? numbers[0] : numbers[1]}}Copy the code

Cons: Cumbersome code (multiple layers of parentheses in recursion, extra helper function min referenced)

Loop writing

let minIndex = (numbers) = > {
  let index = 0 
  for(let i=1; i < numbers.length; i++){ 
    if( numbers[i] < numbers[index] ){  
      index = i 
    }
  }
  return index
}
minIndex([9.6.8.13.5.4])
Copy the code
  • Index always represents the current minimum subscript, initially assuming the current minimum subscript is 0
  • So in the body of the loop, we should start fetching the element with subscript 1, compare it to the element with subscript 0, and assign the lower subscript to index
  • All the way through, get the minimum index

Inspired 💡

Can all “recursion” be written as “loop”?

Yes, this is something that has been proven

  • All recursions can be rewritten as loops
  • If you find recursion hard to understand, you can rewrite it as a loop. Loops are generally easier to understand, but loops are more cumbersome to write and require more code

There’s a lot of detail in the loop

  • Loops are particularly easily disturbed by details that are hard to figure out, especially boundary conditions that are hard to determine (make tables and find patterns).
  • Don’t have to deal with the length of 0 and 1 array (if length = = = 0 | 1 direct return)

If the debug

  • Learn to look at the console, type log (note the mark)

​

​

Select sort

Recursive writing

Recursion must determine the abort condition

  • If the array length is greater than 2, find the smallest value and put it in front, and selectSort all the following values again
  • If the array length is 2, we simply compare the size/swap the two elements, and return the array (recursive abort).
  • Enter the bomb stack, perform multiple concat concatenation array, finally get the sequential array
let selectSort = arr= > {
  if (arr.length > 2) {
    let index = minIndex(arr)
    let min = arr[index]
    arr.splice(index, 1)
    return [min].concat(selectSort(arr))  / / recursion
  } else {
    return arr[0] < arr[1]? arr : arr.reverse()/ / stop}}let minIndex = arr= > arr.indexOf(min(arr))

let min = arr= > {
  if (arr.length > 2) {
    return min([arr[0], min(arr.slice(1)))/ / recursion
  } else {
    return arr[0] < arr[1]? arr[0] : arr[1]  / / stop
  }
}
selectSort([12.5.33.4.1])
Copy the code

Loop writing

For each round of the loop, find the smallest subscript in the unsorted array, swap places, and put the smallest first

  • Each round of the loop assumes that the first element of the current unsorted array is the minimum
    • Because I always represents the lowest subscript of an unsorted array, I always starts with 0
  • Find the minimum subscript in an unsorted array using minIndex
  • If the minimum subscript does not match the hypothesis, swap places via swap
let selectSort = (numbers) = > {
  for(let i = 0; i < numbers.length - 1; i++){   // 👈 key understanding!! (Boundary: Why -1)
    let index = minIndex(numbers.slice(i)) + i   // 👈 key understanding!! (Minimum subscript: why + I)
    if(index ! == i){ swap(numbers,index,i) } }return numbers
}

let swap = (array, i ,j) = > {
  [array[i], array[j]] = [array[j],array[i]]
}

let minIndex = (numbers) = > {
  let index = 0
  for(let i = 0; i < numbers.length; i++){
    if(numbers[i] < numbers[index]){
      index = i
    }
  }
  return index
}

selectSort([20.40.30.10])
Copy the code

​

Why? – 1

How to determine the boundary condition I <?? What should I write

Violence Analysis (Step by step)

let selectSort = (arr) = > { 
  for(let i=0; i<??? ; i++){let index = minIndex(arr) 
    swap(arr, index, i)
  }
}
Copy the code

Assume that arR has length N and a value of 4 👇

  • For the first loop I = 0, the index of the current iterated element is 0. The index of the element to be compared can only be 1\2\3

  • In the second loop I = 1, the index of the current element is 1, and the index of the element to be compared can only be 2\3

  • For the third loop I = 2, the index of the current traversal element is 2, and the index of the element to be compared can only be 3

  • For the fourth loop I = 3, the index of the current traversal element is 3, and the index of the element to be compared and its index cannot be specified

    • In minIndex(numbers. Slice (3)), numbers[3] is the only element left in numbers. Numbers [I] cannot be compared with other elements. There’s no need for minIndex, so I = 3 is meaningless

    • So I can’t be equal to 3, I have to be equal to 3 and you can compare it to an empty array, but that’s unnecessary

  • So I starts at 0 and goes up to 2

  • Conclusion: the value range of I is I < 3, that is, I < n-1

If the array length is 4, the value of I is 0\1\2.

for(let i=0; i < numbers.length - 1; i++ ){... }Copy the code

​

Why + I

If you don’t add I, then index starts at 0 every time

  • Because each round cuts off the preceding element, the subscript value changes
When I =0To ignore0A, from [20.40.30.10] to find the minimum value10/ subscript is [3], actually in [20.40.30.10] the corresponding subscript is still [3】
👉 [10.40.30.20When I =1To ignore1The subscript is0Element), from [40.30.20] to find the minimum value20/ subscript is [2Actually in [10.40.30.20] corresponding subscript should be [3】 👉 [10.20.30.40When I =2To ignore2The subscript is0/1Element), from [30.40] to find the minimum value30/ subscript is [0Actually in [10.20.30.40] corresponding subscript should be [2👉 do not exchangeCopy the code

It is concluded that regular

  • If I =0, minIndex => 3, index => 3 👉 equivalent to minIndex + I = index
  • If I =1, minIndex => 2, index => 3 👉 is equivalent to minIndex + I = index
  • If I =2, minIndex => 0 and index => 2 👉 is equivalent to minIndex + I = index
// Finally get
let index = minIndex( numbers.slice(i) )  + i
Copy the code

Double-layer for loop

Features: less code, just a function. It’s a little bit complicated

Each round finds the smallest subscript in the unsorted array, which is used to swap places, putting the smallest value first

  • Outer loop: Each round starts with the assumption that the first element of the current unsorted array is the minimum, whose subscript j is minIndex
  • Inner loop: The first element j in the current unsorted array is compared to subsequent elements to determine the current minimum subscript
  • If the current minimum subscript does not match the hypothesis, the two positions are swapped
let selectSort = arr= > {
  for (let j = 0; j < arr.length - 1; j++) {  // j represents the subscript of the element traversed in each turn; I represents the index of the next element
    let minIndex = j  // Each round assumes that the first element of the current unsorted array is the minimum, and its subscript j is the minimum subscript
    for (let i = j + 1; i < arr.length; i++) { 
      if (arr[i] < arr[minIndex]) { // Compare the current element with the next element in pairs to find the minimum subscript
        minIndex = i
      }
    }
    if(minIndex ! == j) {// If the minimum is not the current element j, swap the minimum element with the current element
      [arr[minIndex], arr[j]] = [arr[j], arr[minIndex]]
    } 
    // Each round finds the smallest value in the unsorted array and places it at the top of the unsorted array.
    // Note: the current element j in each round is the first element in the current unsorted array
  }
  return arr
}
Copy the code

​

​

Quick sort

Characteristic is “fast”

In general, the recursion is simpler, the loop is more complex (with a lot of detail), and quicksort is only about recursion

Analysis of the

Ideas:

  • Take a middle base at a time. I’m going to halve the array, if it’s greater than the base, I’m going to put it in the left array, if it’s less than the base, I’m going to put it in the right array.
  • Then perform the previous step on the left/right array again (step by step, stack by stack)
  • Abort condition: If there is only one element left in the array, we can return the array (start popup).
let quickSort = arr= > {
  if(arr.length <= 1) { return arr }   // In the most basic case, only one element is left in the array
  let pivotIndex = Math.floor(arr.length / 2)  // Get the index of the benchmark, find the middle number (select floor)
  let pivot = arr.splice(pivotIndex, 1) [0]  // Get the base number, delete the base number from the ARR, divide the ARR into left and right parts
  let left = []
  let right = []
  for(let i=0; i < arr.length; i++){   // Iterate over the array after the deleted base number
    if(arr[i] < pivot){ 
      left.push(arr[i])  // If the current traversal element is less than the base number, it is placed in the left array
    }else{
      right.push(arr[i]) // We get three parts: left array, base number, right array}}return quickSort(left).concat( [pivot], quickSort(right) )  // the core of the 👈 code is this sentence 📌📌
  // Fast sort the left array, fast sort the right array, join the two arrays and the base number
  // If there is only one element left in the array, return the array without comparing its size
}
Copy the code
  • Splice modifies the array and returns an array of deleted elements
  • Pivot /ˈpɪvət/ — the base, center, axis
  • Math.floor(3.5) → 3

Pure code

let quickSort = arr= > {
  if(arr.length <= 1) {return arr }
  let pivotIndex = Math.floor(arr.length / 2)
  let pivot = arr.splice(pivotIndex,1) [0]
  let left = []
  let right = []
  for(let i=0; i<arr.length; i++){
    if(arr[i] < pivot){ left.push(arr[i]) }
    else{ right.push(arr[i]) }
  }
  return quickSort(left).concat([pivot], quickSort(right))
}
Copy the code

​

​

Merge sort merge sort

The most difficult of the first three sorting algorithms to understand

  • Divide the array from the middle into left and right halves, sorting the left half and the right half
  • Then merge the left and right sides

The mergeSort idea

I’m mainly responsible for splitting arrays

  • If you take an out-of-order array, it splits the array into left and right parts.
  • The mergeSort recursive split of the left and right is then performed again until all elements are separated into an array by themselves, reaching the abort condition.
  • To begin the regression, merge two arrays
    • There are only two possible arrays on the left and right: ① two arrays of length 1, ② an empty array & an array of length 1

Function merge idea

The size comparison and sorting operations are all done in the merge

  • Accepts two arrays as arguments (only sorted arrays are accepted, arrays of length 1 are also sorted arrays)
  • ** Since both arrays are ordered, the first item must represent the smallest value in the array in which it is located. The smaller value obtained by comparing the two minima must be the smallest value of all elements, so pick them first
  • For the rest of the array, repeat the merge operation (recursive)
let mergeSort = arr= > {
  if (arr.length === 1) {  // An array of length 1 does not need to be sorted, so by default it is sorted.
    return arr
  }
  // arr.slice(begin,[end]) takes the subscript from begin to end and returns a new array (including begin, but not end).
  // Slice does not alter the original array. Omitting the end argument extracts all the way to the end of the array
  let left = arr.slice(0.Math.floor(arr.length / 2)) // left from 0 to halfway (end not included)
  let right = arr.slice(Math.floor(arr.length / 2)) // Right is taken from half position to end (including begin)
  return merge(mergeSort(left), mergeSort(right)) 
  // Do the split again. Disassemble an array with only 1 element and assume that all arrays are sorted. (Start popup, execute merge)
  // Merge sorted arrays (this is the core of the merge algorithm 👇 see below)
}

let merge = (a, b) = > {  / / 【 precondition: merge received a, b two arrays, must be already sorted two arrays 】!!!!!!
  if (a.length === 0) return b  // An empty array A and an already sorted array B return the sorted array B
  if (b.length === 0) return a  / / in the same way
  return a[0] > b[0]? [b[0]].concat(merge(a, b.slice(1))) : [a[0]].concat(merge(a.slice(1), b))
  // 👆 here is the difficult part of recursion, which requires the disassembly step ⚠️⚠️, see below
}
Copy the code

Slice: does not alter the original array

  • arr.slice(begin, end): Intercepts the part of the index from begin to end (begin, but not end), returning a new array
  • arr.slice(begin): Intercepts the index from begin to the last element of the array, returning a new array

Disassemble the merge

   merge([1.5.10], [2.4.9])
=> a[0] > b[0]? [b[0]].concat(merge(a, b.slice(1))) : [a[0]].concat(merge(a.slice(1), b)) -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- dismantling 👇 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -// First step: Point to the first digit of the two arrays and compare the sizes= > [1.5.10], [2.4.9] write write1 > 2If no, go to [a].0]].concat( merge( a.slice(1), b ) ) // Merge the remaining parts again= > [1, merge( [5.10], [2.4.9]] write write5 > 2If yes, run [b].0]].concat( merge( a, b.slice(1)))// Merge the rest again= > [1.2, merge([5.10], [4.9]] write write5 > 4If yes, run [b].0]].concat( merge( a, b.slice(1)))// Merge the rest again= > [1.2.4, merge([5.10], [9]] write write5 > 9If no, go to [a].0]].concat( merge( a.slice(1), b ) ) // Merge the rest again= > [1.2.4.5, merge([10], [9]] write write10 > 9If yes, run [b].0]].concat( merge( a, b.slice(1)))// Merge the rest again= > [1.2.4.5.9, merge([10], [])] ↑If the abort condition is met: an empty array, an already sorted array, then return the sorted array B directly= > [1.2.4.5.9.10]
Copy the code

brief

Pure code

let mergeSort = arr= > {
  if (arr.length === 1) {
    return arr
  }
  let left = arr.slice(0.Math.floor(arr.length / 2)) 
  let right = arr.slice(Math.floor(arr.length / 2))
  return merge(mergeSort(left), mergeSort(right))  
}
let merge = (a, b) = > {
  if (a.length === 0) return b
  if (b.length === 0) return a
  return a[0] > b[0]? [b[0]].concat(merge(a, b.slice(1))) : [a[0]].concat(merge(a.slice(1), b))
}
Copy the code

​

​

​

Counting sort counting sort

Features: Very fast

Train of thought

  • With a new oneThe data structure–Hash tableFor the record
    • Hash table: A form of key: value
    • JS objects can be a form of a hash table, but are not pure hash tables.
    • Because JS objects have hidden properties, functions, and real hash tables have no hidden properties, only data. So the JS object is not a complete hash table
  • If you find the number N, remember N: 1. If you find it again, add 1…
  • Finally, I print out all the keys in the hash table, so if N: m, then N needs to be printed m times

Analysis of the

  • Iterate through the array of numbers to get a hashTable that records the occurrence of the element key and the number of occurrences of the value.
  • At the same time, in the process of traversing the array, find the maximum value of the array (start by assuming that the first element is the maximum value Max, and then compare the elements larger than Max, and re-assign the value to Max).
  • At this point, we know hashTable and Max.
  • Given the maximum value Max, the values of all elements are in the range of 0 to Max
  • Iterate over all elements in the range 0 to Max and push the element into the array if it matches the hash key
    • If the value of the current key is not 1, there are N elements in the array, and all N elements need to be pushed into the array at this point. So push needs to loop N times
    • Get the number of values as a basis for the number of times I of the for loop to control the execution of push rounds
let countSort = arr= > {
  let hashTable = {}, max = 0, result = []
  for(let i = 0; i < arr.length; i++){  // Iterate over the array to get a hashTable and the maximum value Max
    if(arr[i] in hashTable){
      hashTable[arr[i]] += 1 
    }else{
      hashTable[arr[i]] = 1
    }
    if(arr[i] > max){ max = arr[i] }
  }
  for(let j = 0; j <= max; j++){ // Sort the elements of the array by traversing the array of Max length
    if(j in hashTable){
      for(let i = 0; i < hashTable[j]; i++){  
        // If j occurs 3 times, loop 3 times (add j).
        // I can take several values, so the loop should take three values (I = 0, 1, 2).
        result.push(j)
      }  
    }
  }
  return result
}
Copy the code

Counting sort features ✅

Different data structures

  • Extra hashTable (data structure) used

    • The data structure used in counting sort has been upgraded
    • The algorithm is upgraded directly, very quickly

  • Just iterate over the array once (iterate over the hashTable once more)

    • In the previous sorting algorithm, we went through the array multiple times
    • For example, select sort: find the first minimum value and walk through the array. Find the second minimum and iterate over the remaining elements… reciprocating

  • Why is counting sort, which can be so powerful, just going through the original array?

    A: Because of hashTable, it’s called “trading space for time.”

    • A hashTable is a space stored in memory.
    • You can save extra time by using extra space.
    • Usually, you have to choose between space and time: “Trade space for time” or “Trade time for space”

Off topic: number of letters

Case study “How to count the number of letters in a paragraph and print the result”

  • In fact, it borrows the idea of counting sort
let count = str= > {
  let result = {}
  let newStr = str.replace(/[^a-zA-Z]/g.' ')   // `HiImSam`
  console.log(newStr)
  for(let i=0; i<newStr.length; i++){
    if(newStr[i] in result){
      result[newStr[i]] += 1
    }else{
      result[newStr[i]] = 1}}return result
}
let str = `Hi, I'm Sam`
let newStr = str.match(/a-zA-Z/g)
count(str)
--------------------------------------------------
{
  H: 1
  I: 1
  S: 1
  a: 1
  i: 1
  m: 2
}
Copy the code

Supplement regular

Extract numbers.... value.replace(/[^\d]/g.' '.... value.replace(/[^\u4E00-\u9FA5]/g.' ').... value.replace(/[^a-zA-Z]/g.' ')
Copy the code

case

let str = `Hi, I'm Sam`
let newStr = str.match(/[a-zA-Z]/g)  // ["H", "i", "I", "m", "S", "a", "m"]
// match returns an array
Copy the code
let str = `Hi, I'm Sam`
let newStr = str.replace(/[^a-zA-Z]/g.' ')  // 'HiImSam' (void all non-alphabetic characters in the string)
// replace returns a string (substitution idea)
Copy the code

​

​

​

And what sort algorithm ⁉ ️

Bubble sort visualgo.net/zh/sorting click BUB (VisualGo only provides pseudo-code ideas for reference)

Insert sort visualgo.net/zh/sorting click on Instagram

Hill Sort. At/choose Shell Sort

Radix sort visualgo.net/zh/sorting click RAD


Bubble sort

visualgo.net/zh/sorting (See icon + pseudocode)

Train of thought

  • Compare them in pairs, and then the larger ones.
  • Find a maximum for each round and bubble to the end
let bubbleSort = arr= > {
  for(let i = 0; i < arr.length - 1; i++){    // I stands for rounds (pair-to-pair comparison)
    for(let j = 0; j < arr.length - i; j++){  // j represents the subscript of the element in the current round
      if(arr[j] > arr[j+1]){
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]]  // Swap elements}}}return arr
}
Copy the code

​

Insertion Sort

Reference card train of thought, very good understanding

  • Most people catch the cards, hand holding the cards are already in order.

visualgo.net/zh/sorting Click on INS (see icon + pseudocode)

  • Pick up a card and compare it with the previous one (so start with the element with subscript 1 to ensure there is a value to compare)

  • If it’s smaller than the one in front, insert it in front

Train of thought

  1. ** Starts with the first element, which can be considered sorted **
  2. Fetching the next element, ** scans ** from back to front in the sorted element sequence
  3. Place the removed elements in the proper place among the sorted elements
  4. Repeat steps 2 to 3

Just like in a queue, pick one student at a time and “insert” that student into the part of the queue that has already been formed.

code

  • By default, the first element of the opening (the preceding element) is already sorted.
  • Retrieves the next element to be sorted and compares it with the previously sorted element
  • If the following element is smaller than a previously sorted element, it is inserted at the ** corresponding to the ** of the previously sorted element
// Insert method JS version
function insertionSort(arr) {
  // The element with subscript 0 is sorted by default, so the index of the array to be sorted starts at 1
  for(let i = 1; i < arr.length; i++) {
    // I represents the index of the element in the current array to be sorted
    // j represents the subscript of the currently sorted array element (by default, elements with subscript 0 are sorted, so j must start with 0)
    // The sorted element always precedes the element to be sorted, so j must be less than I
    J = [0, I]
    for(let j = 0; j < i; j++) { 
      // Compare arr[I] with the previously sorted elements
      if(arr[i] < arr[j]) {  
        arr.splice(j, 0, arr[i])  // Insert arr[I] before arr[j], then delete the original arr[I]
        arr.splice(i+1.1) // The subscript of the following element is moved one bit after the insertion of an element in the previous step. The subscript of the element at position I is now changed to I +1
        break  // exit the inner loop, i++}}}}let arr = [10.34.21.47.3.28]
insertionSort(arr)
console.log(arr)
Copy the code

Added: Regular for loop

function insertionSort(arr) {
  for(var i = 1; i < arr.length; i++) {
    var temp = arr[i]
    for(var j = i; j > 0 && arr[j-1] > temp; j--) {
      arr[j] = arr[j-1]
    }
    arr[j] = temp
  }
}
-----------------------------------------------------
function insertionSort(arr) {
  for (var i = 1; i < arr.length; i++) {
    var temp = arr[i];
    for (var j = i - 1; j >= 0; j--) {
      if (arr[j] > temp) {
        arr[j + 1] = arr[j];
      } else {
        break;
      }
    }
    arr[j + 1] = temp;
  }
  returnarr; } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --let arr = [10.34.21.47.3.28]
insertionSort(arr)
console.log(arr)
Copy the code

Added: The normal while loop

function insertionSort(arr) {
  for (var i = 1; i < arr.length; i++) {
    var temp = arr[i];
    var j = i - 1;
    while (j >= 0 && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
  return arr;
}
let arr = [10.34.21.47.3.28]
insertionSort(arr)
console.log(arr)
Copy the code

​

Hill Sort Shell Sort

  • Extremely rare
  • The algorithm is more complex. There are no examples in real life, no examples in mathematics
  • It was invented in 1959 by a guy named Shell

​

Radix Sort

Especially suitable for ** multi-digit sorting **

  • Refers to the elements in an unsorted array that have one, two, three, four, or five digits. (Array of various forms)
  • Rote memorization, order is very important, remember the wrong is over (but can understand the spirit of the algorithm 👇)

  • The ones place is stacked from bottom to top, the ones place is stacked from bottom to top…
    • Then expand all the elements into an array in the very important order of bits 0-9 from the bottom up
  • For this new array, sort by ten digits, stacked from bottom to top from 0 to 9.
    • Then expand the array in 0-9 order from bottom to top
  • …
  • Repeat for all digits
  • The last array to expand is the sorted array

​

Heap Sort

  • Heap sort should be the end of sorting, because there’s nothing more complicated than heap sort
  • All other complex sorts are basically improvements on heap sorts
  • Once you’ve done heap sorting, you’ve done the tree (data structure), and you’ve done the hard part of sorting