Quick sort

Divide and conquer, that is, divide it into parts and solve it one by one

Ideas:

  • In the array, select a number as the “pivot”.
  • Divide an array intoOr soTwo parts, less thanThe benchmarkOn theThe left part, is more thanThe benchmarkOn theThe right part.
  • For the left and right parts of the baseline, repeat steps 1 and 2 until there is only one element left in all parts.

Animation Reference:

Code implementation

class ArrayList {
  array = [];

  // Used to insert numbers
  insert(item) {
    this.array.push(item);
  }

  // Quicksort
  quickSort() {
    const quick = (array) = > {
      if (array.length <= 1) {returnarray; }let pivotIndex = Math.floor(array.length / 2);
      let pivot = array.splice(pivotIndex, 1) [0];
      let left = [];
      let right = [];
      for (let i = 0; i < array.length; i++) {
        if (array[i] > pivot) {
          right.push(array[i]);
        } else{ left.push(array[i]); }}return quick(left).concat([pivot], quick(right));
    };
    return this.array = quick(this.array); }}let list = new ArrayList();
list.insert(12);
list.insert(2);
list.insert(45);
list.insert(123);
list.insert(481);
list.insert(56);
console.log(list.array);

// Call quicksort
list.quickSort();
console.log(list.array);

Copy the code

Quicksort efficiency

Time complexity: O(nlogn)