A list,

  • Time complexity: O(nlogn)
  • Space complexity: O(logn)
  • Stable: No
  • Advantages: Fast, less data movement
  • Cons: unstable

Second, core ideas

  • Divide and conquer, select the base value, divide into areas smaller than the base value, and treat areas larger than the base value.
  • Recursively, the partition is then selected base value, divided into two smaller regions, until no longer can be divided.

3. Sorting process diagram

In fact, the general process is to select the base value, partition, repeat the above. It’s kind of like a binary tree, which has a depth of log base 2n.

Four, the code

Code address: github.com/shubenwumin…

For the time being, let’s write three ways, which do not optimize the selection of the base value, the base value is directly selected to the left.

  • The first kind of non-in-place sorting, written in a simple way, can cope with the interview, but the interviewer will usually ask the space complexity can be optimized?
  • The second method optimizes spatial complexity by sorting in place
  • The third is an optimization of the second, which optimizes the number of swaps

The first is non-in-situ sorting

This code doesn’t need much explanation, just look at my comments.

Const quickSort = function (arr) {if(arr. Length < 2) return arr; // Const pivot = arr.splice(0, 1); // const left = []; // const right = []; // Allocate the remaining elements to the left and right partitions according to certain rules. for(let i = 0; i < arr.length; I++) {// the value greater than the base value is allocated to the right area, If (arr[I] > pivot[0]) {right.push(arr[I])} else {left.push(arr[I])}} Return quickSort(left).concat(pivot). Concat (quickSort(right)); }Copy the code

Second, in situ sorting

The code looks at quickSort first and then partition. Almost every line of the code is commented. A few questions before you look at the code. Question:

  • How are left and right zones divided?
  • With whom does the base value swap, should it be in the left or right region?
  • How do I record the subscript of an element to be swapped with a reference value?
Const partition = function(arr, left, right) {// Pivot = pivotValue [left]; // let leftLast = left; For (let I = left + 1; let I = left + 1; i <= right; If (arr[I] <= pivotValue) {leftLast++; if(arr[I] <= pivotValue) {if(arr[I] <= pivotValue) {leftLast++; [arr[i], arr[leftLast]] = [arr[leftLast], arr[i]]; }} // The order of the array at the end of the loop should already be base + left + right, but we want the order left + base + right, [arr[left], arr[leftLast]] = [arr[leftLast], arr[left]]; // return leftLast; } const quickSort = function (arr, left = 0, right = arr. length-1) {if (left >= right) return; QuickSort (ARr, left, Pivotindex-1); pivotIndex = partition(ARr, left, right); QuickSort (arr, pivotIndex + 1, right); // Return arr; }Copy the code

Third, in situ sorting II

It’s an improved version of the second one, where you find the small one and you swap it once, and you find the big one and the small one at the same time. Record the first subscript of an element smaller than the base value from right to left, record the first subscript of an element larger than the base value from left to right, and swap them. Until the two record subscripts intersect.

Let’s go straight to the code. Or that sentence, the comment is very detailed, do not understand the above said, look at the code, the code to see the above paragraph of words you will understand.

Const partition = function(arr, left, right) {// Const pivotValue = arr[left]; // let I = left; // let j = right; While (I < j) {// Record a small value less than the benchmark from right to left while(I < j && arr[j] >= pivotValue) {j--} // Record a large value greater than the benchmark from left to right while(I < j && arr[I] <= PivotValue) {i++} the if (I < j) {/ / exchange find great value and small [arr [I], arr [j]] = [arr [j], arr [I]] / / exchange after continue to find i++; j--; }} // I === j; [arr[i], arr[left]] = [arr[left], arr[i]]; // return base subscript I; } const quickSort = function (arr, left = 0, right = arr. length-1) {if (left >= right) return; QuickSort (ARr, left, Pivotindex-1); pivotIndex = partition(ARr, left, right); QuickSort (arr, pivotIndex + 1, right); // Return arr; }Copy the code