词汇
| English | 释义 | 拼音 |
|---|---|---|
| Sorting/ˈsɔːtɪŋ/ | 排序 | pái xù |
| selection sort/sɪˈlekʃn sɔːt/ | 选择排序 | xuǎn zé pái xù |
| insertion sort/ɪnˈsɜːʃn sɔːt/ | 插入排序 | chā rù pái xù |
| in place/ɪn pleɪs/ | 原地 | yuán dì |
把东西排好序
- 排序把元素重新排列成有序(比如从小到大)。
- AP 课程涵盖两种简单排序:选择排序和插入排序。
- 两者都用嵌套循环,把元素交换或移动到位。
- 先排序,才能在之后用快速的二分查找。
选择排序
- 找到最小的剩余元素并把它交换到前面。
- 然后找剩下里最小的,交换到下一个位置,如此继续。
- 数组的前部逐渐变有序;后部未排序部分缩小。
- 每趟一次交换——但每趟仍要扫描其余部分。

插入排序:逐轮将每个键值移至正确位置
插入排序
- 取下一个元素,把它往回移到已排好序前部里的正确位置。
- 就像整理手里的一手牌:把每张新牌插到它该在的地方。
- 有序区每趟增长一个。
- 当数据已接近有序时很快。
工作量多大
- 两种排序都用嵌套循环,所以最坏情况约做
n²次比较。 - 这对小数组没问题,但对很大的数组很慢。
- 它们原地排序——不需要第二个数组。
- 考试要你追踪它们,而不只是说出名字。
注意
选择排序把最小的剩余元素交换到前面;插入排序把每个新元素往回移到有序部分——别搞混。两者都是 O(n²) 的嵌套循环排序,都原地排序。一步一步追踪它们(AP 考试问每趟之后数组的状态),而不是死记一个名字。
例子
对 [3, 1, 2] 做选择排序:
- 第 1 趟:最小是
1;交换到前面 →[1, 3, 2]。 - 第 2 趟:
[3, 2]里最小是2;交换 →[1, 2, 3]。 - 排好了——前部每趟增长一个元素。
关键点
排序给元素排序。选择排序反复把最小的剩余元素交换到前面;插入排序把每个新元素往回移到有序部分。两者都是嵌套循环、原地、O(n²) 的排序。先排序,之后才能用快速的二分查找。
探索
逐步走过一次排序
每一趟再把一个元素排到位。
练习
选择排序的工作方式是……
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
选择排序选出最小值并把它交换到前面。
练习
插入排序的工作方式是……
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
插入排序把每个元素插入它的有序位置。
练习
在最坏情况下,两种排序都约做……
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
嵌套循环给出 O(n²)。
练习
选择排序和插入排序都原地工作(不需要第二个数组)。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
它们重排同一个数组。
练习
给对 [3, 1, 2] 做选择排序的各趟排序。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
前部逐渐有序,每趟一个元素。
练习
先排序有用,因为它让你之后能用……
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
二分查找需要已排序数据。