三路快排处理重复键

功能说明

该示例实现三路快速排序，把数组分成小于基准、等于基准、大于基准三段。与普通二路快排不同，所有等于基准的元素会在一次分区后落到最终位置，因此面对大量重复值不会退化成平方复杂度。函数原地排序并返回同一个数组，适合给标签、状态码或枚举值排序。

关键代码

sortRange 使用 less、index、greater 三个指针完成荷兰国旗分区。比较结果小于 0 时把元素换到 less 并同时推进两个指针，大于 0 时把元素换到 greater 且不推进 index，等于 0 时只推进 index。分区后先递归较小的一侧，再通过循环处理较大的一侧，减少递归深度。基准值在分区前取出，避免交换后基准位置漂移。

使用注意

该实现不稳定，相等元素的原始顺序不保证保留。比较器必须返回一致的负数、零、正数，不要混用字符串与数字。数组会被直接修改，如果需要保留原数组应先复制。遇到 NaN 或不可比较值时结果不可预期，调用方应在传入前清洗数据。递归改循环只优化了栈深度，时间复杂度仍是平均 O(n log n)。

验证方式

用重复三次的单词数组断言分区后三个 alpha 连续且顺序正确。测试已排序、逆序、全部相等、空数组与单元素数组。用降序比较器验证结果反向。再生成随机数组，与 Array.prototype.sort 的结果逐项比较，确认原地排序没有丢失或复制元素。

代码示例

export function quickSort(items, compare = defaultCompare) {
  if (!Array.isArray(items)) throw new TypeError("items must be an array");
  if (typeof compare !== "function") throw new TypeError("compare must be a function");
  sortRange(items, 0, items.length - 1, compare);
  return items;
}

function sortRange(items, low, high, compare) {
  while (low < high) {
    const pivot = items[low + ((high - low) >>> 1)];
    let less = low;
    let index = low;
    let greater = high;
    while (index <= greater) {
      const order = compare(items[index], pivot);
      if (order < 0) {
        swap(items, less, index);
        less += 1;
        index += 1;
      } else if (order > 0) {
        swap(items, index, greater);
        greater -= 1;
      } else {
        index += 1;
      }
    }
    if (less - low < high - greater) {
      sortRange(items, low, less - 1, compare);
      low = greater + 1;
    } else {
      sortRange(items, greater + 1, high, compare);
      high = less - 1;
    }
  }
}

function swap(items, left, right) {
  const temporary = items[left];
  items[left] = items[right];
  items[right] = temporary;
}

function defaultCompare(left, right) {
  return left < right ? -1 : left > right ? 1 : 0;
}

const words = ["delta", "alpha", "charlie", "alpha", "bravo", "alpha"];
console.log(quickSort([...words]));
console.log(quickSort([...words], (left, right) => right.localeCompare(left)));