| English | 释义 | 拼音 |
|---|---|---|
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | 分治 | fēn zhì |
| merge sort/mɜːdʒ sɔːt/ | 归并排序 | guī bìng pái xù |
| merge/mɜːdʒ/ | 合并 | hé bìng |
递归遇上查找与排序
- 同样的分治思想驱动递归二分查找和归并排序。
- 把问题分成两半,解决两半,再合并。
- 递归二分查找通过在一半上调用自己来查找那一半。
- 归并排序先对每一半排序,然后把已排序的两半合并到一起。
递归二分查找
- 基准情形:一个空范围意味着目标未找到。
- 看中间。若它就是目标,返回它的下标。
- 若目标更小,在左半上递归;若更大,在右半上。
- 每次调用把范围减半——同样的
O(log n),用递归写出来。
归并排序
- 把数组分成两半;对每一半递归排序。
- 基准情形:一个 0 个或 1 个元素的数组已经有序。
- 合并:走过两个已排序的半,总是取更小的前端元素。
- 比
n²的排序快得多——约n log n的工作量。
分治为何取胜
- 每步把问题减半带来那个
log n因子。 - 归并排序的
n log n在大数组上胜过选择/插入排序的n²。 - 基准情形(空或一个元素)停止每一个分支。
- 与所有递归同样的形状:向下分,向上合。
递归二分查找在一半上递归(目标只在一侧);归并排序在两半**上递归然后把它们合并。**两者都需要基准情形——对查找,空范围意味着“未找到”;对归并排序,0 个或 1 个元素的数组已经有序。分治正是让它们快的原因(O(log n) 和 O(n log n))。
对 [3, 1, 2, 4] 做归并排序:
- 分成
[3, 1]和[2, 4];各自排序 →[1, 3]和[2, 4]。 - 合并:取 1,再取 2,再取 3,再取 4 →
[1, 2, 3, 4]。 - 每次合并轮流挑更小的前端元素。
递归二分查找在一半上递归(基准情形:空范围 = 未找到),做 O(log n) 查找。归并排序在两半上递归并把它们合并(基准情形:0 或 1 个元素),做 O(n log n) 排序。两者都是分治:向下分,向上合——比 n² 快得多。
Merge sort splits into halves, then merges up
Single elements are sorted (base case); merges combine them upward.
Recursive binary search recurses on...
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
The target is only on one side of the middle.
Merge sort recurses on...
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Sort each half, then merge the two sorted halves.
The base case for merge sort is an array of...
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
One (or zero) element needs no sorting.
Merge sort's running time is about...
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
log n levels of splitting, n work per level.
Both recursive binary search and merge sort are divide-and-conquer algorithms.
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
Both split the problem in half and recurse.
Order the merge step for halves [1,3] and [2,4].
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
Always take the smaller front element: 1, 2, 3, 4.