This article introduces five common front-end sorting methods.

Bubble sort

Bubble sort gets its name from the way it sorts, traversing the array, comparing each item to the next, and switching if it doesn’t fit, in a total of n rounds, where n is the length of the array. After n rounds, the array is fully sorted. The items that fit the bill bubble to the end of the array like bubbles rising from the bottom to the surface, so it’s called bubble sort.

  • Time complexity O(n^2)
  • Space complexity O(1)
  • Stability: stability
Var arr =,8,2,6,10,9,3,1,5,4 [7]; function bubbleSort(arr) { const len = arr.length; for(let i = 0; i < len - 1; i++) { for(let j = 0; j < len - 1 - i; J++) {if (arr [j] > arr [j + 1]) {/ / before a than a big, after exchanging position [arr [j], arr [m + 1]] = [arr [j + 1], arr [j]]. } } } return arr; } bubbleSort(arr); / /,2,3,4,5,6,7,8,9,10 [1]Copy the code

Selection sort

Find the smallest (largest) value in the array and place it first, then find the second-smallest value and place it second… And so on.

  • Time complexity O(n^2)
  • Space complexity O(1)
  • Stability: unstable
Var arr =,8,2,6,10,9,3,1,5,4 [7]; function selectionSort(arr) { const len = arr.length; for(let i = 0; i < len; i++) { let minIndex = i; for (let j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; } if (minIndex ! = i) { [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; } } } return arr; } selectionSort(arr); / /,2,3,4,5,6,7,8,9,10 [1]Copy the code

Insertion sort

  • Time complexity O(n^2)
  • Space complexity O(1)
  • Stability: stability
Var arr =,8,2,6,10,9,3,1,5,4 [7]; function insertionSort(arr) { for (let i = 1; i < arr.length; i++) { const temp = arr[i]; // let j = I; While (j > 0 &&arr [j-1] > temp) {// Compare arr[j] = arr[j-1]; // If the previous element is larger than it, the previous element is placed at the current element's position j--; } arr[j] = temp;} arr[j] = temp; } return arr; } insertionSort(arr); / /,2,3,4,5,6,7,8,9,10 [1]Copy the code

Merge sort

To sort an array, we divide the array into two parts, sort the two parts separately, and merge the sorted parts together so that the entire array is sorted. Merge sort is divide-and-conquer. Divide and conquer, as the name suggests, is to divide and conquer, to solve a big problem by breaking it down into smaller sub-problems. When small sub-problems are solved, big problems are solved.

  • The time complexity of fractions is O(logN), the time complexity of combinations is O(n), the time complexity is O(nlogN).
  • Space complexity: O(n)
  • Stability: O(N)
Var arr =,8,2,6,10,9,3,1,5,4 [7]; function mergeSort(arr) { const rec = (arr) => { if (arr.length === 1) { return arr; } const mid = Math.floor(arr.length / 2); const left = arr.slice(0, mid); const right = arr.slice(mid, arr.length); const orderLeft = rec(left); const orderRight = rec(right); const res = []; while(orderLeft.length || orderRight.length) { if(orderLeft.length && orderRight.length) { res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift()) } else if(orderLeft.length) { res.push(orderLeft.shift()); } else if(orderRight.length) { res.push(orderRight.shift()); } } return res; } const res = rec(arr); res.forEach((n, i) => { arr[i] = n; }); return arr; } mergeSort(arr);Copy the code

Quick sort

  • Recursion is order logN in time.
  • The time complexity of partition operations is O(n)
  • Time complexity: O(nlogN)
  • Space complexity: O(logn)
  • Stability: unstable
Var arr =,8,2,6,10,9,3,1,5,4 [7]; function quickSort(arr) { if (arr.length <= 1) { return arr; } let left = []; let right = []; let pivotValue = arr[0]; let len = arr.length; for(let i = 1; i < len; i++) { if (arr[i] < pivotValue) { left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort(left).concat(pivotValue, quickSort(right)); } quickSort(arr);Copy the code

Refer to the article

Six kinds of sorting algorithm JavaScript implementation and summary

The Beauty of JavaScript Data Structures and Algorithms – Top 10 classic sorting algorithms