源本科技 | 码上会

logo
源本科技 码上会
一站式数字化转型技能学习平台

JavaScript 排序算法

2026/01/13
14
0

学习目标

  • 理解常见排序算法的基本思想与实现方式

  • 掌握五种核心排序算法：冒泡排序、选择排序、插入排序、归并排序和快速排序

  • 能够分析不同算法的时间复杂度、空间复杂度及适用场景

  • 了解算法的稳定性及其在实际开发中的意义

排序概述

排序是将一组数据按照特定顺序（升序或降序）重新排列的过程。它是计算机科学中最基础且重要的操作之一，广泛应用于数据库查询、搜索优化、数据分析等场景。

示例：

  • 输入：[64, 34, 25, 12, 22, 11, 90]
    输出：[11, 12, 22, 25, 34, 64, 90]

  • 输入：[1, 2, -3, 3, 4, 5]
    输出：[-3, 1, 2, 3, 4, 5]

冒泡排序

Bubble Sort

原理

重复遍历数组，比较相邻元素，若顺序错误则交换。每一轮会将最大（或最小）元素“冒泡”到末尾。

稳定性

  • 稳定：相等元素不会被交换，相对顺序保持不变。

实现

function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n; i++) {
        let swapped = false;
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        if (!swapped) break; // 优化：若某轮无交换，说明已有序
    }
    return arr;
}

// 示例
console.log(bubbleSort([2, 1, 3, 4])); // [1, 2, 3, 4]

复杂度

  • 时间复杂度：O(n²)（最坏 / 平均），O(n)（最好，已有序）

  • 空间复杂度：O(1)（原地排序）

仅适用于小规模数据或教学演示。

选择排序

Selection Sort

原理

  • 每次从未排序部分中选出最小（或最大）元素，放到已排序部分的末尾。

特点

  • 原地排序

  • 不稳定（虽然本实现未显式破坏稳定性，但一般实现可能因交换而失稳）

  • 写操作少（适合写入代价高的存储，如 EEPROM）

实现

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

// 示例
console.log(selectionSort([64, 25, 12, 22, 11])); // [11, 12, 22, 25, 64]

复杂度

  • 时间复杂度：O(n²)（所有情况）

  • 空间复杂度：O(1)

优点：交换次数最多为 n-1 次，比冒泡更少。

插入排序

Insertion Sort

原理

  • 将数组分为“已排序”和“未排序”两部分。逐个取出未排序元素，插入到已排序部分的正确位置。

稳定性

  • 稳定：相等元素不会跨越彼此。

特点

  • 对小规模或近似有序数据效率高

  • 自适应（Adaptive）：输入越有序，性能越好

实现

function insertionSort(arr) {
    const n = arr.length;
    for (let i = 1; i < n; i++) {
        const key = arr[i];
        let j = i - 1;
        // 向右移动大于 key 的元素
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key; // 插入 key
    }
    return arr;
}

// 示例
console.log(insertionSort([12, 11, 13, 5, 6])); // [5, 6, 11, 12, 13]

复杂度

  • 时间复杂度：O(n²)（最坏），O(n)（最好，已有序）

  • 空间复杂度：O(1)

推荐用于小数组（如 < 10 个元素）或作为高级排序的子过程（如快速排序的优化）。

归并排序

Merge Sort

原理

采用分治法（Divide and Conquer）：

  1. 将数组递归地分成两半

  2. 分别对两半排序

  3. 合并两个有序子数组

稳定性

  • 稳定

实现

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) {
    const result = [];
    let i = 0, j = 0;

    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }

    // 添加剩余元素
    return result.concat(left.slice(i), right.slice(j));
}

// 示例
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

复杂度

  • 时间复杂度：O(n log n)（所有情况）

  • 空间复杂度：O(n)（需要额外数组存储合并结果）

适合大数据集，性能稳定，常用于外部排序。

快速排序

Quick Sort，Lomuto 分区

原理

  1. 选择一个基准（此处选最后一个元素）

  2. 将小于基准的元素放左边，大于等于的放右边

  3. 递归排序左右子数组

稳定性

  • 不稳定：分区过程中相等元素可能被重排

实现

简化版，非原地

function quickSort(arr) {
    if (arr.length <= 1) return arr;

    const pivot = arr[arr.length - 1];
    const left = [];
    const right = [];

    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    return [...quickSort(left), pivot, ...quickSort(right)];
}

// 示例
console.log(quickSort([10, 7, 8, 9, 1, 5])); // [1, 5, 7, 8, 9, 10]

注：此实现非原地排序，实际工程中可使用双指针实现原地分区以节省内存。

复杂度

  • 平均时间复杂度：O(n log n)

  • 最坏时间复杂度：O(n²)（如已排序数组，每次 pivot 为最大 / 最小）

  • 空间复杂度：O(n)（递归栈 + 临时数组）

平均性能优秀，是 V8 引擎中 Array.prototype.sort() 对中等规模数组的底层算法之一（结合了插入排序优化）。

算法对比

算法

时间复杂度（平均）

时间复杂度（最坏）

空间复杂度

稳定

适用场景

冒泡排序

O(n²)

O(n²)

O(1)

✅

教学、极小数据

选择排序

O(n²)

O(n²)

O(1)

❌

写操作昂贵的环境

插入排序

O(n²)

O(n²)

O(1)

✅

小数组、近似有序数据

归并排序

O(n log n)

O(n log n)

O(n)

✅

大数据、要求稳定

快速排序

O(n log n)

O(n²)

O(log n)~O(n)

❌

通用高性能排序

实际开发中，优先使用内置 Array.prototype.sort()，它在现代引擎中经过高度优化（如 V8 使用 Timsort 变种）。

思考题

  1. 为什么快速排序在平均情况下比归并排序更快，尽管两者时间复杂度相同？

  2. 如果你需要对一个包含大量重复元素的数组进行排序，并要求算法稳定，你会选择哪种排序算法？为什么？

  3. 尝试将快速排序改写为原地排序版本（不使用额外数组），并分析其空间复杂度变化。