当前位置：首页 > JavaScript

js sort源码实现

2026-03-01 13:52:30JavaScript

JavaScript 的 `Array.prototype.sort` 方法在不同浏览器引擎中的实现可能有所不同，但通常基于高效的排序算法。以下是其核心实现原理和常见优化策略的解析：

排序算法选择

现代 JavaScript 引擎（如 V8、SpiderMonkey）通常结合多种排序算法：

快速排序：用于大多数情况，时间复杂度为 O(n log n)。
插入排序：当数组长度较小时（如 n ≤ 10），因其常数项更优而切换至此。
归并排序：部分引擎对稳定排序有需求时使用（如 Chrome 对非数值类型排序）。

V8 引擎的实现示例

V8 的 sort 实现分为以下几个关键步骤：

1. 预处理

js sort源码实现

检查数组长度，短数组直接使用插入排序。
对数值类型和非数值类型分派不同逻辑。

2. 快速排序核心

选取基准值（pivot）时采用三数取中法（median-of-three）。
递归分区时对小分区切换为插入排序。

// 伪代码示例（非完整实现）
function quickSort(arr, compareFn, left, right) {
  if (right - left <= INSERTION_THRESHOLD) {
    insertionSort(arr, compareFn, left, right);
    return;
  }
  const pivotIndex = medianOfThree(arr, left, right);
  const partitionIndex = partition(arr, compareFn, left, right, pivotIndex);
  quickSort(arr, compareFn, left, partitionIndex - 1);
  quickSort(arr, compareFn, partitionIndex + 1, right);
}

3. 稳定性处理

js sort源码实现

对非数值类型（如对象）采用稳定排序（如归并排序变种）。

比较函数处理

若未提供比较函数，默认将元素转换为字符串后按 Unicode 码点排序：

// 默认比较逻辑
function defaultCompare(a, b) {
  const strA = String(a);
  const strB = String(b);
  return strA < strB ? -1 : strA > strB ? 1 : 0;
}

性能优化点

插入排序阈值：小数组直接使用插入排序减少递归开销。
三数取中法：避免快速排序最坏情况（如已排序数组导致 O(n²)）。
混合排序策略：根据数据类型和长度动态切换算法。

手动实现示例

以下是一个简化的快速排序实现（非引擎源码）：

function sort(arr, compareFn) {
  const compare = compareFn || defaultCompare;
  if (arr.length <= 1) return arr;

  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    compare(arr[i], pivot) < 0 ? left.push(arr[i]) : right.push(arr[i]);
  }

  return [...sort(left, compareFn), pivot, ...sort(right, compareFn)];
}