快速排序

题目：将数组按升序排列。例：[9, 39, 7, 9, 10, 78, 3] → [3, 7, 9, 9, 10, 39, 78]。

1. 实现一：递归 + concat（思路清晰）

取中点作为基准（pivot），把小于基准的放进 left、不小于的放进 right，再递归拼接：

// [9 39 7 9 10 78 3] 进行升序排序

var sortArray = function(nums) {
  if (nums.length <= 1) return nums;
  let pivotIndex = Math.floor(nums.length / 2);
  let mid = nums.splice(pivotIndex, 1)[0];
  let left = [], right = [];

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

  return sortArray(left).concat([mid], sortArray(right));
};

优点：思路最直接，每次都"取中分两半"，类似归并的分裂模式；代码短。
缺点：splice 会改动原数组；额外分配 left / right 两个数组，空间占用 O(n log n)；稳定性依赖于实现。

2. 实现二：双哨兵原地交换（思路二）

用两个哨兵 i（左）、j（右）从两头往中间扫描。j 从右向左找第一个比基准（key = arr[from]）小的元素，i 从左向右找第一个比基准大的元素，两者交换；当 i === j 时把基准换到 i 位置，再递归处理两侧。

/**
 思路：两个哨兵 i、j；j 从右边找比基数小的，i 从左边找比基数大的，
       然后交换两个目标元素的位置，直到 i=j，然后交换 i 和基数的位置，递归处理。
**/
function quick_sort(arr, from, to) {
  let i = from; // 哨兵 i
  let j = to;   // 哨兵 j
  let key = arr[from]; // 标准值
  if (from >= to) {    // 如果数组只有一个元素
    return;
  }
  while (i < j) {
    while (arr[j] > key && i < j) {
      // 从右边向左找第一个比 key 小的数，找到或者两个哨兵相碰，跳出循环
      j--;
    }
    while (arr[i] <= key && i < j) {
      // 从左边向右找第一个比 key 大的数，找到或者两个哨兵相碰，跳出循环
      // 这里的 = 号保证在本轮循环结束前，key 的位置不变，
      // 否则跳出循环后交换 i 和 from 位置时，from 上的元素有可能已经不是 key
      i++;
    }
    /**
     代码执行到这里，
       1、两个哨兵都找到了目标值。
       2、j 哨兵找到了目标值。
       3、两个哨兵都没找到（key 是当前数组最小值）。
    **/
    if (i < j) { // 交换两个元素的位置
      const temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }
  arr[from] = arr[i]; //
  arr[i] = key;
  quick_sort(arr, from, i - 1);
  quick_sort(arr, i + 1, to);
}