js sort源码实现
JavaScript 的 Array.prototype.sort 方法在 V8 引擎中的实现会根据数组类型和长度选择不同的排序算法，主要分为以下情况：
小数组（长度 ≤ 10）
使用插入排序（Insertion Sort），因为对于小规模数据，插入排序的时间复杂度接近 $O(n)$，且常数项较低。
// 插入排序核心逻辑（简化版）
function insertionSort(arr, compareFn) {
for (let i = 1; i < arr.length; i++) {
const current = arr[i];
let j = i - 1;
while (j >= 0 && compareFn(arr[j], current) > 0) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}大数组（长度 > 10）
使用快速排序（QuickSort）的变体——TimSort（混合排序算法）。V8 会对数组进行以下处理：
- 检查数组是否已接近有序（如升序/降序），若接近有序则使用优化路径。
- 递归执行快速排序，但会限制递归深度，若超过阈值则转为堆排序（HeapSort）避免最坏情况下的 $O(n^2)$ 时间复杂度。
// 快速排序核心分区逻辑（简化版）
function quickSort(arr, compareFn, left, right) {
if (left < right) {
const pivotIndex = partition(arr, compareFn, left, right);
quickSort(arr, compareFn, left, pivotIndex - 1);
quickSort(arr, compareFn, pivotIndex + 1, right);
}
}
function partition(arr, compareFn, left, right) {
const pivot = arr[right];
let i = left;
for (let j = left; j < right; j++) {
if (compareFn(arr[j], pivot) <= 0) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[right]] = [arr[right], arr[i]];
return i;
}特殊优化
- 数字数组：V8 会检测数组元素是否全为数字，若为数字则使用数值比较而非字符串比较，性能显著提升。
- 对象数组：根据
compareFn的复杂度可能触发不同优化路径。
默认比较规则
若未提供 compareFn，元素会被强制转换为字符串后按 Unicode 码点排序：
const defaultCompare = (a, b) => {
const aStr = String(a);
const bStr = String(b);
return aStr < bStr ? -1 : aStr > bStr ? 1 : 0;
};注意事项
- 排序稳定性：ES2019 规定
sort必须稳定（相同元素保持原始顺序），现代浏览器均遵守。 - 稀疏数组：空位（
empty）会被视为undefined参与排序。
