Bubble sort

function bubbleSort(arr){ let 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]){ [arr[j],arr[j+1]] = [arr[j+1],arr[j]] } } } return arr }Copy the code

Selection sort

Select sort starts at the beginning of the array, compares the first element to the other elements, checks all the elements, puts the smallest element in the first place, starts with the second element, and repeats all the way to the end.

function selectSort(arr){ let len = arr.length for(let i = 0; i <= len -1; i++){ for(let j = i; j <= len -1 ; j++){ if(arr[j] < arr[i]){ [arr[j],arr[i]] = [arr[i],arr[j]] } } } return arr }Copy the code

Insertion sort

Insert the core of the sorting ideaLocally ordered (partially ordered)

  • I starts at 1, takes the current number, and compares it to the previous number
  • The second loop, j, starts at 1, assumes that the preceding i-1 are all ordered, makes a judgment, if the preceding number is greater than the current number, then carries out the swap,.
  • Until there are no unsorted numbers left, then sorting is over.
function insertSort(arr){ for(var i = 1; i < arr.length; i++){ for(var j = i; j > 0 ; j--){ if(arr[j-1] > arr[j]){ [arr[j-1],arr[j]] = [arr[j],arr[j-1]] }else if(arr[j-1] <= arr[j]){ break } } } return arr }Copy the code

Quick sort

Thought: “Divide and rule”,

  • Put the ones with less than the reference value on the left, and the ones with more on the right
  • Recurse on the left until the array has length 1

The average time is O(nlogn), and the worst time is O(n^2).

function quickSort(arr){ if(arr.length == 1){ return arr } let left = 0 let right = arr.length-1 let arrLeft = [] let arrRight = [] let pivotIndex = (left + right)>>>1 let pivot = arr.splice(pivotIndex,1)[0] // let pivot = Arr. Splice (pivotIndex,1) also works because only one value can be directly compared to the following number: pivotIndex (pivotIndex,1) 1 < [2] / / true 0 0 < < [1, 3] / / false [1, 3] [0] / / true for (let I = 0; i < arr.length; i++){ if(arr[i] <= pivot){ arrLeft.push(arr[i]) }else{ arrRight.push(arr[i]) } } return quickSort(arrLeft).concat(pivot,... quickSort([arrRight])) }Copy the code

Use Pointers to swap positions

Function quick(arr,begin,end){if(begin >= end){return} let pivot = arr[begin]// Use the leftmost as a reference point let left = begin let right = end while(left < right){ while(arr[right] >= pivot && left < right){ right-- } while(arr[left] <= pivot && left < right){ left++ } [arr[left],arr[right]] = [arr[right],arr[left]] } [arr[begin],arr[left]] = [arr[left],arr[begin]] quick(arr,begin,left-1) quick(arr,left+1,end) } quick(arr,0,arr.length-1) return arr }Copy the code