JavaScript中的排序算法与Array.prototype.sort实现

描述
JavaScript中的Array.prototype.sort()方法是用于对数组元素进行排序的内置方法。虽然它使用方便，但其底层实现和排序算法特性需要深入理解。不同的JavaScript引擎使用不同的排序算法，但都遵循ECMAScript规范对稳定性和比较逻辑的要求。

排序基础概念

1. 排序算法分类：比较排序（冒泡、插入、快速排序等）和非比较排序
2. 稳定性：相等元素的相对位置在排序后保持不变
3. 时间复杂度：最佳、平均和最坏情况下的性能表现

Array.prototype.sort的默认行为

// 默认将元素转换为字符串后按Unicode码点排序
const arr = [10, 2, 1];
arr.sort(); // 结果：[1, 10, 2]（不是数值顺序）

比较函数的实现原理

1. 比较函数接收两个参数a和b
2. 返回负数表示a应该排在b前面
3. 返回正数表示a应该排在b后面
4. 返回0表示相对位置不变

// 数值升序排序
arr.sort((a, b) => a - b);

// 字符串长度排序
const strArr = ['a', 'ccc', 'bb'];
strArr.sort((a, b) => a.length - b.length);

V8引擎的排序实现（以Chrome为例）

1. 数组长度≤10：使用插入排序（稳定且对小数组高效）
2. 数组长度＞10：使用快速排序的变体（不稳定但平均性能好）
3. 现代V8使用TimSort（混合插入和归并排序的稳定算法）

手写快速排序实现

function quickSort(arr, compareFn = (a, b) => a - b) {
    if (arr.length <= 1) return arr;
    
    const pivot = arr[Math.floor(arr.length / 2)];
    const left = [];
    const right = [];
    const equal = [];
    
    for (const item of arr) {
        const cmp = compareFn(item, pivot);
        if (cmp < 0) left.push(item);
        else if (cmp > 0) right.push(item);
        else equal.push(item);
    }
    
    return [...quickSort(left, compareFn), ...equal, ...quickSort(right, compareFn)];
}

稳定排序的实现技巧

// 通过保留原始索引实现稳定排序
function stableSort(arr, compareFn) {
    const indexedArr = arr.map((value, index) => ({ value, index }));
    
    indexedArr.sort((a, b) => {
        const cmp = compareFn(a.value, b.value);
        // 如果值相等，按原始索引排序保证稳定性
        return cmp !== 0 ? cmp : a.index - b.index;
    });
    
    return indexedArr.map(item => item.value);
}

性能优化实践

1. 避免在比较函数中创建新对象
2. 对预排序数组使用适应性算法
3. 对大数组考虑使用Web Workers并行处理

// 优化比较函数：缓存对象属性访问
const objects = [{x: 5}, {x: 2}, {x: 8}];
objects.sort((a, b) => {
    // 避免重复属性访问
    const aX = a.x;
    const bX = b.x;
    return aX - bX;
});

实际应用场景

1. 表格数据的多列排序
2. 虚拟列表的渲染优化
3. 搜索结果的相关性排序

通过理解排序算法的底层原理，可以更好地使用Array.prototype.sort()方法，并在需要时实现自定义的高效排序解决方案。