[Address of Station B]

Bubble sort

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+1]<arr[j]) [arr[j],arr[j+1]] = [arr[j+1],arr[j]] } } return arr; }Copy the code

The time is (O(n^2)). Each time you compare two values in the array, if the first one is greater than the last one, switch places, so that after each inner loop, you push the maximum value of the unsorted part to the last part of the unsorted part and do this len-1 times, The whole array is going to be ordered and the thing to notice is that the inner loop, because every time it’s going to push the largest value to the end of the range, it doesn’t have to go to the end of the array every time

Selection sort

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

It’s (O(n^2)) find the minimum value of the unsorted interval each time, and if the minimum value of the unsorted interval is not the index of the loop, swap the values of the two places so that each loop determines the minimum value of the unsorted interval to the index of the loop len-1 times, and the whole array becomes ordered

Insertion sort

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

It’s order n^2 time, and just like a card, every time you put a new value in the proper place in an ordered array, it’s going to keep the interval before the current index in order until you get to the end of the array

Hill sorting

function shellSort(arr){ const len = arr.length; let step = len >> 1; For (step; 0<step; Step = step >> 1){// group insert sort for(let I = step; i<len; i++){ for(let j = i; j>=step&&arr[j]<arr[j-step]; j-=step){ [arr[j-step],arr[j]] = [arr[j],arr[j-step]] } } } return arr }Copy the code

Hill sort is an algorithm that optimizes insertion sort by comparing the size of two elements separated by steps from back to front, and if the latter is less than the previous, then switch places so that after each step the elements in each set of steps are ordered by steps divided by 2 until the step is 1, The whole array is ordered so that the swap process is as short as possible

Merge sort

function mergeSort(arr){
  if(arr.length===1) return arr;
  function merge(left,right){
    const res = [];
    while(left.length&&right.length){
      if(left[0]<right[0])
        res.push(left.shift())
      else
        res.push(right.shift())
    }
    return [...res,...left,...right]
  }
  const mid = arr.length >> 1;
  return merge(
    mergeSort(arr.slice(0,mid)),
    mergeSort(arr.slice(mid))
  )
}
Copy the code

Time complexity for (O (nlogn) by recursive split array for each of the two points, until there is only one element in an array In the process of recursive backtracking, combination or so two parts array combination process, each time to compare the two array first, remove smaller values into the result array, until one of the two arrays to empty, the combination results back

Quick sort

Fast row 1

function quickSort(arr){ if(arr.length<2) return arr; const base = arr.pop(),left = [],right = []; for(let i = 0; i<arr.length; i++){ if(arr[i]<base) left.push(arr[i]) else right.push(arr[i]) } return [...quickSort(left),base,...quickSort(right)] }Copy the code

You take one of the elements of the array as base, you put anything less than that base on left, and you put it on right and you keep recursively splitting the array until you get to 1 and you recursively combine left,base, and right

Fast row 2

function handle(arr, left, right) { if(left>=right) return left; const base = arr[left] let l = left + 1; let r = right; while (l <= r) { if(arr[l] < base) { l++; } else if(arr[r] >= base) { r--; <} else {/ / there l r && arr [l] > arr exchange situation of [r] [arr [l], arr [r]] = [arr [r], arr [l]] l++, r -}} / / will start with the last less than its value to exchange [arr [left], arr [l - 1]] = [arr] [l - 1, arr [left]] / / return benchmark index return l - 1; } function quickSort(arr, l, r) { if (l < r) { const ind = handle(arr, l, r); // quickSort(ARr, L, ind-1); QuickSort (arr, IND + 1, r); } return arr; }Copy the code

Check for l

arr[r] in each interval by double-pointer, and if so, swap the values of the two elements

Finally, the base value is swapped with the last element less than it, and the subscript position of the last element less than the base value is returned

Because in the process of double-pointer movement, the left pointer element is larger than the right pointer element, and because the reference value is exchanged with the value of the last element smaller than it, the elements before the reference value must be smaller than it, and the elements after it must be greater than or equal to it

Divide the array by the base value, and recursively process the next two intervals

The time complexity is O(nlogn), but the space complexity of quickrow 1 is higher. The space complexity of quickrow 2 is less than or equal to O(n-1) in the personal test

Count sorting

Counting sort is by

function countSort(arr){ countArr = [], res = []; for(let i = 0; i<arr.length; i++){ if(countArr[arr[i]] === undefined) countArr[arr[i]] = 0 countArr[arr[i]]++ } for(let i = 0; i<countArr.length; i++){ while(countArr[i]){ res.push(i) countArr[i]-- } } return res; }Copy the code

The counting sort process is

1. Through the sorting algorithm that puts the value of the array to be sorted into the corresponding subscript position of the counting array and records the quantity, if the same value occurs several times, the corresponding number of times exists in the corresponding subscript position of the counting array

2. Iterate through the count array. If the current subscript of the count array is not 0, push the current subscript into the result array with the current subscript -1 until it is 0

Counting sort, however, is very limited in that it can only sort non-negative integers, because the subscripts of arrays are integers starting at 0

What if there are negative integers in the array

function countSort(arr){ const min = Math.min(... arr), countArr = [], res = []; for(let i = 0; i<arr.length; i++){ if(countArr[arr[i]-min] === undefined) countArr[arr[i]-min] = 0 countArr[arr[i]-min]++ } for(let i = 0; i<countArr.length; i++){ while(countArr[i]){ res.push(i+min) countArr[i]-- } } return res; }Copy the code

When stored in a count array, the current value is stored minus the smallest value in the array to be sorted. This ensures that negative integer values can have subscripts greater than or equal to 0

Add min as you iterate through the count array and fetch the value

What if it’s a non-integer, or even a list of goods?

First of all, if you’re dealing with an array like this, is it better to sort it in another way?

If you also want to sort by counting sort, what I have in mind here is a hash table that maintains the relationship between sorting criteria and corresponding subscripts. If you have a different method, please leave a comment in the comments section.

Finally, there is, of course, sort, which is not covered in this article

If you have any questions or suggestions, please leave a comment!