进阶排序：快排 / 归并 / 堆排序

// 运行环境：Node.js 14+
// 保存为 dsa-l18.js，执行：node dsa-l18.js

// 快速排序：选基准 pivot，分区使左小右大，递归两侧
function quickSort(a) {
  if (a.length <= 1) return a
  const [pivot, ...rest] = a
  const left = rest.filter(x => x < pivot)
  const right = rest.filter(x => x >= pivot)
  return [...quickSort(left), pivot, ...quickSort(right)]
}
// 原地版（更省空间，用双指针分区，经典写法）：
function quickSortInPlace(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return a
  let i = lo
  for (let j = lo; j < hi; j++) if (a[j] < a[hi]) { [a[i], a[j]] = [a[j], a[i]]; i++ }
  [a[i], a[hi]] = [a[hi], a[i]] // 基准归位
  quickSortInPlace(a, lo, i - 1); quickSortInPlace(a, i + 1, hi)
  return a
}

// 归并排序：分两半各自排好，再合并两个有序数组
function mergeSort(a) {
  if (a.length <= 1) return a
  const mid = a.length >> 1
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)))
}
function merge(L, R) {
  const out = []; let i = 0, j = 0
  while (i < L.length && j < R.length) out.push(L[i] <= R[j] ? L[i++] : R[j++])
  return out.concat(L.slice(i), R.slice(j))
}

// 堆排序：建最大堆，反复把堆顶（最大）换到末尾
function heapSort(a) {
  a = a.slice()
  const n = a.length
  const siftDown = (i, size) => {
    while (true) {
      let m = i, l = 2*i+1, r = 2*i+2
      if (l < size && a[l] > a[m]) m = l
      if (r < size && a[r] > a[m]) m = r
      if (m === i) break
      [a[m], a[i]] = [a[i], a[m]]; i = m
    }
  }
  for (let i = (n >> 1) - 1; i >= 0; i--) siftDown(i, n) // 建堆
  for (let end = n - 1; end > 0; end--) { [a[0], a[end]] = [a[end], a[0]]; siftDown(0, end) }
  return a
}

console.log(quickSort([5,2,4,1,3]))        // [1,2,3,4,5]
console.log(quickSortInPlace([5,2,4,1,3])) // [1,2,3,4,5]
console.log(mergeSort([5,2,4,1,3]))        // [1,2,3,4,5]
console.log(heapSort([5,2,4,1,3]))         // [1,2,3,4,5]