4 basic sorting algorithms

Select sort

1. Find the smallest number in the array
2. Exchange operation: the smallest number is always in the first place
3. Traverse the array accordingly
4. The following is the code implementation

//
let sort = (numbers) => {
//
  for(let i=0; i< numbers.length -1; i++){          
    console.log(`----`)//log 
    console.log(`i: ${i}`)
    //i 
    let index = minIndex(numbers.slice(i))+ 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
}

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

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

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

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.reverse() : numbers
    }
}
 

Quick sort

1. Set the number in the middle of the array as a base number
2. The numbers smaller than the benchmark number are placed on the left to form an array, and the numbers greater than the benchmark number are placed on the right to form an array
3. Execute 1, 2 points in sequence
4. When the length of the array is less than 2, it cannot be grouped and returned to the array directly
5. Look at the execution diagram first

6. The following is the code implementation

let quickShort = (numbers)=>{
    if(numbers.length<2){
    return numbers
    }
    let index = Math.floor(numbers.length/2)
    let middel = numbers.splice(index,1)[0]    //splice 
                                               //[0]
    console.log(`midedl:${middel}`)            //log 
    let left = []
    let right=[]
    for(let i=0;i<numbers.length;i++){
        if(numbers[i]>midel){
             right.push(numbers[i])
          }else{ 
            left.push(numbers[i])
           }
        }
  console.log(`left:${left}`)
  console.log(`right:${right}`)
 //concat 
  return quickShort(left).concat(midel, quickShort(right))            
}
let numbers = [1,5,6,14,2,12,7,10,0,22,11]
quickShort(numbers)
 

Merge and sort (disassemble first, then combine)

1. There is no base number, the array is divided into two left and right arrays in half
2. Continue to perform operation 1 until only one number is stored in the array, which is actually an entry
3. Compare pairwise arrays
4. Combine the sorted arrays
5. Look at the execution diagram first

6. The following is the code implementation

let mergeShort = (numbers)=>{
  if(numbers.length<2){    //2 
    return numbers
  }
 //1 
  let left = numbers.slice(0, Math.floor(numbers.length/2))
  let right = numbers.slice( Math.floor(numbers.length/2),numbers.length)
  console.log(`left:${left}`)
  console.log(`right:${right}`)
  return merge(mergeShort(left),mergeShort(right))  
}
//
let merge = (a,b)=>{
  if(a.length === 0){  // a   0   b  
    return b
  }
  if (b.length === 0){ // b  0  a  
    return a
  }
 // a   b      b 
  return a[0]>b[0] ? [b[0]].concat(merge(a,b.splice(1))) : [a[0]].concat(merge(b,a.splice(1)))
}
let numbers = [2,9,1,7,4,11,8,0,13,6] 
mergeShort(numbers)
 

Count sort

1. Traverse each item in the array into the hash table, and mark the maximum value
2. Traverse the hash table (0~max), push the value in the array
3. Look at the execution diagram first

4. The following is the code implementation

let countSort = numbers=>{
  let max = 0
  let hashTable = {}
  let result = []
  for(let i=0;i<numbers.length;i++){
    if(numbers[i]>max){    //
      max = numbers[i]
    }
    if(!(numbers[i] in hashTable)){    //number[i] 
      hashTable[numbers[i]] = 1        //value = 1
     }else{                            // value += 1
      hashTable[numbers[i]] +=1 
     }
  }
  for(let j=0;j<=max;j++){             //
    if(j in hashTable){
      for(let i=0;i<hashTable[j];i++)      //push 
      result.push(j)
    }
  }
  return result
}
let numbers = [9,1,7,4,11,2,8,13,6,15,3]
countSort(numbers)
 

summary

• All recursion can be changed to loop
• When the algorithm is difficult to understand, it is much easier to draw an execution graph
• Pseudo-code is also a very good method, and it is not difficult to understand according to the code into the data
• When the algorithm is implemented in code, a lot of errors are found. The log debugging method will give you a lot of help
• There are a lot of details to be dealt with when writing code with loops. You may not notice when you understand the algorithm. Details like judging boundary conditions must be considered.