此页面需较新浏览器(支持 SharedArrayBuffer)。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
把数组排好顺序
- 排序(sorting)就是把数组里的值排好顺序,通常是从小到大。
- 在 AP CSA 考试中,你必须会写和追踪两种排序:选择排序(selection sort)和插入排序(insertion sort)。
- 你还需要会追踪(但不用会写)第三种排序:归并排序(merge sort)。这三种我们都会看。
选择排序:基本思路
- 从左到右遍历数组。
- 在每个位置
i,找出最小的值(在还没排好的那一部分里,也就是从i到末尾)。 - 把那个最小的值交换到位置
i。这样0..i就排好了。 - 重复,直到整个数组都排好顺序。
English
public class Sorter {
public static void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i; // index of smallest so far
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j; // found a smaller value
}
}
int temp = a[min]; // swap a[i] and a[min]
a[min] = a[i];
a[i] = temp;
}
}
}
选择排序:一次追踪
- 让我们对
{5, 2, 4, 1, 3}进行排序。|左侧的部分已经排好序了。 - 每一趟从剩下的部分里挑出最小的值,交换到前面。
start: [5, 2, 4, 1, 3]
i=0 smallest=1 → swap a[0],a[3]: [1 | 2, 4, 5, 3]
i=1 smallest is already 2 → no move: [1, 2 | 4, 5, 3]
i=2 smallest=3 → swap a[2],a[4]: [1, 2, 3 | 5, 4]
i=3 smallest=4 → swap a[3],a[4]: [1, 2, 3, 4 | 5]
done: [1, 2, 3, 4, 5]
插入排序:基本思路
- 想象你手里拿着扑克牌,一次把一张牌插到正确的位置。
- 从下标
1开始。把这个值叫作 key(钥匙/待插入的值)。 - 把左边比它大的值都向右挪一格,直到 key 能放进去。
- 把 key 放进空位。这样它左边的所有值都排好了。
English
public class Sorter {
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i]; // the value to place
int j = i - 1;
while (j >= 0 && a[j] > key) { // shift bigger values right
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = key; // drop key into the gap
}
}
}
插入排序:一次追踪
- 再次对
{5, 2, 4, 1, 3}进行排序。随着遍历的进行,|左侧的部分始终保持有序。 key是每一趟我们要插入的值。
start: [5, 2, 4, 1, 3]
i=1 key=2 → shift 5 right, place 2: [2, 5 | 4, 1, 3]
i=2 key=4 → shift 5 right, place 4: [2, 4, 5 | 1, 3]
i=3 key=1 → shift 5,4,2 right, place 1: [1, 2, 4, 5 | 3]
i=4 key=3 → shift 5,4 right, place 3: [1, 2, 3, 4, 5]
done: [1, 2, 3, 4, 5]
归并排序:只追踪
- 归并排序(merge sort)用到递归(第 15 课)。考试不要求你写它,但你必须会追踪它。
- 一次又一次地把数组对半分(split),直到每一小块只剩一个值。
- 再把成对的小块合并(merge)起来,始终保持它们有序。
归并排序:一次追踪
- 一个值本身就算是"有序"的。把两个有序的小块合并,就得到一个更大的有序小块。
split: [5, 2, 4, 1]
[5, 2] [4, 1]
[5] [2] [4] [1]
merge: [2, 5] [1, 4]
merge: [1, 2, 4, 5]
- 选择排序和插入排序在大数组上很慢(它们大约要 n² 步)。
- 归并排序在大数组上更快(大约 n·log n 步)。这就是它重要的原因。
常见错误
- 选择排序和插入排序都是 O(n²)。
- 手动追踪一个小数组,检查排序。
现在轮到你
- 每个任务给你一个带 TODO 的方法骨架。请原地排序数组(直接改
a本身)。 - 一个隐藏的 Harness 会排序好几个数组并检查结果。
- 使用 Check answer(检查答案)将您的代码与提供的测试一起编译并查看结果。请保留启动文件中显示的类和接口。
探索
Selection / insertion sort
Sorting compares and swaps until the list is ordered.
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
Complete selectionSort(int[] a) so it sorts the array in place from small to large, using selection sort. The checker tests several arrays.
点击“运行”查看此处输出。
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
Complete insertionSort(int[] a) so it sorts the array in place from small to large, using insertion sort. The checker tests several arrays.
点击“运行”查看此处输出。
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
Complete isSorted(int[] a) returning true if the array is in order from small to large (each item is <= the next), else false. An empty or one-item array counts as sorted.
点击“运行”查看此处输出。