一、比较类排序

🔵 冒泡排序

• 原理：相邻元素两两比较，每轮将最大元素冒泡到末尾
• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 稳定性：稳定

function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}

🔵 选择排序

• 原理：每次选择最小元素放到已排序序列末尾
• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 稳定性：不稳定

function selectionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let minIndex = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) minIndex = j;
        }
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
    return arr;
}

🔵 插入排序

• 原理：将未排序元素插入已排序序列的合适位置
• 时间复杂度：O(n²)（适合小规模数据）
• 空间复杂度：O(1)
• 稳定性：稳定

function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let current = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > current) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = current;
    }
    return arr;
}

🔴 快速排序

• 原理：分治思想，选取基准元素进行分区排序
• 时间复杂度：O(n log n) 平均，最坏O(n²)
• 空间复杂度：O(log n)
• 稳定性：不稳定

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

🔴 归并排序

归并排序（Merge Sort）是一种基于分治策略的高效排序算法，其核心思想是将数组递归拆分为最小单元后合并，合并过程中完成排序。

• 原理：分治思想，先分解后合并
• 时间复杂度：O(n log n)
• 空间复杂度：O(n)
• 稳定性：稳定

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        left[0] < right[0] ? result.push(left.shift()) : result.push(right.shift());
    }
    return result.concat(left, right);
}

🔴 堆排序

• 原理：构建最大堆，逐个取出堆顶元素
• 时间复杂度：O(n log n)
• 空间复杂度：O(1)
• 稳定性：不稳定

function heapSort(arr) {
    buildMaxHeap(arr);
    for (let i = arr.length - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        heapify(arr, 0, i);
    }
    return arr;
}

function buildMaxHeap(arr) {
    for (let i = Math.floor(arr.length / 2); i >= 0; i--) {
        heapify(arr, i, arr.length);
    }
}

function heapify(arr, i, heapSize) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    if (left < heapSize && arr[left] > arr[largest]) largest = left;
    if (right < heapSize && arr[right] > arr[largest]) largest = right;
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, largest, heapSize);
    }
}

二、非比较类排序

🔵 计数排序
• 适用场景：整数排序，数据范围较小
• 时间复杂度：O(n + k)
• 空间复杂度：O(k)
• 稳定性：稳定

🔵 桶排序
• 适用场景：均匀分布的数据
• 时间复杂度：O(n + k)
• 空间复杂度：O(n + k)

🔵 基数排序
• 适用场景：整数或字符串排序
• 时间复杂度：O(nk)
• 空间复杂度：O(n + k)

三、前端应用场景

1. 表格排序：推荐使用稳定排序（如归并排序）
2. 数据可视化：大数据量时优先选择O(n log n)算法
3. 搜索/过滤功能：结合排序实现高效数据检索
4. 虚拟滚动列表：快速排序适合内存优化

四、浏览器sort方法实现

• V8引擎：混合排序（快速排序 + 插入排序，数组长度>10用快速排序） • Firefox：归并排序 • Safari：底层使用C++实现的归并排序

五、算法选择策略

场景	推荐算法
小规模数据（n ≤ 10）	插入排序
需要稳定排序	归并排序
内存敏感	堆排序
平均性能最佳	快速排序
整数小范围数据	计数排序

六、性能优化技巧

1. 避免在渲染循环中进行排序
2. 使用Web Worker处理大规模数据排序
3. 对稳定排序需求使用Array.prototype.sort()（ES6规范要求稳定）
4. 对对象数组排序时，优先缓存排序键值

掌握这些排序算法有助于应对前端面试中的算法题，并在实际开发中优化数据处理性能。建议重点理解快速排序、归并排序和堆排序的实现原理，这些是前端工程师最常被考察的排序算法。