The realization of the minOf2

  • Find the smaller of the two numbers
let minOf2 = (numbers) = > {
  if(numbers[0] < numbers[1]) {return numbers[0]}else{
    return numbers[1]}}Copy the code
  • Optimize the code
let minOf2 = numbers= >
  numbers[0] < numbers[1]? numbers[0] : numbers[1]
Copy the code
  • To optimize the
let minOf2 = ([a,b]) = > a < b ? a : b
Copy the code

This writing is called destructor assignment

  • call
minOf2([1.2])  //1
minOf2.call(null[1.2])  // Master call method
Copy the code
  • JS built inMath.min
Math.min(1.2)  //1

Math.min.call(null.1.2)   // Master call method

Math.min.apply(null[1.2])
Copy the code
  • aboutMath

Math looks like a constructor like Object, but actually Math is just an ordinary Object.

The realization of the minOf3

  • Find the smallest of the three numbers
let minOf3 = ([a,b,c]) = > {
    return minOf2([a, minOf2([b,c])])
}
Copy the code

The realization of the minOf4

  • Find the smallest of the four numbers
let minOf4 = ([a,b,c,d]) = > {
    return minOf2([a, minOf3([b,c])])
}
Copy the code

MinOf2 can be used to minimize arrays of any length

minThe implementation of the

let min = (numbers) = > {
  if(numbers.length > 2) {return min(
      [numbers[0], min(numbers.slice(1)))}else{
     return Math.min.apply(null,numbers)
   }
  }
Copy the code

That’s recursion

Implement sort

Sorting algorithm

Ideas:

  • Do it recursively
  • Implement with a loop

Selection sort

Sort an array of length 2

let sort2 = ([a,b]) = > {
  if(a < b){
    return [a,b]
  }else{
    return [b,a]
  }
}
Copy the code
  • Optimize the code
let sort2 = ([a,b]) = >
  a < b ? [a,b] : [b,a]
Copy the code

Sort an array of length 3

let sort3 = (numbers) = > {
  let index = minIndex(numbers)
  let min = numbers[index]
  number.splice(index,1) // Delete min from numbers
  return [min].concat(
    sort2(numbers)
  )
}
Copy the code

implementationminIndex

let minIndex = (numbers) = >
  numbers.indexOf(min(numbers))
// Bug in this code: if there are two minimum values, such as two 1's, index will only return the index of the first 1
Copy the code

This is a trick

Sort an array of any length

let sort = (numbers) = >{
  if(numbers.length > 2) {let index = minIdex(numbers)
   let min = numbers[index]
   numbers.splice(index,1)
   return [min].concat(sort(numbers))
 }else{
   return numbers[0]< numbers[1]? numbers : numbers.revese() } }Copy the code

cycle

Any recursion can be rewritten as a loop, but it’s more difficult to write

  • Rewrite the above code into a loop
let sort = (numbers) = > {
  for(let i=0; i < numbers.length-1, i++){
    let index = minIndex(numbers.slice(i))+ i
    if(index! ==i){swap(numbers, index, i)} }return numbers
 }
Copy the code
  • Debug with log
let sort = (numbers) = > {
  for(let i=0; i < numbers.length-1, i++){
    console.log(` - `)
    console.log(`i: ${i}`)
    let index = minIndex(numbers.slice(i))+ i
    console.log(`index: ${index}`)
    console.log(`min: ${numbers[index]}`)
    if(index! ==i){ swap(numbers, index, i)console.log(`swap ${index}: ${i}`)
      console.log(numbers)
    }
  }
  return numbers
 }
Copy the code

implementationswap

let swap = (arry, i, j) = > {
  let temp = arry[i]
  arry[i] = arry[j]
  arry[j] = temp
}
swap(numbers, 1.2)
Copy the code

Quick sortquick sort

let quickSort = arr= > {
   if (arr.length <= 1) {returnarr; }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[1] < pivot) {left.push(arr[i])
     } else {right.push(arr[i]) }
    }
    return quickSort(left).concat(
       [pivot], quickSort(right) )
  }
Copy the code

Merge sortmerge sort

let mergeSort = arr= >{
  let k = arr.length
  if(k===1) {return arr}
  let left = arr.slice(0.Math.floor(k/2))
  let right = arr.slice(Math.floor(k/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

Count sorting

  • Ideas:

Use a hash table for the record

If you find the number N, remember N:1. If you find it again, add 1

And then I print out all the keys in the hash table, let’s say N:m, so N needs to be printed m times

let countSort = arr= >{
  let hashTable = {}, max = 0, result = []
  for(let i=0; i<arr.length; i++){ // go through the number group
    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++){ // iterate over the hash table
    if(j in hashTable){
        result.push(j)
    }
  }
  return result
}
Copy the code
  • Bug in the code above: if j appears twice, it needs to be iterated again
let contSort = arr= >{
  let hashTable = {}, max = 0, result = []
  for(let i=0; i<arr.length; i++)}{ 
    { // go through the number group
    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++){ // iterate over the hash table
    if(j in hashTable){
      for(let i = 0; i<hashTable[j]; i++){
        result.push(j)
      }
    }
  }
  return result
}
Copy the code

Other sort

  • Bubble sort
  • Insert sort visualgo.net/zh/sorting click on Instagram
  • Hill Sort. At/choose Shell Sort
  • Radix sort visualgo.net/zh/sorting click RAD is suitable for multi-digit sort