js sort源码实现
JavaScript sort 源码实现
JavaScript 的 Array.prototype.sort 方法的具体实现依赖于引擎（如 V8、SpiderMonkey 等）。以下是基于 V8 引擎的实现逻辑和关键细节：
排序算法选择
V8 使用混合排序策略（Hybrid Sort），结合快速排序（QuickSort）和插入排序（Insertion Sort）：
- 对于小型数组（长度 ≤ 10），使用插入排序。
- 对于大型数组，使用快速排序，并在递归深度过深时切换为堆排序（HeapSort）以避免最坏情况。
关键步骤
快速排序分区 选取基准值（pivot）并将数组分为小于和大于基准值的两部分：
function partition(arr, low, high, compareFn) {
const pivot = arr[high];
let i = low;
for (let j = low; j < high; j++) {
if (compareFn(arr[j], pivot) < 0) {
[arr[i], arr[j]] = [arr[j], arr[i]]; // Swap
i++;
}
}
[arr[i], arr[high]] = [arr[high], arr[i]]; // Move pivot
return i;
}插入排序 对小规模数组进行优化：
function insertionSort(arr, compareFn, low = 0, high = arr.length - 1) {
for (let i = low + 1; i <= high; i++) {
const key = arr[i];
let j = i - 1;
while (j >= low && compareFn(arr[j], key) > 0) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}比较函数处理
若未提供比较函数，默认将元素转换为字符串并比较 UTF-16 编码：
function defaultCompare(a, b) {
const strA = String(a);
const strB = String(b);
if (strA < strB) return -1;
if (strA > strB) return 1;
return 0;
}稳定性
ES2019 要求 sort 必须稳定（相等元素的原始顺序保留）。V8 通过以下方式实现：
- 对小数组直接使用插入排序（天然稳定）。
- 对大数组使用归并排序（MergeSort）的变体。
性能优化
- 使用三数取中法（Median-of-Three）选择基准值以减少最坏情况。
- 递归深度超过阈值时切换为堆排序。
注意事项
- 原始数组会被修改（原地排序）。
- 稀疏数组的空白元素会被排在末尾。
- 比较函数应返回数值（负数、零、正数），而非布尔值。
