企业官网建设流程全解析

freeCodeCamp 课程设计解析：用递归分治实现快速排序（Quick Sort）

【免费下载链接】freeCodeCampfreeCodeCamp.org's open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp

本文基于 freeCodeCamp 课程大纲中的 "Implement Quick Sort" 挑战文档展开，系统讲解快速排序的分治思想、pivot 分区策略与递归收敛过程，并逐条剖析该挑战的四组测试断言、种子代码与官方参考实现，帮助你掌握一套不依赖内置.sort()的完整排序算法实现方案，同时了解这道题在 freeCodeCamp 课程体系中的定位与演进。

挑战背景：快速排序在 freeCodeCamp 课程体系中的位置

本挑战的源文档是 Implement Quick Sort，挑战 ID 为587d825a367417b2b2512c89，属于 JavaScript Algorithms and Data Structures 方向的核心练习题。

从课程结构配置看，这道题被组织在algorithms板块中（见 algorithms.json），其挑战顺序为：

1. Find the Symmetric Difference
2. Inventory Update
3. No Repeats Please
4. Pairwise
5. Implement Bubble Sort
6. Implement Selection Sort
7. Implement Insertion Sort
8. Implement Quick Sort（本文主题）
9. Implement Merge Sort
10. Implement Binary Search

可以看到，快速排序被安排在三类基础排序（冒泡、选择、插入）之后、归并排序之前，形成"从 O(n²) 的直观算法逐步过渡到 O(n log n) 高效算法"的递进学习路径。该板块整体隶属于 Coding Interview Prep 超单元（见 coding-interview-prep.json），面向面试算法准备场景。

值得注意的是，同一个挑战 ID 还被复用于新版 JavaScript 课程体系（JS v9）中的多文件编辑器实验题lab-quicksort-js（见 lab-quicksort-js.json 与 javascript-v9.json）。在 JS v9 的algorithms模块中，它排在lab-insertion-sort之后、review-searching-and-sorting-algorithms-js与 quiz 之前，即作为排序算法系列的收官实验题出现。这个复用在后文会进一步展开。

快速排序核心思想：分治、分区与递归收敛

原挑战文档对快速排序给出了如下的标准定义：

快速排序是一种高效的、递归的分治（divide-and-conquer）排序方法。其过程是：在原始数组中选取一个 pivot（枢轴）值，然后将数组分区为两个子数组——一个存放小于 pivot 的值，一个存放大于 pivot 的值；随后对这两个子数组递归调用快速排序算法，并合并两者的结果；这一过程持续进行，直到达到"空数组或单元素数组"的基准情形（base case）并直接返回；递归调用逐层展开（unwinding）后，最终得到有序数组。

拆解这句话可以得到快速排序的四个关键要素：

• 分治（Divide and Conquer）：把"排序整个数组"的问题分解为"排序两个更小的子问题"，这是递归算法成立的前提；
• Pivot 选择：从原数组中取一个值作为枢轴。文档明确指出，虽然 pivot 的选择很重要，但"对本练习而言任意 pivot 均可"，为简化实现，可以直接取首元素或末元素；
• 分区（Partition）：一次遍历把元素划到"小于 pivot"与"大于 pivot"两侧；
• 基准情形：空数组或只有一个元素的数组天然有序，直接返回，递归在此终止。

关于性能，文档给出的结论是：快速排序平均性能为O(n log n)，且实现相对容易，这两个属性使其成为一种流行且实用的排序方法。可以推断，文档中特意强调"pivot 选择很重要"，对应的正是快速排序的经典退化风险：若每次选中的 pivot 恰好是子数组的最大值或最小值（例如对已有序数组固定取首元素），分区将极度不平衡，递归退化为 O(n) 深度的链式调用，平均 O(n log n) 便无法保证。这也是为什么工业实现常采用三数取中、随机化 pivot 等策略。

题目要求与约束

原文档的 Instructions 部分给出了明确的实现规格：

编写函数quickSort，接收一个整数数组作为输入，返回这些整数从小到大排序后的数组。pivot 的选择虽重要，但此处任意 pivot 均可，为简单起见可使用首元素或末元素。

种子代码（seed）非常简洁，只留出了待填写的函数体：

function quickSort(array) { // Only change code below this line return array; // Only change code above this line }

也就是说，题目要求在不修改函数签名的前提下，在quickSort内部完成完整的排序逻辑，且不能借助Array.prototype.sort（这一点由后文的测试强制约束）。

逐条解析四组测试断言

挑战文档的--hints--部分包含四组测试，它们共同界定了"正确实现"的完整验收标准。逐条分析如下：

1.quickSort必须是一个函数

assert(typeof quickSort == 'function');

类型守卫，防止提交者用变量或直接赋值的方式绕开函数式实现。

2. 返回值必须是升序有序数组

function isSorted(a){ for(let i = 0; i < a.length - 1; i++) if(a[i] > a[i + 1]) return false; return true; } assert.isTrue( isSorted( quickSort([ 1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92 ]) ) );

这里自定义了isSorted校验器，通过相邻元素两两比较（a[i] > a[i + 1]即判负）验证"非降序"性质。测试输入是一个 17 个元素的乱序数组，且刻意包含重复值（1、2、43、123各出现两次）——这对实现是一个隐含挑战：如果分区只考虑<和>两个分支而丢弃等于 pivot 的元素，或者把重复元素错误地丢弃，测试就会失败。

3. 结果数组与原数组"仅顺序不同"（成员守恒）

assert.sameMembers( quickSort([ 1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92 ]), [1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92] );

assert.sameMembers要求结果数组与原始数组拥有完全相同的元素集合（含重复计数），不允许丢失或新增任何元素。结合测试 2，"有序 + 成员守恒"两者同时成立，等价于"这是一个正确的排序"。

4. 禁止使用内置.sort()方法

function isBuiltInSortUsed(){ let sortUsed = false; const temp = Array.prototype.sort; Array.prototype.sort = () => sortUsed = true; try { quickSort([0, 1]); } finally { Array.prototype.sort = temp; } return sortUsed; } assert.isFalse(isBuiltInSortUsed());

这是四组测试中最有教学价值的一组。它采用了典型的"猴子补丁"（monkey patching）手法：

1. 先把原始的Array.prototype.sort备份到temp；
2. 用探针函数替换它，一旦被调用就置位sortUsed；
3. 在try/finally中调用被测的quickSort([0, 1])，并在finally中无论是否抛错都恢复原方法，保证测试环境不被污染；
4. 最终断言探针从未被触发。

这个设计把"必须自己实现排序"从口头约束变成了可执行的运行时检测，也提醒实现者：即使只调用一次.sort()（哪怕是隐藏在某处），都会被捕获。

官方参考实现：三路分区的完整解析

文档--solutions--部分给出的官方解法（源文档）如下：

function quickSort(array) { if (array.length === 0) { return []; } else { const pivotValue = array[0]; // Sort elements into three piles let lesser = []; let equal = []; let greater = []; for (let e of array) { if (e < pivotValue) { lesser.push(e); } else if (e > pivotValue) { greater.push(e); } else { equal.push(e); } } return [...quickSort(lesser), ...equal, ...quickSort(greater)]; } }

可以把它拆解为四个步骤：

1. 基准情形：array.length === 0时直接返回[]。这是递归终止条件——因为每次递归处理的子数组都严格小于原数组（pivot 本身被移入equal堆不再参与递归），递归必然终止。
2. 选 pivot：const pivotValue = array[0]，直接取首元素，正是文档 Instructions 中"为简化可取首或末元素"的落地。
3. 三路分区（three-way partition）：单次for...of遍历把全部元素分入lesser/equal/greater三个"堆"（piles）。注意它没有采用经典的"两路分区 + 原地交换"写法，而是构建新数组。从源码结构看，这种写法有两个直接收益：
   • 不修改输入数组（题目未要求原地排序，构建新数组天然避免了副作用）；
   • equal堆专门收集所有等于 pivot 的元素（含 pivot 自身），从而天然、安全地处理了测试数组中大量存在的重复值——这些元素一次分区后便永久归位，不再进入递归。
4. 递归合并：[...quickSort(lesser), ...equal, ...quickSort(greater)]一行完成"递归左半 + 已归位的等值元素 + 递归右半"的拼接。equal堆放在中间且不再递归，正是分治"合并（combine）"步骤的具体形态。

以输入[3, 1, 2]走一遍：pivot 为3，lesser = [1, 2]、equal = [3]、greater = []；返回[...quickSort([1,2]), 3, ...quickSort([])]；继续递归[1,2]得[1, 2]，最终[1, 2, 3]。递归的"展开—收敛"过程与文档中 "The unwinding of the recursive calls return us the sorted array" 的描述完全对应。

复杂度视角

文档给出的结论是平均 O(n log n)。结合上述实现可以进一步说明：分区阶段每层对每个元素做一次常数次比较与一次push，是 O(n)；当 pivot 大致落在中间时，递归深度约为 log(n)，故总量为 O(n log n) 次比较。可以推断，由于本实现固定取首元素且不做随机化，面对已有序/逆序输入时递归深度会退化到 n 级；但在课程练习语境下，这一点被题目"any pivot will do"的说明明确豁免，学习重点放在分治骨架本身而非 pivot 优化策略。

同一挑战的"实验室"变体：从练习题到 Lab

原挑战（challengeType: 1，单文件编辑器）在 JS v9 课程中以challengeType: 26的实验室（lab）形式复用，其多文件版文档位于 lab-quicksort-js/587d825a367417b2b2512c89.md。两个版本的核心描述基本一致（同样强调分治、pivot 分区与平均 O(n log n)），但实验室版本有三处值得注意的差异：

1. 函数名不同：Lab 版要求实现的是quicksort（全小写），而 algorithms 板块的练习题要求quickSort（驼峰）——迁移代码时需注意命名；
2. 测试断言更强：Lab 版用assert.sameOrderedMembers直接对照精确的期望输出[1, 1, 2, 2, 4, 8, 32, 43, 43, 55, 63, 92, 123, 123, 234, 345, 5643]，比练习题版的"自定义isSorted+sameMembers"组合更严格；两者都保留了同一段猴子补丁式的.sort()禁用检测；
3. User Stories 新增显式约束：Lab 版列出三条用户故事，其中第三条 "Thequicksortfunction should recursively call itself to sort the array" 明确要求实现必须递归调用自身，把"分治"从隐含要求变成了验收标准。

此外，lab-quicksort-js是 JS v9algorithms模块倒数第三个板块（其后是 review 与 quiz），承担"排序算法系列收口"的角色；同一 ID 的变体还出现在 Python 侧的lab-quicksort板块（见 lab-quicksort.json），说明 freeCodeCamp 把快速排序视为跨语言（JavaScript / Python）共同的必考算法实验。课程体系内与本题强相关的配套视频资源还包括 quicksort-video.md 与 implementing-quicksort-video.md。

小结

这篇课程文档浓缩了实现快速排序所需的完整知识闭环：

• 算法骨架：pivot 分区 → 递归子数组 → 空/单元素基准情形 → 展开合并，平均 O(n log n)；
• 实现要点：官方解法采用三路分区（lesser/equal/greater）+ 展开运算符拼接，天然处理重复值且不改写入参，pivot 取首元素即可满足题目要求；
• 验收边界：四组测试分别覆盖"是函数、有序、成员守恒、禁用.sort()"，其中猴子补丁式检测是运行时验证"未走捷径"的典范写法；
• 体系定位：该挑战在algorithms板块中承接选择/插入排序、先于归并排序，并以 Lab 变体在 JS v9 与 Python 课程中复用，是 freeCodeCamp 面试准备与新版课程共用的核心算法题。

掌握本文的分区逻辑与测试约束后，你可以直接以官方解法为基线完成提交，也可以尝试把 pivot 换成末元素或随机元素、把三路分区改写为原地交换版本，来进一步验证自己对递归收敛过程的理解。

【免费下载链接】freeCodeCampfreeCodeCamp.org's open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp