深入浅出 JavaScript 快速排序：从原理到高性能实现

2026-02-12 12:16:30 0条评论 2次阅读 0人点赞

在日常的前端开发或算法学习中，我们经常需要对数据进行排序。虽然 JavaScript 提供了内置的 Array.prototype.sort() 方法，但作为一名追求卓越的开发者，理解排序算法背后的原理至关重要。今天，我们将深入探讨计算机科学中最经典、也是最高效的排序算法之一——快速排序（Quick Sort）。

在这篇文章中，我们不仅会学习快速排序的核心思想，还会通过 JavaScript 动手实现它，并探讨如何在实际项目中优化它的性能。无论你是为了准备技术面试，还是为了写出更高效的代码，这篇文章都将为你提供详实的参考。

1 什么是快速排序算法？
2 算法的核心工作原理
3 JavaScript 编程实现
4 代码深度解析
5 优化与进阶实现
6 常见陷阱与解决方案
7 性能分析：为什么要用它？
8 总结与最佳实践

什么是快速排序算法？

快速排序是一种高效的排序算法，其核心思想基于分治法（Divide and Conquer）。简单来说，分治法就是把一个复杂的问题分解成两个或多个相同的子问题，直到这些子问题简单到可以直接求解，最后将子问题的解合并起来得到原问题的解。

在快速排序中，我们的目标是将一个乱序的数组变成有序的。为了做到这一点，我们需要选定一个元素作为“标尺”，我们称之为基准。

基准的选择策略

基准的选择对于算法的效率有直接影响，常见的策略有：

选取第一个元素：实现简单，但在数组本身就有序或接近有序时，性能较差。
选取最后一个元素：这也是我们今天主要演示的方法，逻辑清晰，易于理解。
选取中间元素：通常能较好地避免最坏情况的发生。
随机选择：通过引入随机性，可以降低特定数据分布导致性能下降的概率。

在接下来的讲解中，为了让你更直观地理解分区过程，我们将统一采用最后一个元素作为基准来进行演示。

算法的核心工作原理

快速排序的“快”体现在哪里？它并不像冒泡排序那样每次只能交换相邻的元素，而是通过“跳跃式”的交换，让元素每次移动的距离更大。

它的核心流程可以概括为以下几步：

选择基准：从数组中选出一个元素作为基准。
分区操作：遍历数组，将所有比基准小的元素移到基准的左边，所有比基准大的元素移到基准的右边。经过这一步，基准元素就处于了它在最终有序数组中的正确位置。
递归排序：对基准左侧的子数组和右侧的子数组，重复上述步骤。

让我们通过一个具体的例子来看看分区是如何进行的。假设我们有一个数组 INLINECODEef9434fe，我们选取最后一个元素 INLINECODEd04c0c3e 作为基准。

分区步骤详解

为了让你看清每一步的变化，我们来模拟一下分区函数的执行过程：

步骤 1：初始化与第一次比较

我们将 INLINECODE40732a4f 设为基准。我们从左向右开始遍历。首先，INLINECODE3114eb89 与基准 40 比较。

* INLINECODEfbc75fb3：符合条件。我们将 INLINECODEd46369b0 保留在左侧的“较小区域”。此时数组仍为 [10, 80, ...]。

步骤 2：处理较大元素

接着比较 INLINECODEe29fb2c3 和基准 INLINECODE7389af40。

* INLINECODE3b32ae2c：不符合条件。INLINECODE82a9138b 应该在右侧，所以此时我们不移动它，而是继续向后看。

步骤 3：发现较小元素并交换

接下来比较 INLINECODEac95e2f6 和基准 INLINECODE25d2424d。

* INLINECODEe5dd6471：符合条件！这是一个“较小”的元素，但它现在位于 INLINECODEa378fb8e 的后面。为了维持分区秩序，我们需要把这个较小的元素移到前面去。于是，我们交换 INLINECODE3e55b95c 和 INLINECODE4ff45930。

* 数组变为：[10, 30, 80, 90, 40]。

步骤 4：继续遍历

接下来比较 INLINECODE4323e777 和基准 INLINECODE1069083a。

* 90 > 40：不符合条件。无需操作，保持原位。

步骤 5：基准归位

遍历结束后，所有比 INLINECODE4a6bbac2 小的元素（INLINECODE46acfcd6）都已经排列在数组的前面了。现在，我们需要把基准元素 40 放到它正确的位置（即所有较小元素之后）。

* 我们将 INLINECODE45df9dc5 与 INLINECODEa0f4f603（当前较小区域的下一个位置）进行交换。

* 数组最终变为：[10, 30, 40, 90, 80]。

* 此时，INLINECODE685796ec 已经归位，我们以 INLINECODE32f7ae48 为界，将数组分为了左右两部分。

JavaScript 编程实现

理解了原理后，让我们用代码来实现它。我们将编写两个函数：一个是 INLINECODE8a2c45d2 负责分区，另一个是 INLINECODE9bb30af7 负责递归调用。

示例 1：基础实现（基于最后一个元素）

这是最标准的快速排序写法，推荐你在理解算法时使用。

/**
 * 快速排序的分区函数
 * @param {number[]} arr - 待排序的数组
 * @param {number} low - 起始索引
 * @param {number} high - 结束索引
 * @returns {number} 分区索引（基准元素的位置）
 */
function partition(arr, low, high) {
    // 1. 选择最后一个元素作为基准
    let pivot = arr[high];
    
    // i 用于记录比基准小的元素的存放位置，初始为 low - 1
    let i = low - 1;

    // 2. 遍历从 low 到 high-1 的元素
    for (let j = low; j <= high - 1; j++) {
        // 如果当前元素小于基准
        if (arr[j] = high) return;

    // 获取分区索引
    let pi = partition(arr, low, high);

    // 递归排序基准左边的子数组
    quickSort(arr, low, pi - 1);
    // 递归排序基准右边的子数组
    quickSort(arr, pi + 1, high);
}

// --- 测试代码 ---
let arr = [10, 80, 30, 90, 40];
console.log("原始数组: " + arr);

// 注意：我们需要传入数组的长度减 1 作为 high
quickSort(arr, 0, arr.length - 1);

console.log("排序后数组: " + arr);

输出结果：

原始数组: 10,80,30,90,40
排序后数组: 10,30,40,80,90

代码深度解析

让我们花点时间分析一下上面的代码，这对于你调试和理解至关重要：

变量 INLINECODE8748f514 的作用：在 INLINECODE34aad3e3 函数中，INLINECODE961dde0d 初始化为 INLINECODEf05782a1。你可以把它想象成一个“边界”，所有小于基准的元素都被放在这个边界的左边。每当我们发现一个比基准小的元素，边界 i 就向右扩一位，然后把新发现的小元素交换进来。

为什么是 INLINECODEa10087c1：循环结束后，INLINECODEf596be37 指向的是最后一个比基准小的元素。因此，基准的正确位置自然就是 i + 1。最后这一步交换至关重要，它完成了分区的最后一块拼图。

递归的结束条件：if (low >= high) 是递归的安全网。当子数组只有一个元素或为空时，就不需要再排序了，这防止了栈溢出。

优化与进阶实现

虽然上面的实现逻辑正确，但在实际开发中，我们经常需要处理更复杂的情况。让我们看看如何优化它。

示例 2：随机化基准（优化核心策略）

如果我们总是选择最后一个元素作为基准，当面对一个已经排序好的数组时，快速排序的性能会退化到 O(N²)，这是最坏的情况。为了避免这种情况，我们可以随机选择基准。

// 生成随机数的辅助函数
function getRandomInt(max) {
    return Math.floor(Math.random() * max);
}

function randomPartition(arr, low, high) {
    // 生成 low 到 high 之间的随机索引
    let randomIndex = getRandomInt(high - low + 1) + low;
    
    // 在分区前，先将随机选中的元素与最后一个元素交换
    // 这样后续的逻辑就可以复用之前的 partition 函数了
    [arr[randomIndex], arr[high]] = [arr[high], arr[randomIndex]];
    
    // 调用标准的分区逻辑
    return partition(arr, low, high);
}

function quickSortRandomized(arr, low, high) {
    if (low >= high) return;
    // 使用随机分区函数
    let pi = randomPartition(arr, low, high);
    quickSortRandomized(arr, low, pi - 1);
    quickSortRandomized(arr, pi + 1, high);
}

let arr2 = [10, 7, 8, 9, 1, 5];
// 注意：在实际使用中，可能需要多次运行才能体现随机性的优势
quickSortRandomized(arr2, 0, arr2.length - 1);
console.log("随机基准排序结果: " + arr2);

示例 3：更简洁的“函数式”写法

如果你不喜欢手动管理 INLINECODE9acac989 和 INLINECODE6a7c708f 索引，或者希望代码更具可读性，我们可以利用 JavaScript 的数组方法（如 filter）来写出更符合现代 JS 风格的快速排序。注意：这种写法虽然简洁，但会占用更多内存空间，因为创建了新数组。

function quickSortFunctional(arr) {
    // 递归终止条件
    if (arr.length <= 1) {
        return arr;
    }

    // 1. 选择基准（这里选中间元素）
    const pivotIndex = Math.floor(arr.length / 2);
    // 将基准元素从原数组中取出
    const pivot = arr.splice(pivotIndex, 1)[0];

    // 2. 分区：使用 filter 将元素分为小于、大于和等于基准的三组
    const left = []; // 存放小于基准的元素
    const right = []; // 存放大于基准的元素
    
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    // 3. 递归并合并结果
    // [...left, pivot, ...right] 并不完全准确，应该对 left 和 right 递归排序
    return [...quickSortFunctional(left), pivot, ...quickSortFunctional(right)];
}

let arr3 = [3, 6, 8, 10, 1, 2, 1];
// 这种写法非常优雅，但请注意由于 splice 和创建新数组带来的性能开销
console.log("函数式快速排序: " + quickSortFunctional(arr3));

常见陷阱与解决方案

作为经验丰富的开发者，我们不仅要会写代码，还要知道哪里容易出错。以下是我们在编写快速排序时常遇到的坑：

交换逻辑错误：

问题*：在 INLINECODE28c298b2 函数中，容易混淆 INLINECODEaa6feee1 和 arr[j] 的交换顺序。
解决*：始终记住 INLINECODE6b1f9a2c 是“小数区的边界”，INLINECODE98b133cc 是“当前扫描指针”。交换是为了把 INLINECODEdf27196c 找到的小数扔到 INLINECODE99a956b9 的边界内。

递归栈溢出：

问题*：对于非常巨大的数组，或者当分区极度不平衡时（例如每次只分出一个元素），递归深度过深会导致栈溢出。
解决*：使用“尾递归优化”（虽然 JS 引擎支持不一），或者改用迭代（循环）版的快速排序，利用栈数据结构来模拟递归过程。

时间复杂度退化：

问题*：对于已排序数组，选择第一个或最后一个元素作为基准会导致 O(N²) 的时间复杂度。
解决*：如前所述，使用随机化基准或三数取中法（取头、尾、中三个数的中位数作为基准）。

性能分析：为什么要用它？

我们来总结一下快速排序的性能特点，这能帮助你在实际场景中做选择。

时间复杂度：

* 平均情况：O(N log N)。这是大多数情况下的表现，非常高效。

* 最坏情况：O(N²)。发生在数组已经有序且每次选择最端点元素时。通过随机化可以极大降低此概率。

* 最好情况：O(N log N)。每次基准都正好将数组平分。

空间复杂度：

* O(log N)。这是由于递归调用栈所占用的空间。

稳定性：

* 快速排序是不稳定的排序算法。这意味着如果有两个相同的数字（比如两个 10），排序后它们的相对顺序可能会改变。如果需要稳定性，归并排序可能是更好的选择。

总结与最佳实践

在这篇文章中，我们深入探讨了快速排序算法。从核心的“分治”思想，到具体的分区步骤，再到 JavaScript 的多种实现方式，我们已经掌握了这项强大的工具。

你可以把今天学到的知识应用到以下场景：

大数据集排序：对于内存中的中型到大型数据集，快速排序通常是最高效的原地排序算法。
二分查找的前置步骤：快速排序将数据整理有序后，我们就可以快速应用二分查找算法。
构建更复杂的系统：在很多高级算法中，排序都是预处理的关键一步。

写在最后

虽然 JavaScript 引擎（如 V8）内置的 sort 方法通常已经高度优化（在不同场景下可能会混合使用快速排序、归并排序和插入排序），但理解快速排序的底层逻辑，能让你对数据结构和算法有更深刻的直觉。

当你下次面对一个需要优化的性能瓶颈时，或者在手写代码进行实时数据处理时，希望你能自信地写出属于自己的 quickSort 函数。 Happy Coding！

投稿给我们	如何建站？
vps是什么？	如何安装宝塔？
如何通过博客赚钱？	便宜wordpress托管方案
免费wordpress主题	这些都是免费方案

豆丁博客