Reference quicksort is a sorting algorithm developed by Tony Hall. On average, order n two items and compare them (nlogn) several times. In the worst case, a comparison of TWO (N2) steps is required, but this is not common. In fact, quicksort is generally significantly faster than any other two (NLOGN) algorithms because its inner loop can be implemented efficiently on most architectures.

Algorithm thought

The essence of quicksort is divide and conquer, and then divide and conquer recursively based on bubble sort.

  1. Selects a reference value from the array
  2. Rearranging an array based on a reference value, putting elements smaller than the reference value in front, elements larger than the reference value in back, and then the reference value in the middle is called partition.
  3. Recursively arrange the left and right partitions respectively

The demo

Code Implementation Simple Version (JS)

const arr = [3.44.38.5.47.15.36.26.27.2.46.4.19.50.48]

/ * * *@param {Number[]} arr
 * @param {Number} l
 * @param {Number} r* /
function quickSort(arr, l, r) {
  if (l >= r) return
  let x = l, / / pointer to the left
    y = r, / / right pointer
    base = arr[l] // take the first element as the reference value
  // partition
  while (x < y) {
    while (x < y && arr[y] >= base) { // Find the first element from the right of the array that is less than the reference value
      y--
    }
    if (x < y) { // Place the element less than the base value to the left of the base value with the left pointer one step back
      arr[x++] = arr[y]
    }
    while (x < y && arr[x] <= base) { // Find the first element from the left of the array that is greater than the reference value
      x++
    }
    if (x < y) { // Place the element greater than the base value to the right of the base value, while the right pointer moves forward
      arr[y--] = arr[x]
    }
  }
  arr[x] = base // All elements smaller than the base value are on the left, and elements larger than the base value are on the right
  // Recurse the left and right halves here
  quickSort(arr, l, x - 1)
  quickSort(arr, x + 1, r)
  return
}

quickSort(arr, 0, arr.length - 1)

console.log(arr) / / [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
Copy the code

Unilateral recursive

/ * * *@param {Number[]} arr
 * @param {Number} l
 * @param {Number} r* /
function quickSort(arr, l, r) {
  while (l < r) {
    let x = l,
      y = r,
      base = arr[l]
    while(x < y) {
      while (x < y && arr[y] >= base) {
        y--
      }
      if (x < y) {
        arr[x++] = arr[y]
      }
      while (x < y && arr[x] <= base) {
        x++
      }
      if (x < y) {
        arr[y--] = arr[x]
      }
    }
    arr[x] = base
    quickSort(arr, x + 1, r)
    r = x - 1 // Reduce one recursion}}Copy the code