Bubble sort

A common way of sorting; A simple and easy to understand sorting method; A stable way of sorting; Time complexity: O(n^2); Features: Stable

// Target array
const list = [5.6.3.12.5.2]
const len = list.length;

// Iterate over the target array
for(let i = 0 ; i < len ; i++){

    // Go through the target array,
  for(let j = i+1 ; j < len ; j++){
   // Interswitch larger elements with smaller elements in adjacent elements
    [list[i],list[j]] = [list[j],list[i]]
  }
}
console.log(list.join(', '))
Copy the code

Selection sort

The main principle of a simple and intuitive sorting method: select the minimum value of the array from the target array, and put the minimum value at the beginning of the array; And then we take the smallest of the remaining elements and put it in the second part of the array; And so on, until the last digit of the destination array. Finish sorting. Time complexity: O(n^2) is not a stable sort


// Select sort
const list = [5.6.3.12.5.2]
const len = list.length;
for(let i = 0 ; i  < len ; i++){
  let min = list[i];
  let idx = i;
  for(let j = i+1 ; j < len ; j++){
    if(list[j] < min){
      min = list[j];
      idx = j
    }
  }
  / / exchange
  [ list[i], list[idx]] = [list[idx],list[i]]
}
console.log(list.join(', '))
Copy the code

Insertion sort

Similar to selection sort; Compares the current element with the previously sorted array, starting with the subscript 1 of the destination array. Insert elements into the sorted array; That is, insert sort; Time complexity: O(n^2) insertion sort is stable sort

// Get the array
const list = [5.6.3.12.5.2]
const len = list.length;
// Start with the first one, because the 0th one doesn't need to be sorted
for(let i = 1 ; i < len  ; i++){
  // Get the first data, do you want to iterate through the previous data;
  let j = i-1;
  // Save the current data
  const curr =  list[i]
  while(j>=0 && list[j] > curr){
    list[j+1] = list[j];
    j--;
  }
  list[j+1] = curr
}
console.log(list.join(', '))

Copy the code

Hill sorting

Advanced insert sort or optimized version of insert sort; Time complexity O(n*logN); But it’s not a stable sort;


// Get the array again
const list = [5.6.3.12.5.2]

const len = list.length;

// Find the grouping, usually half of the array
let mid  = Math.floor(len/2);

// then loop to shrink the group's length components, such as starting with 10, then 5,2,1,0
while(mid >0) {for(let i = mid ; i < len ; i++){
    for(let j = i - mid ; j >=0 && list[j] > list[mid+j] ; j-=mid){
      const t = list[j];
      list[j] = list[j+mid];
      list[j+mid] = t
    }  
  }
  mid  = Math.floor(mid/2);
  
}
console.log(list.join(', '))


Copy the code

Quick sort

The main idea is to split the target array; Split the target array into two parts; The split rule is to find any element in the array; Data less than the element is placed on the left, and data greater than the modified element is placed on the right. Then, divide the left and right side data according to the above method. Since we’re doing it the same way, the first thing to think about is recursion; The code is as follows: the time complexity of quicksort is O(n*logN); Because when you do recursion, you definitely need space; So space complexity: O(logN); But quicksort is not a stable sort


// Fast recursive method

const list = readline().split(', ').map(Number);


const loop=(arr) = >{
  if(arr.length <=1) return arr;
  const p = arr.pop();
  const left = [];
  const right = []
  for(let i = 0 ; i < arr.length ; i++){
    if(arr[i] < p){
      left.push(arr[i])
    }else{
      right.push(arr[i])
    }
  }
  / / recursion
  return loop(left).concat(p).concat(loop(right))
};
console.log(loop(list).join(', '))
Copy the code

Why is quicksort fast?

Using the idea of divide and conquer, compare the elements with as few elements as possible to find their proper position