快排

核心思想

采用“分而治之”的思想，进行排序。选定一个基点，进行一趟遍历，将大于小于基点分别置换到该点的左边和右边（视乎升序降序需要），然后分别对左边区域和右边区域进行同样操作，直至区域只剩下一个点，此时排序完成。

代码实现

  /**
   * 快排
   * @param {Array} arr 待排序数组
   * @returns arr 排好序的数组
   */
function quickSort(arr) {
    function sort(arr, l, r) {
    // 如果只有一个元素，排序完成
    if (l < r) {
      // 交换排序，分区
      const index = partition(arr, l, r);
      // 对分区递归处理
      sort(arr, l, index - 1);
      sort(arr, index + 1, r);
    }
    return arr;
  }

  /**
   * 以首元素为基点进行一轮快排
   * @param {Array} arr 数组
   * @param {Number} l 低位下标
   * @param {Number} r 高位下标
   * @returns index 基本点的下标
   */
  function partition(arr, l, r) {
    const baseIndex = l;
    const base = arr[baseIndex];

    while (l < r) {
      // 高位往低位寻找比基点值小的元素
      while (arr[r] >= base && l < r) {
        --r;
      }
      // 低位往高位寻找比基点大的元素
      while (arr[l] <= base && l < r) {
        ++l;
      }
      //交换位置
      swapByIndex(arr, l, r);
    }
    // 将基本点放置在排好的数中间
    swapByIndex(arr, baseIndex, l);
    // 返回基本点点下标作为分区标识
    return l;
  }

  /**
   * 根据下标，将数组元素互换位置
   * @param {Array} arr 数组
   * @param {Number} a 元素下标
   * @param {Number} b 元素下标
   * @returns arr 操作后的数组
   */
  function swapByIndex(arr, a, b) {
    const temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
    return arr;
  }

  return sort(arr, 0, arr.length - 1);
}