JavaScript 中的快速排序

请提供您希望翻译的正文内容，我将把它翻译成简体中文并保留原有的格式。

概述

快速排序是一种广泛使用、快速且优雅的分治排序算法。
基本思路：

1. 选择一个 pivot 元素。
2. 对数组进行划分，使得小于枢轴的元素位于左侧， 大于枢轴的元素位于右侧。
3. 递归地对左侧和右侧子数组应用相同的逻辑。

“快速排序之所以快，是因为它在每一步都大幅度地缩小问题规模。”

功能式（非原地）快速排序

// functional quick sort
const quickSort = (arr) => {
  if (arr.length  {
  const pivot = arr[high];
  let i = low - 1;

  for (let j = low; j  {
  if (low  {
  const pivot = arr[low];
  let i = low - 1;
  let j = high + 1;

  while (true) {
    do { i++; } while (arr[i]  pivot);

    if (i >= j) return j; // boundary index
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
};

const hoarePartition = (arr, low, high) => {
  const pivot = arr[low];
  let i = low - 1;
  let j = high + 1;

  while (true) {
    do { i++; } while (arr[i] < pivot);
    do { j--; } while (arr[j] > pivot);

    if (i >= j) return j; // boundary index
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
};

const quickSortHoare = (arr, low = 0, high = arr.length - 1) => {
  if (low < high) {
    const p = hoarePartition(arr, low, high);
    quickSortHoare(arr, low, p);
    quickSortHoare(arr, p + 1, high);
  }
  return arr;
};

示例

前: [34, 56, 3, 234, 6, 7]（枢轴 = 34）
分区后: [7, 6, 3 | 234, 56, 34] – 返回的分区索引 = 2。

与 Lomuto 的主要区别

• 枢轴 不一定 会停留在最终的排序位置。
• 函数返回的是 边界索引，而不是枢轴索引。
• 交换次数更少 → 通常更快，尤其在存在大量重复元素时。

比较：Lomuto 与 Hoare

复杂度分析

• 空间复杂度
  • 函数式快速排序：O(n)（额外数组）。
  • 原地快速排序：O(log n)（递归栈）。

Summary

• Functional Quick Sort 易于理解，但会使用额外的内存。
• In‑place Quick Sort 使用 Lomuto 或 Hoare 分区方式更适合生产代码。
• Hoare’s scheme 通常交换次数更少，在处理重复值时性能更好，而 Lomuto’s scheme 更简单，并且保证枢轴最终位于正确位置。

选择最符合您环境约束和待排序数据特性的版本。