The process of shallow

Quicksort works by setting some sort of intermediate reference. By comparing this baseline value, groups larger than this value and smaller than this value can be distinguished. Then continue to differentiate the array into the baseline, in the comparison. Until the array is no longer sharable, the layers are merged upwards and the result is returned.

Time order nlogn.

Code implementation ideas

  1. Determining whether the array length passed in is divisible is also a criterion for terminating recursion
  2. Get the intermediate value of the array and extract it
  3. Define two arrays to hold the left and right datasets. Loop through the array, storing values greater than the middle in right and values less than the middle in left.
  4. Recursive, respectively in the left and right array values, again cut judgment back to the first step
  5. After all values have been split and compared, the values are merged back from the bottom up and returned out

Code implementation

const quickSort = arr= > {
  if(arr.length <= 0) return arr
  const middleNumber = arr.splice(Math.floor(arr.length / 2), 1) [0]
  const left = []
  const right = []
  for(let i = 0; i < arr.length; i++) {
    if(arr[i] > middleNumber) right.push(arr[i])
    else left.push(arr[i])
  }
  return quickSort(left).concat(middleNumber, quickSort(right))
}
Copy the code

legend

The painting is a little ugly. The above is my personal understanding. If there is something wrong, please point it out