First, selection sort

Select the sorting algorithm: In a set of arrays, each time you find the smallest number, bring it to the front, then do the same for the next array, until there are only two numbers left, compare and put the smaller number in front to complete the sorting of the array. So the point of sorting arrays is to find a way to get the smallest number, to represent the code recursively, (you can quickly understand the recursion by substitution and the call stack, which is a function calling a function)

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

Once the smallest number is found, sorting the rest is much easier:

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

Another way of thinking about recursion in computers is to rewrite it as a loop:

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

Optimize sort code:

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 } let swap = (array, i, j) => { let temp = array[i] array[i] = array[j] array[j] = temp } let minIndex = (numbers) => { let index = 0 for(let i=1; i<numbers.length; i++){ if(numbers[i] < numbers[index]){ index=i } } return index }Copy the code

The actual complexity of selection sort is generally n^2.

Second, quicksort

The idea of quicksort is to use a number as the benchmark method many times, small to the front, big to the back, this number is sorted, in turn each number is clicked when the benchmark, these numbers are sorted.

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] < pivor){ left.push(arr[i]) } else { right.push(arr[i]) } } return quickSort(left).concat( [pivot],quickSort(right) ) }Copy the code

The time complexity of quicksort is nlog2n.

Merge sort

Selection sort of way of thinking is the array is divided into two parts, the two parts are sorted by default and then two groups of arrays is divided into four groups, repeat this operation, until the separated only a number of arrays, and then to the two that have been sequenced to merge with a number of the array, repeat this operation, until the merged into a full array of that have been sequenced.

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

The time complexity of merge sort is: nlog2n.

Four, counting sort

The idea of counting sort is to use a hash table to record the number N:1. If the number N is found again, add 1. Finally, print out all the keys of the hash table.

let countSort = arr =>{ let hashTable = {}, max = 0, result = [] for(let i= 0; i<arr.length; i++){ 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++){ if(j in hashTable){ for(let i =0; i<hashTable[j]; i++){ result.push(j) } } } return result }Copy the code

The time complexity of counting sort is (n+ Max)