在 freeCodeCamp 课程中实现归并排序：divide-and-conquer 策略的完整实践

在 freeCodeCamp 课程中实现归并排序divide-and-conquer 策略的完整实践【免费下载链接】freeCodeCampfreeCodeCamp.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCampmerge sort归并排序是与 quick sort 并列的两种经典中间难度排序算法之一采用分治divide-and-conquer递归策略稳定达到 O(nlog(n)) 的时间复杂度。freeCodeCamp 的 coding-interview-prep 课程在 algorithms 区块中设置了名为 Implement Merge Sort 的编程挑战要求学习者在不使用内置.sort()方法的前提下手写一个mergeSort函数完成整数数组的升序排序。读完本文你将掌握归并排序先拆分、后合并的完整执行模型理解merge与mergeSort两个函数如何分工协作并能对照课程的 4 项断言测试排序正确性、元素完整性、禁用内置排序写出可复现的参考实现。挑战在课程体系中的位置从课程结构看该挑战文件 587d825c367417b2b2512c8f.md 归属于coding-interview-prep超块下的algorithms区块。根据 超块配置该超块共包含algorithms、data-structures、take-home-projects三个区块而 区块配置中列出的 10 道挑战里排序算法部分依次为顺序挑战文件1Implement Bubble Sort8d5123c8c441eddfaeb5bdef.md2Implement Selection Sort587d8259367417b2b2512c85.md3Implement Insertion Sort587d8259367417b2b2512c86.md4Implement Quick Sort587d825a367417b2b2512c89.md5Implement Merge Sort本挑战587d825c367417b2b2512c8f.md6Implement Binary Search61abc7ebf3029b56226de5b6.md也就是说学习者先完成了三个 O(n²) 级别的初阶排序和一个 O(nlog(n)) 的快排才会遇到本挑战。这与课程文档的定位一致——merge sort 被描述为另一个常见的中间难度排序算法another common intermediate sorting algorithm且是课程明确覆盖的最后一个排序算法文档同时预告后续在树形数据结构部分还会介绍依赖二叉堆的 heap sort。算法核心思想为什么两个有序数组容易合并课程文档对归并排序原理的表述是合并两个已经各自有序的数组相对容易但输入只是一个未排序的数组如何从它出发得到两个有序数组答案就是递归拆分——不断把原数组对半切分直到到达单元素数组这一基准情形base case。单元素数组天然有序于是可以开始自底向上合并合并过程逐层展开unwind拆分阶段产生的递归调用最终产出包含全部元素的有序数组。由此可以概括出文档给出的两步模型1递归地将输入数组一分为二直到产生只含一个元素的子数组。2将每个有序子数组两两合并产出最终排序数组。从源码结构看这种先全部拆到叶子、再逐层合并的写法正是分治策略中自顶向下递归 自底向上归并的标准形态递归树的深度为 log(n)每一层所有合并操作的总工作量为 O(n)合计得到 O(nlog(n))。文档也基于此给出该算法的时间复杂度结论O(nlog(n))并指出归并排序之所以流行正是因为它性能良好且相对容易实现。任务要求两个函数的职责划分文档给出的指令Instructions原文要求编写一个mergeSort函数接收整数数组返回按从最小到最大排序后的数组。文档特别推荐了一种实现方式merge函数负责合并两个已排序的数组mergeSort函数负责递归拆分产生单元素数组并喂给merge。编辑器的初始种子代码seed是function mergeSort(array) { // Only change code below this line return array; // Only change code above this line }学习者只需替换中间的两行注释之间的逻辑。值得注意的是课程允许在mergeSort函数体内声明嵌套的merge辅助函数——参考解法正是这种组织方式。参考解法逐行解析挑战文档内置的--solutions--段提供了官方参考解法这里结合其内嵌注释做逐段解析function mergeSort(array) { if (array.length 1) { return array; } else { const splitIndex Math.floor(array.length / 2); return merge( mergeSort(array.slice(0, splitIndex)), mergeSort(array.slice(splitIndex)) ); } // Merge two sorted arrays function merge(array1, array2) { let merged []; while (array1.length array2.length) { if (array1[0] array2[0]) { merged.push(array1.shift()); } else if (array1[0] array2[0]) { merged.push(array2.shift()); } else { merged.push(array1.shift(), array2.shift()); } } // After looping ends, one array is empty, and other array contains only // values greater than all values in merged return [...merged, ...array1, ...array2]; } } mergeSort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]);递归拆分部分基准情形array.length 1时直接返回对应上文单元素数组天然有序的论证。拆分点Math.floor(array.length / 2)向下取整保证左半部分可能比右半部分短一个元素如长度为 5 时左 2 右 3但两侧都非空递归必然终止。array.slice(0, splitIndex)与array.slice(splitIndex)生成两个副本这是非破坏性操作——课程测试恰好依赖这一点见下文assert.sameMembers验证元素未被修改。合并部分merge(array1, array2)的循环不变式是两个输入数组始终各自有序且头部元素分别是其中的最小值。每次比较array1[0]与array2[0]把较小者shift()出来推入merged。相等分支merged.push(array1.shift(), array2.shift())一次性弹出两个元素这是处理重复值本测试数组中123、43、2、1均出现两次的关键等价于把相等的两个元素都纳入结果。循环结束后两个数组中必有一个已空另一个的剩余元素大于merged中所有值因为此前每一轮弹出的都是当前双头最小值。因此直接展开拼接[...merged, ...array1, ...array2]即可无需再排序。从实现细节看shift()是 O(n) 操作因此这段参考解法中merge的理论代价高于用双指针索引遍历的 O(n) 版本但课程目标是验证算法结构理解而非极致性能这一写法以可读性优先。四项断言测试与约束条件课程通过 4 条断言来验证实现逐条拆解可得到完整的验收标准1.mergeSort必须是函数assert.isFunction(mergeSort);2. 返回值必须是从最小到最大的有序数组文档提供了一个通用的isSorted校验器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( mergeSort([ 1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92 ]) ) );3. 元素构成不得改变只能重排不能增删assert.sameMembers( mergeSort([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以多重集multiset语义比较两个数组元素及出现次数必须完全一致仅顺序可以不同。这直接呼应了文档指令中except for order除顺序外不变的约束——注意测试数据中刻意包含重复值因此用Set之类的去重手段去凑答案会在这里失败。4. 禁止使用内置.sort()function isBuiltInSortUsed(){ let sortUsed false; const temp Array.prototype.sort; Array.prototype.sort () sortUsed true; try { mergeSort([0, 1]); } finally { Array.prototype.sort temp; } return sortUsed; } assert.isFalse(isBuiltInSortUsed());这条断言通过猴子补丁monkey patch手段将Array.prototype.sort替换为置位标记函数调用被测代码后在finally中恢复原型。只要mergeSort内部任何位置包括借助其他库间接调用触碰了.sort断言即失败。这保证了学习者真正实现了排序逻辑而不是调一下内置方法。此外测试使用的 17 元素数组[1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92]与前一挑战 Implement Quick Sort 中的断言数据完全相同从源码结构看课程的排序算法挑战共享同一组基准测试数据便于横向对比不同算法实现的正确性。递归展开示例以小型数组[3, 1, 4, 2]为例可以直观看到文档所述拆到单元素再逐层合并的过程[3, 1, 4, 2] / \ [3, 1] [4, 2] / \ / \ [3] [1] [4] [2] - 基准情形单元素天然有序 \ / \ / [1, 3] [2, 4] - 合并两个有序单元素 \ / [1, 2, 3, 4] - 合并两个有序子数组每一层合并都只依赖两个输入各自有序这一前提与上文merge函数的循环不变式一一对应。常见实现细节与易错点基于文档解法与断言设计可以归纳出几个容易踩坑的地方拆分边界Math.floor(array.length / 2)之后必须保证左右两部分都不为空否则递归不会终止。对于长度为 2 的数组切分结果为[a]和[b]正好落入基准情形。相等元素的处理参考解法在array1[0] array2[0]时同时弹出两个元素。如果只弹出其一另一相等元素会留在数组中等待下一轮比较结果依然正确这是归并排序稳定性的体现之一但若写成else分支只处理了而漏掉逻辑上依赖数组自然结束容易引发困惑。不要原地修改输入断言 3 的sameMembers虽只比较多重集成员但slice生成副本的写法天然满足不改变入参的整洁语义。shift()的性能代价如上所述频繁shift会使合并过程退化为 O(n²) 级别。若追求效率可改用两个索引指针遍历输入数组把 O(n) 的合并恢复到线性复杂度——这是课程未要求但值得了解的优化方向。小结本挑战以拆分到单元素 两两有序合并两步模型把归并排序的递归结构讲得非常收敛mergeSort负责自顶向下的分裂并触发递归merge负责自底向上的线性归并两者共同实现了文档所述的 O(nlog(n)) 排序。对照课程的四项断言——函数存在、升序输出、元素多重集不变、禁用内置.sort——可以清楚地界定合格的归并排序实现的边界。完成该挑战后学习者即已走完algorithms区块中从冒泡、选择、插入、快排到归并的全部排序算法序列下一步则是 Implement Binary Search在有序数组上做 O(log n) 查找与本文的排序产出正好衔接。【免费下载链接】freeCodeCampfreeCodeCamp.orgs open-source codebase and curriculum. Learn math, programming, and computer science for free.项目地址: https://gitcode.com/GitHub_Trending/fr/freeCodeCamp创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考