快速选择

快速选择最坏效率：
快速选择平均效率：O(N)
快速选择最好效率：

假设有一个无序的数组，你不需要将它排序，只要找出里面第10小的值，或第5大的值。
快速选择的优势就在于它不需要把整个数组都排序就可以找到正确位置的值。
快速选择的分区操作只需在上一次分出的一半区域上进行，即值可能存在的那一半。

分区指的是从数组随机选取一个值，以其为轴，将比它小的值放到它左边，比它大的值放到它右边。

分区步骤如下。

(1)左指针逐个格子向右移动，当遇到大于或等于轴的值时，就停下来。
(2)右指针逐个格子向左移动，当遇到小于或等于轴的值时，就停下来。
(3)将两指针所指的值交换位置。
(4)重复上述步骤，直至两指针重合，或左指针移到右指针的右边。
(5)将轴与左指针所指的值交换位置。

class QuickSelect extends Sort {
  
  sort(originalArray, minPosition) {
    const array = [...originalArray];

    if (array.length < minPosition || minPosition <= 0) {
      return null;
    }
    
    const leftArray = [];
    const rightArray = [];

    const pivotElement = array.shift();
    const centerArray = [pivotElement];

    while (array.length) {
      const currentElement = array.shift();

      this.callbacks.visitingCallback(currentElement);

      if (this.comparator.equal(currentElement, pivotElement)) {
        centerArray.push(currentElement);
      } else if (this.comparator.lessThan(currentElement, pivotElement)) {
        leftArray.push(currentElement);
      } else {
        rightArray.push(currentElement);
      }
    }
    
    if(leftArray.length > minPosition - 1) {
      return this.sort(leftArray, minPosition);
    } else if(leftArray.length === minPosition - 1) {
      return pivotElement;
    } else {
      return this.sort(rightArray, minPosition-leftArray.length-centerArray.length)
    }
  }
}

class Sort {
  constructor(originalCallbacks) {
    this.callbacks = Sort.initSortingCallbacks(originalCallbacks);
    this.comparator = new Comparator(this.callbacks.compareCallback);
  }

  /**
   * @param {SorterCallbacks} originalCallbacks
   * @returns {SorterCallbacks}
   */
  static initSortingCallbacks(originalCallbacks) {
    const callbacks = originalCallbacks || {};
    const stubCallback = () => {};

    callbacks.compareCallback = callbacks.compareCallback || undefined;
    callbacks.visitingCallback = callbacks.visitingCallback || stubCallback;

    return callbacks;
  }

  sort() {
    throw new Error('sort method must be implemented');
  }
}

class Comparator {
  /**
   * @param {function(a: *, b: *)} [compareFunction] - It may be custom compare function that, let's
   * say may compare custom objects together.
   */
  constructor(compareFunction) {
    this.compare = compareFunction || Comparator.defaultCompareFunction;
  }

  /**
   * Default comparison function. It just assumes that "a" and "b" are strings or numbers.
   * @param {(string|number)} a
   * @param {(string|number)} b
   * @returns {number}
   */
  static defaultCompareFunction(a, b) {
    if (a === b) {
      return 0;
    }

    return a < b ? -1 : 1;
  }

  /**
   * Checks if two variables are equal.
   * @param {*} a
   * @param {*} b
   * @return {boolean}
   */
  equal(a, b) {
    return this.compare(a, b) === 0;
  }

  /**
   * Checks if variable "a" is less than "b".
   * @param {*} a
   * @param {*} b
   * @return {boolean}
   */
  lessThan(a, b) {
    return this.compare(a, b) < 0;
  }

  /**
   * Checks if variable "a" is greater than "b".
   * @param {*} a
   * @param {*} b
   * @return {boolean}
   */
  greaterThan(a, b) {
    return this.compare(a, b) > 0;
  }

  /**
   * Checks if variable "a" is less than or equal to "b".
   * @param {*} a
   * @param {*} b
   * @return {boolean}
   */
  lessThanOrEqual(a, b) {
    return this.lessThan(a, b) || this.equal(a, b);
  }

  /**
   * Checks if variable "a" is greater than or equal to "b".
   * @param {*} a
   * @param {*} b
   * @return {boolean}
   */
  greaterThanOrEqual(a, b) {
    return this.greaterThan(a, b) || this.equal(a, b);
  }

  /**
   * Reverses the comparison order.
   */
  reverse() {
    const compareOriginal = this.compare;
    this.compare = (a, b) => compareOriginal(b, a);
  }
}