freeCodeCamp 课程源码解读：用 Markdown 挑战文件实现 Insertion Sort（插入排序）

freeCodeCamp 课程源码解读：用 Markdown 挑战文件实现 Insertion 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 课程仓库中 Algorithms 模块的官方挑战文件 Implement Insertion Sort，完整讲解插入排序的算法思想、题目要求与测试用例，并结合仓库中的挑战解析管线（challenge parser）、挑战类型定义与课程结构配置，还原这道题从 Markdown 源文件到在线编辑器可运行挑战的完整实现链路。读完你可以掌握：插入排序的逐步执行过程、官方参考解法与替代写法、以及该仓库中挑战文件的结构与校验机制。

挑战文件在课程体系中的位置

这道挑战位于课程的algorithms区块（block）中。区块结构由 algorithms.json 定义，其中challengeOrder字段以挑战id和标题列出了 10 道挑战的排列顺序，插入排序排在第 7 位：

{ "isUpcomingChange": false, "dashedName": "algorithms", "helpCategory": "JavaScript", "challengeOrder": [ { "id": "a3f503de51cf954ede28891d", "title": "Find the Symmetric Difference" }, { "id": "a56138aff60341a09ed6c480", "title": "Inventory Update" }, { "id": "a7bf700cd123b9a54eef01d5", "title": "No Repeats Please" }, { "id": "a3f503de51cfab748ff001aa", "title": "Pairwise" }, { "id": "8d5123c8c441eddfaeb5bdef", "title": "Implement Bubble Sort" }, { "id": "587d8259367417b2b2512c85", "title": "Implement Selection Sort" }, { "id": "587d8259367417b2b2512c86", "title": "Implement Insertion Sort" }, { "id": "587d825a367417b2b2512c89", "title": "Implement Quick Sort" }, { "id": "587d825c367417b2b2512c8f", "title": "Implement Merge Sort" }, { "id": "61abc7ebf3029b56226de5b6", "title": "Implement Binary Search" } ], "blockLayout": "legacy-challenge-list" }

可以观察到该区块是"先集合运算、后排序算法"的编排：冒泡排序（Bubble Sort）→ 选择排序（Selection Sort）→ **插入排序（Insertion Sort，本篇主角）**→ 快排（Quick Sort）→ 归并排序（Merge Sort）→ 二分查找（Binary Search），难度由低到高递进。该区块还声明了blockLayout: "legacy-challenge-list"，即使用经典挑战列表布局渲染。

挑战文件结构：一份 Markdown 定义了整道题

挑战源文件 587d8259367417b2b2512c86.md 采用 frontmatter + 约定标记（# --xxx--）的 Markdown 结构。其 frontmatter 只有 4 个字段，却能唯一定位挑战并声明类型：

--- id: 587d8259367417b2b2512c86 title: Implement Insertion Sort challengeType: 1 forumTopicId: 301613 dashedName: implement-insertion-sort ---

各字段含义如下：

• id：MongoDB ObjectId 风格的唯一标识，与结构文件algorithms.json中challengeOrder引用的 id 一一对应，同时也是文件名本身；
• title：在线课程侧边栏中显示的挑战标题；
• challengeType: 1：根据 challenge-types.ts 中的定义，1对应js类型（普通 JavaScript 编程题）。该文件同时给出了视图类型映射viewTypes[js] = 'classic'（渲染经典编辑器视图）和提交方式映射submitTypes[js] = 'tests'（提交时运行断言测试），也就是说这道题的"完成判定"完全由题目内嵌的断言测试决定；
• dashedName：URL 中的短横线命名（slug），符合 challenge-schema.js 中slugRE（^[a-z0-9-]+$）的正则约束。

文件正文按以下约定分区：

这一约定并非松散规范，而是被解析管线强校验的：challenge-parser 基于unified/remark构建了处理链，其中validateSections插件会先验证所有分区标记，再由addTests、addSeed、addSolution、addText等插件把各分区内容抽取为挑战对象字段：

// tools/challenge-parser/parser/index.js（节选） const processor = unified() .use(remark) .use(tableAndStrikeThrough) .use(directive) .use(frontmatter, ['yaml']) .use(addFrontmatter) .use(validateSections) // 先校验所有 --xxx-- 分区标记 .use(replaceImports) .use(addSeed) // 提取 --seed-- 中的 starter code .use(addSolution) // 提取 --solutions-- 中的参考解法 // ... .use(addTests) // 提取 --hints-- 中的断言测试 .use(addText, ['description', 'instructions', 'notes', 'explanation', 'transcript']);

从源码结构看，一道挑战的完整对象还需满足 challenge-schema.js 中 Joi 定义的 schema（tests必填、solutions为"文件的数组的数组"等），解析产物会经过这一层结构校验后才进入课程数据。

题目描述：插入排序是如何工作的

原题 description 部分的核心陈述（已完整保留其技术内容）：

The next sorting method we'll look at is insertion sort. This method works by building up a sorted array at the beginning of the list. It begins the sorted array with the first element. Then it inspects the next element and swaps it backwards into the sorted array until it is in sorted position. It continues iterating through the list and swapping new items backwards into the sorted portion until it reaches the end. This algorithm has quadratic time complexity in the average and worst cases.

翻译成要点：插入排序通过在列表前部维护一个已排序子数组来完成排序：

1. 以第一个元素作为长度为 1 的"已排序区"；
2. 取出下一个元素，把它与已排序区从后往前逐个比较并后移，直到找到它应插入的位置；
3. 重复该过程直到遍历完整个数组。

题目对算法复杂度的官方定性是：平均与最坏情况下时间复杂度均为二次方（O(n²)）。这一点与同区块的冒泡排序描述（"for average and worst cases has quadratic time complexity"）一致。

官方要求（Instructions）：编写函数insertionSort，接收一个整数数组，返回按从小到大排序后的整数数组：

Write a functioninsertionSortwhich takes an array of integers as input and returns an array of these integers in sorted order from least to greatest.

完整测试用例解析：题目内嵌了 4 个断言

# --hints--分区既是"卡住时的提示"，也是判题的测试集合。原题包含 4 组断言，下面逐一讲解其设计意图。

测试 1：函数存在性

insertionSort should be a function. assert.isFunction(insertionSort);

最基础的类型检查，确保用户定义了一个可调用对象而非常量。

测试 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( insertionSort([ 1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92 ]) ) );

测试先定义了一个辅助函数isSorted：线性扫描相邻元素，只要出现a[i] > a[i+1]即判定未排序。它把 17 个元素、含大量"逆序对"和重复值（两个123、两个43、两个2、两个1）的数组作为输入——重复值这一细节很关键：插入排序的正确实现必须用>（严格大于）而非>=作为比较条件，否则等值元素的移动行为虽然不违反排序正确性，但这里也提醒读者该数组同时考察了"稳定性"无关路径下的边界处理。

测试 3：成员守恒（不增删元素）

assert.sameMembers( insertionSort([ 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] );

sameMembers校验结果与输入具有完全相同的多重集（multiset）——排序只允许改变顺序，不允许丢失或新增任何元素（含重复计数）。这与测试 2 组合起来，恰好完整刻画了"排序"的数学定义：有序 + 成员不变。

测试 4：小数组精确结果 + 禁用内置 sort

// 精确结果断言 assert.deepEqual(insertionSort([5, 4, 33, 2, 8]), [2, 4, 5, 8, 33]) // 禁止使用内置 .sort() function isBuiltInSortUsed(){ let sortUsed = false; const temp = Array.prototype.sort; Array.prototype.sort = () => sortUsed = true; try { insertionSort([0, 1]); } finally { Array.prototype.sort = temp; } return sortUsed; } assert.isFalse(isBuiltInSortUsed());

前一条用deepEqual对 5 元素小数组做精确比对；后一条是这道题最有教学价值的技巧——猴子补丁（monkey patching）：临时替换Array.prototype.sort为一个只置位标志的桩函数，运行被检测函数后再finally恢复原型，以此捕获"偷偷调用内置排序"的行为。这个 try/finally 保证即使用户函数抛错，原型链也能被还原，不污染后续测试。它说明课程的测试设计在防作弊上是有刻意的工程细节的。

初始代码（Seed）与官方参考解法

# --seed--分区提供给用户编辑器的起点代码只有三行：

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

注释限定了允许修改的区域（editableRegionBoundaries机制在 schema 的fileJoi中有对应字段定义），防止用户改写函数签名。

原题# --solutions--分区给出的官方参考解法：

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

逐行拆解这段实现：

1. 外层for循环：currentIndex从0遍历到array.length - 1。循环进行到currentIndex时，array[0..currentIndex-1]已经是有序的，array[currentIndex]就是待插入的"新元素"。currentIndex = 0时内层循环一次都不执行，等价于"以第一个元素初始化已排序区"，与题目描述完全吻合。
2. let current = array[currentIndex]：先把待插入元素暂存。之所以要暂存，是因为下面的后移操作会覆盖它自己的位置——这是插入排序"先搬砖、再腾位、最后落位"三步曲的第一步。
3. while (j > -1 && array[j] > current)：从j = currentIndex - 1开始向头部扫描。两个条件缺一不可：
   • j > -1：防止越界，保证扫描不会越过数组头；
   • array[j] > current：只把严格大于current的元素后移。由于此处是>而不是>=，等值元素会停在原地，这正是上面测试 2 中重复值能通过的原因之一，也让该实现是稳定排序。
4. array[j + 1] = array[j]; j--;：把比current大的元素整体后移一格，为current腾出空间。注意它不是"交换"而是"整体平移"，所以每轮内层循环最多只需一次赋值而非三次（交换的两个赋值）。
5. array[j + 1] = current;：while退出时，j指向最后一个不大于current的元素（或-1），因此j + 1就是current的最终插入点，落位完成。

以测试 4 的输入[5, 4, 33, 2, 8]走一遍：

复杂度分析：外层固定 n 次；内层每次最多后移currentIndex个元素。最好情况（输入已有序）内层while每轮 0 次赋值，总比较 O(n)；最坏情况（逆序）每轮移动约 i 次，总移动次数为1+2+…+(n-1) = n(n-1)/2，即 O(n²)——与题目"平均和最坏二次方"的描述严格对应。空间上只用了current、j两个变量，是 O(1) 原地排序。

等价的"交换式"写法：读者也可以写成更直观的形式，语义完全一致且同样能过全部测试：

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

它用"相邻交换"代替"整体平移"，每轮交换次数相同（都是该元素越过的逆序元素个数），只是常量开销略大。两种写法共同体现了插入排序的核心不变量：每一轮外层迭代结束后，前 i+1 个元素构成有序前缀。

挑战类型如何驱动判题行为

frontmatter 中的challengeType: 1不只是元数据，它决定整套运行机制。在 challenge-types.ts 中：

const html = 0; const js = 1; // ← 本挑战 const backend = 2; // ... export const challengeTypes = { html, js, backend, /* ... */ }; export const viewTypes = { [html]: 'classic', [js]: 'classic', // → 渲染经典单文件 JS 编辑器 // ... }; export const submitTypes = { [html]: 'tests', [js]: 'tests', // → 提交 = 运行 # --hints-- 中的断言 // ... };

由此可以串起完整链路：Markdown 文件（描述/提示/seed/solution 四分区）→challenge-parser 管线（validateSections校验标记，addTests/addSeed/addSolution抽取内容）→Joi schema 校验（tests、solutions、id、dashedName等必填约束）→运行期（viewTypes.js = 'classic'决定用经典编辑器加载seed代码，submitTypes.js = 'tests'决定点击"Run Tests"时执行hints分区里那 4 组断言）。同一机制也适用于同区块的 Implement Bubble Sort、Implement Quick Sort、Implement Merge Sort 等姊妹挑战——它们的测试结构（isFunction→isSorted→sameMembers→ 内置 sort 检测）几乎逐字复用，只更换函数名与参考解法。

小结：从一道 O(n²) 排序题学到的三件事

1. 算法层面：插入排序靠"有序前缀 + 后移落位"两步不变量工作，O(1) 原地、稳定，平均/最坏 O(n²)；参考解法的精髓在于用一次暂存加while平移代替交换式比较，以及>与>=的选择对稳定性的影响。
2. 工程层面：禁用内置.sort()的猴子补丁测试（try/finally 还原原型）展示了断言驱动教学场景中"防作弊测试"的可复制写法。
3. 课程管线层面：一个仅含 5 个 frontmatter 字段的 Markdown 文件，经由tools/challenge-parser的 remark 插件链与 Joi schema，最终决定了编辑器视图、seed 代码区域和判题断言——理解challengeType到viewTypes/submitTypes的映射，是读懂 freeCodeCamp 全部编程题挑战运行机制的钥匙。

关键文件索引：

• 挑战源文件：curriculum/challenges/english/blocks/algorithms/587d8259367417b2b2512c86.md
• 区块结构与顺序：curriculum/structure/blocks/algorithms.json
• 挑战解析管线：tools/challenge-parser/parser/index.js
• 挑战对象 schema：curriculum/schema/challenge-schema.js
• 挑战类型与视图/提交映射：packages/shared/src/config/challenge-types.ts

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