🧩 分治算法
一大盒拼图很难一次拼完，聪明的办法是：先按颜色分成几小堆，每小堆拼好，最后再把小拼图拼成整幅。分治算法就是这个套路——把大问题拆成小问题（分），小问题解决掉（治），再把小答案合成大答案（合）。这一页看两个最出名的分治排序：归并排序和快速排序。
考纲知识点：归并排序算法
快速排序算法
快速排序算法
📖
考纲 · 知识点详述
摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 五级
- (9)掌握分治算法的基本原理，能够使用归并排序和快速排序对数组进行排序。
📚
先学一学
花 5 分钟读完下面 5 课，再去闯关就不慌啦
1
✂️ 分治三步：分解、解决、合并
分治（Divide and Conquer）就是把一个大问题：① 分解成几个更小、结构一样的子问题；② 子问题小到直接能解就解决，还不能就直接再分；③ 把小问题的答案合并成大问题的答案。分到「只剩一个数」这种最小情况，答案自然就有了。
🧩 生活类比：全班大扫除
· 分解：把全班分成 4 个小组，每组负责一片区域。
· 解决：每组把自己的区域打扫干净。
· 合并：检查完所有小组，整间教室就干净了。
组太大就再分小组——和分治一模一样。
· 解决：每组把自己的区域打扫干净。
· 合并：检查完所有小组，整间教室就干净了。
组太大就再分小组——和分治一模一样。
💡 口诀：分治三步走——拆成小问题、小问题各自办、小答案拼大答案。
2
🃏 归并排序：先拆到一张牌，再两两合并
归并排序把数组从中间对半拆，一直拆到每个小组只剩 1 个数（1 个数当然有序），然后开始合并：把两堆已经排好序的数像洗牌一样合成一堆有序的。
🧪 合并两堆有序牌
左堆 [3, 8]，右堆 [1, 5]：
两堆都看最前面的小牌：3 和 1，取更小的 1 → 结果 [1]
再比 3 和 5，取 3 → [1, 3]
再比 8 和 5，取 5 → [1, 3, 5]
剩 8 → [1, 3, 5, 8]，合并完成！
两堆都看最前面的小牌：3 和 1，取更小的 1 → 结果 [1]
再比 3 和 5，取 3 → [1, 3]
再比 8 和 5，取 5 → [1, 3, 5]
剩 8 → [1, 3, 5, 8]，合并完成！
💡 口诀：归并 = 拆到单张、两两合并；合并时每次拿两堆里更小的那张。
✅ 归并排序很稳定
合并时若左右两堆有相等的数，总让左边（原来在前）的先出来，所以相等的数顺序不变——归并排序是稳定的。
💡 口诀：相等先取左边 → 稳定；归并排序是「稳定先生」。
3
⚡ 快速排序：挑个基准，小的站左边、大的站右边
快速排序先挑一个数当基准（pivot），把比它小的都放左边、比它大的都放右边，于是基准一次就回到了它最终的位置；再对左边、右边分别用同样的办法排，直到全部有序。
🧪 例子：排 [5, 3, 8, 1, 6]
挑基准 5：比 5 小的 {3, 1} 放左边，比 5 大的 {8, 6} 放右边 → [3, 1] 5 [8, 6]，5 已归位。
左边 [3, 1] 挑基准 3 → [1] 3 ……
右边 [8, 6] 挑基准 8 → 6 8 ……
最后整体有序：[1, 3, 5, 6, 8]。
左边 [3, 1] 挑基准 3 → [1] 3 ……
右边 [8, 6] 挑基准 8 → 6 8 ……
最后整体有序：[1, 3, 5, 6, 8]。
💡 口诀：快排 = 挑基准、分两边；基准一次归位，左右再各自快排。
⚠️ 快排不稳定 + 最坏情况
快排把相等的数可能换到前面去，所以不稳定。如果每次挑的基准都特别倒霉（比如已排好序的数组还总挑到最大/最小），一边总是空，快排会退化到约 O(n²)。但平均情况下它非常快，是很多系统排序的默认选择。
💡 口诀：快排平均飞快、不稳；最坏退化成 O(n²)，基准挑好很重要。
4
📈 复杂度：为什么是 O(n log n)
🧮 数一数工作量和层数
归并每次把数组对半拆，n 个元素能拆出约 log₂n 层（8 个拆 3 层：8→4→2→1）。每一层里，所有元素合计都要被「处理/合并」约一遍，每层工作量约 n。总工作量 ≈ n × log n，所以归并排序复杂度是 O(n log n)。快排平均也是 O(n log n)。
💡 口诀：log n 层，每层干 n 的活；n × log n = 又快又稳的排序复杂度。
⚔️ 和四级三种排序比比
冒泡、插入、选择是 O(n²)；归并、快排是 O(n log n)。n=100 万时，n² 约一万亿步，n log n 约两千万步——分治让排序「跨了一个大台阶」。
💡 口诀：n² 慢慢爬，n log n 大步跨；数据一大，分治排序明显占优。
5
🆚 归并 vs 快排 & 行业实际
🆚 一张表认清楚
· 归并排序：先拆到单张再两两合并；稳定；最坏也是 O(n log n)；合并时要借额外数组（占空间）。
· 快速排序：挑基准分两边，基准归位；不稳定；平均 O(n log n)，最坏可能 O(n²)；不用额外大数组。
· 都靠「拆半 + 递归」，和递归算法页的分治是一家人。
· 快速排序：挑基准分两边，基准归位；不稳定；平均 O(n log n)，最坏可能 O(n²)；不用额外大数组。
· 都靠「拆半 + 递归」，和递归算法页的分治是一家人。
💡 口诀：归并稳而匀，快排快而省；选哪个看你要不要稳定、怕不怕最坏。
🌟 行业实际
给一亿用户按积分排名、把搜索结果按相关度排序……真实系统都用分治级排序。很多编程语言内置的排序是「快排 + 归并」的混血（数据少用插入，数据多用快排/归并），兼顾稳定和速度——可见会分析复杂度、会选算法有多重要。
🎯
闯关小锦囊 · 考点提醒
- 分治三步：分解 → 解决（子问题）→ 合并；拆到最小情况答案自然出来。
- 归并排序：拆到单个元素再两两合并，每次取两堆里更小的；稳定，O(n log n)。
- 快速排序：挑基准、小的左大的右、基准归位，再递归排两边；不稳定，平均 O(n log n)、最坏 O(n²)。
- 复杂度来源：约 log n 层 × 每层约 n 的活 = O(n log n)。
- 归并占额外空间；快排不占大额外空间。数据少时插入排序反而更省。
- 合并两个长度 n 的有序数组，最坏比较 2n − 1 次；快排基准挑得倒霉（如已排序数组仍取首个元素）会退化到 O(n²)。
🎮
学完了？来闯关！
下面 15 个小挑战，点一点就能玩
Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。