Sorting Algorithms · 排序算法
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| 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ì |
Putting things in order
- Sorting 排序 rearranges elements into order (smallest to largest, say).
- The AP course covers two simple sorts: selection sort 选择排序 and insertion sort 插入排序.
- Both use nested loops and swap or shift elements into place.
- Sorting first is what lets you use fast binary search afterwards.
把东西排好序
- 排序把元素重新排列成有序（比如从小到大）。
- AP 课程涵盖两种简单排序：选择排序和插入排序。
- 两者都用嵌套循环，把元素交换或移动到位。
- 先排序，才能在之后用快速的二分查找。
Selection sort
- Find the smallest remaining element and swap it to the front.
- Then find the smallest of what's left, swap it into the next spot, and so on.
- The front of the array grows sorted; the back shrinks unsorted.
- One swap per pass — but it still scans the rest each pass.
选择排序
- 找到最小的剩余元素并把它交换到前面。
- 然后找剩下里最小的，交换到下一个位置，如此继续。
- 数组的前部逐渐变有序；后部未排序部分缩小。
- 每趟一次交换——但每趟仍要扫描其余部分。
Insertion sort
- Take the next element and shift it back into its correct place among the already-sorted front.
- Like sorting a hand of cards: slot each new card where it belongs.
- The sorted region grows by one each pass.
- Fast when the data is already nearly sorted.
插入排序
- 取下一个元素，把它往回移到已排好序前部里的正确位置。
- 就像整理手里的一手牌：把每张新牌插到它该在的地方。
- 有序区每趟增长一个。
- 当数据已接近有序时很快。
How much work
- Both sorts use nested loops, so they do about
n²comparisons in the worst case. - That's fine for small arrays but slow for very large ones.
- They sort in place 原地 — no second array needed.
- The exam wants you to trace them, not just name them.
工作量多大
- 两种排序都用嵌套循环，所以最坏情况约做
n²次比较。 - 这对小数组没问题，但对很大的数组很慢。
- 它们原地排序——不需要第二个数组。
- 考试要你追踪它们，而不只是说出名字。
Selection sort SWAPS the smallest remaining element to the front; insertion sort SHIFTS each new element back into the sorted part — don't mix them up. Both are O(n²) nested-loop sorts and both sort in place. Trace them step by step (the AP exam asks for the array's state after each pass), rather than memorising a name.
选择排序把最小的剩余元素交换到前面；插入排序把每个新元素往回移到有序部分——别搞混。两者都是 O(n²) 的嵌套循环排序，都原地排序。一步一步追踪它们（AP 考试问每趟之后数组的状态），而不是死记一个名字。
Selection sort on [3, 1, 2]:
- Pass 1: smallest is
1; swap to front →[1, 3, 2]. - Pass 2: smallest of
[3, 2]is2; swap →[1, 2, 3]. - Sorted — the front grew one element per pass.
对 [3, 1, 2] 做选择排序：
- 第 1 趟：最小是
1；交换到前面 →[1, 3, 2]。 - 第 2 趟：
[3, 2]里最小是2；交换 →[1, 2, 3]。 - 排好了——前部每趟增长一个元素。
Sorting orders elements. Selection sort repeatedly swaps the smallest remaining element to the front; insertion sort shifts each new element back into the sorted part. Both are nested-loop, in-place, O(n²) sorts. Sorting enables fast binary search afterwards.
排序给元素排序。选择排序反复把最小的剩余元素交换到前面；插入排序把每个新元素往回移到有序部分。两者都是嵌套循环、原地、O(n²) 的排序。先排序，之后才能用快速的二分查找。
Stepping through a sort · 逐步走过一次排序
Each pass places one more element in order. · 每一趟再把一个元素排到位。
Selection sort works by... · 选择排序的工作方式是……
Selection sort selects the minimum and swaps it forward. · 选择排序选出最小值并把它交换到前面。
Insertion sort works by... · 插入排序的工作方式是……
Insertion sort inserts each element into its sorted place. · 插入排序把每个元素插入它的有序位置。
In the worst case, both sorts do about... · 在最坏情况下，两种排序都约做……
Nested loops give O(n²). · 嵌套循环给出 O(n²)。
Both selection and insertion sort work in place (no second array). · 选择排序和插入排序都原地工作（不需要第二个数组）。
They rearrange the same array. · 它们重排同一个数组。
Order the passes of selection sort on [3, 1, 2]. · 给对 [3, 1, 2] 做选择排序的各趟排序。
Front grows sorted, one element per pass. · 前部逐渐有序，每趟一个元素。
Sorting first is useful because it lets you later use... · 先排序有用，因为它让你之后能用……
Binary search needs sorted data. · 二分查找需要已排序数据。