JavaScript中的排序算法有哪些？如何实现快速排序或归并排序

JavaScript中常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等，其中快速排序和归并排序因为时间复杂度表现优秀，是实际开发中使用频率较高的两种高效排序算法。

常见排序算法分类

按照排序的实现逻辑和效率，JavaScript中的排序算法可以分为以下几类：

• 简单排序：冒泡排序、选择排序、插入排序，时间复杂度多为O(n²)，适合小规模数据排序
• 高效排序：快速排序、归并排序、堆排序，平均时间复杂度多为O(n log n)，适合大规模数据排序
• 特殊场景排序：计数排序、基数排序，适合特定范围的整数排序，时间复杂度可以达到O(n)

快速排序的实现

快速排序的核心思想是选择一个基准元素，将数组分为小于基准和大于基准的两部分，再对两部分递归执行相同操作，直到子数组长度为1。具体实现代码如下：

// 快速排序实现函数
function quickSort(arr) {
    // 如果数组长度小于等于1，直接返回
    if (arr.length <= 1) {
        return arr;
    }
    // 选择中间元素作为基准
    const pivotIndex = Math.floor(arr.length / 2);
    const pivot = arr[pivotIndex];
    // 定义存放小于、等于、大于基准的数组
    const left = [];
    const equal = [];
    const right = [];
    // 遍历数组，按大小分到对应数组
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else if (arr[i] === pivot) {
            equal.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    // 递归处理左右数组，拼接结果
    return [...quickSort(left), ...equal, ...quickSort(right)];
}

// 测试示例
const testArr = [3, 6, 2, 8, 1, 5, 9, 4, 7];
console.log(quickSort(testArr)); // 输出 [1,2,3,4,5,6,7,8,9]

归并排序的实现

归并排序采用分治思想，先将数组拆分为最小的子数组，再将相邻的子数组有序合并，直到合并为完整的有序数组。具体实现代码如下：

// 归并排序实现函数
function mergeSort(arr) {
    // 如果数组长度小于等于1，直接返回
    if (arr.length <= 1) {
        return arr;
    }
    // 拆分数组为左右两部分
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
    // 递归拆分并合并
    return merge(mergeSort(left), mergeSort(right));
}

// 合并两个有序数组的函数
function merge(left, right) {
    const result = [];
    let i = 0;
    let j = 0;
    // 遍历两个数组，将较小的元素先放入结果数组
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i]);
            i++;
        } else {
            result.push(right[j]);
            j++;
        }
    }
    // 将剩余元素追加到结果数组
    return result.concat(left.slice(i)).concat(right.slice(j));
}

// 测试示例
const testArr2 = [5, 3, 8, 1, 7, 2, 6, 4, 9];
console.log(mergeSort(testArr2)); // 输出 [1,2,3,4,5,6,7,8,9]

两种排序算法的对比

快速排序和归并排序的特点对比如下：

如果需要稳定的排序结果且内存空间充足，优先选择归并排序；如果更看重空间占用且数据分布较为随机，快速排序是更好的选择。实际开发中可以根据具体场景灵活选用这两种算法。

JavaScript快速排序归并排序排序算法修改时间：2026-07-22 02:15:23