# 快速排序（空间优化）

// 对于这种空间复杂度优化的算法来说，swap 是必须的
function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

/**
 * 对于这种空间复杂度优化的算法来说，helper 函数是必须的
 * 因为我们需要用两个指针来指明当前数组开始和结束的位置
 */
function quickSortHelper(arr, l, r) {
  // base case
  if (r - l < 1) return;
  if (r - l === 1) {
    if (arr[l] > arr[r]) swap(arr, l, r);
  }

  /**
   * 这个时候我们需要 partition 了
   * 先选择 pivot（选择 pivot 的方法也有讲究）
   * 
   * 选择三个点：头、尾、中间，取这三者的中位数作为pivot
   * 这也是一种优化，比直接选【头/中间/尾】的算法要牛逼
   * 可以用来向面试官展示你的与众不同之处
   */
  const mid = Math.floor((l + r) / 2);
  if (arr[l] > arr[mid]) swap(arr, l, mid);
  if (arr[l] > arr[r]) swap(arr, l, r);
  if (arr[mid] > arr[r]) swap(arr, mid, r);

  /**
   * 现在，arr 的三个点已经排序完毕了，pivot 就在 mid 的位置
   * 然后把 mid 上的元素（pivot）给 swap 到数组的末尾
   * 这么做是为了在 partition 的过程中更加方便
   */
  swap(arr, mid, r);
  const pivot = arr[r];

  /**
   * 接下来开始区分左侧的部分与右侧的部分
   * 算法是这样的：
   * 
   * - 从位置 l 开始，先设置 s(start) = e(end) = l
   * - while e < r 
   *   - 如果当前的元素（arr[e]）>= pivot，那就 e++
   *   - 否则，就 swap(s, e)，然后 s++, e++
   * - 在最后，还需要 swap(s, e)
   * 
   * 该算法正确，是因为
   * 1. 在当前元素比 pivot 大的时候 e++，因此当下次碰见比 pivot 小的元素时，
   *    [s, ..., e-1] 这一部分的数组都比 pivot 大（或者等于）
   * 2. 然后，在碰见比 pivot 小的元素时，swap(s, e) ，也就是把比 pivot 小的元素
   *    给 swap 到了比 pivot 大的元素左边，而当前 s 的位置，就是区分左右部分的位置
   * 3. 接着，s++，e++，此时 s 所在的位置就是右侧部分的开始，e 所在的位置则是“遇见”
   *    了一个之间没见过的元素，然后又需要从步骤1开始做起
   * 4. 在这些杂七杂八的都做完后，s 所在的位置就是右侧部分的开始，s 所在位置左边的所有
   *    元素都比 pivot 小，而 e 则是已经抵达了 pivot 的位置。这个时候 swap(s, e)，
   *    就相当于把 pivot 给 swap 到了左侧部分结束位置的下一个位置
   * 5. 因此，pivot 现在在正确的位置上，其左侧的内容比它小，右侧的内容比它大
   * 6. 所有的操作就是在原数组上操作，没有新建空间，但 swap 的操作会消耗空间（每次都要建temp），
   *    而在每一层都有 O(n) 次 swap，所以在每一层的空间复杂度都是 O(n)....真的是这样吗？
   * 7. 想知道答案的话，请往下看
   */
  let s = e = l;
  while (e < r) {
    if (arr[e] >= pivot) e++;
    else {
      swap(arr, s, e);
      s++;
      e++;
    }
  }

  swap(arr, s, e);
  /**
   * 现在，pivot 就在 s 的位置
   * partition 完成了，pivot 左侧比其小，右侧比其大
   * 因此，继续递归，递归的方式就是传递 l 和 r
   */
  quickSortHelper(arr, l, s - 1);
  quickSortHelper(arr, s + 1, r);
}

function quickSort(arr) {
  // edge case
  if (!arr || !arr.length) return [];

  // 调用 helper 函数
  quickSortHelper(arr, 0, arr.length - 1);

  return arr;
}

// 为了取 median of three
function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function quickSort(arr) {
  // edge case
  if (!arr || !arr.length) return null;

  // base case
  if (arr.length < 2) return arr;

  // 选择三个点：头、尾、中间，取这三者的中位数作为pivot
  const mid = Math.floor(arr.length / 2);
  if (arr[0] > arr[mid]) swap(arr, 0, mid);
  if (arr[0] > arr[arr.length - 1]) swap(arr, 0, arr.length - 1);
  if (arr[mid] > arr[arr.length - 1]) swap(arr, mid, arr.length - 1);

  // 现在，arr的三个点已经排序完毕了，pivot就在mid的位置
  const pivot = arr[mid];
  const left = [];
  const right = [];

  // left
  for (let i = 0; i < mid; i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }

  // right
  for (let i = mid + 1; i < arr.length; i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }

  return quickSort(left).concat([pivot], quickSort(right));
}

const arr = [];
for (let i = 50000000; i >= 0; --i) {
  arr.push(i);
}
quickSort(arr);