Sorting: bubble, selection, and insertion · 排序:冒泡、选择与插入
Putting an array in order
- Sorting rearranges an array so the items go from smallest to largest.
- We sort in place: we move items around inside the same array, with no return value.
- Three classic methods do this: bubble, insertion, and selection sort.
把数组排好序
- 排序重新排列数组,让元素从小到大。
- 我们就地排序:在同一个数组里把元素挪来挪去,没有返回值。
- 三种经典方法都能做到:冒泡、插入、选择排序。
Swapping two elements
- Every sort needs to swap two items. Save one in a temporary, then overwrite.
int t = a[i]; a[i] = a[j]; a[j] = t;exchanges positionsiandj.- Forgetting the temporary loses one of the values — always keep it.
交换两个元素
- 每种排序都需要交换两个元素。先用一个临时变量存住一个,再覆盖。
int t = a[i]; a[i] = a[j]; a[j] = t;交换位置i和j。- 忘了临时变量就会丢掉其中一个值 —— 一定要保留它。
Bubble sort
- Go through the array and compare each pair of neighbours:
a[j]anda[j + 1]. - If they are in the wrong order, swap them. The biggest value "bubbles" to the end.
- Repeat the passes until the whole array is in order.
冒泡排序
- 遍历数组,比较每一对相邻的元素:
a[j]和a[j + 1]。 - 如果顺序不对,就交换它们。最大的值会“冒”到末尾。
- 一遍一遍地重复,直到整个数组都排好序。
Insertion sort
- Treat the left part of the array as already sorted, and grow it one item at a time.
- Take the next item as a key, shift bigger sorted items to the right, then drop the key into the gap.
- This is how many people sort playing cards in their hand.
插入排序
- 把数组左边的部分当作已经排好序的,然后一次扩大一个元素。
- 把下一个元素当作关键值,把更大的已排序元素向右移,再把关键值放进空出来的位置。
- 很多人整理手里的扑克牌就是这样做的。
#include <stdio.h>
int main(void) {
int a[] = {3, 1, 2};
// one bubble pass: compare neighbours and swap if out of order
for (int j = 0; j < 2; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
printf("%d %d %d\n", a[0], a[1], a[2]); // 1 2 3
return 0;
}
Common mistakes
- Bubble, selection and insertion sort are all O(n²).
- Trace a small array by hand to check your sort.
常见错误
- 冒泡、选择、插入排序都是 O(n²)。
- 手动追踪一个小数组,检查排序是否正确。
Now you try
- Sort ascending (smallest first), in place, with no return value.
- The checker tries several arrays, including negatives and an already-sorted one.
- Do not write a
main— the checker provides one.
现在轮到你了
- 按升序(从小到大)就地排序,没有返回值。
- 检查器会尝试好几个数组,包括负数和一个已经排好序的。
- 不要自己写
main—— 检查器会提供。
Watch a sort run · 看排序的过程
Bubble / selection / insertion all compare and swap into order. · 冒泡 / 选择 / 插入排序都是比较并交换到有序。
Complete void swap(int a[], int i, int j) so it exchanges the items at index i and j, in place (no return). Do not · 不 write a main. · 完成 void swap(int a[], int i, int j),让它就地交换下标 i 和 j 上的元素(没有返回值)。不要写 main。
Click Run to see the output here. · 点击“运行”查看此处输出。
Complete void bubble_sort(int a[], int n) so it sorts the array ascending, in place, using bubble sort. Do not · 不 write a main. · 完成 void bubble_sort(int a[], int n),用冒泡排序把数组就地升序排好。不要写 main。
Click Run to see the output here. · 点击“运行”查看此处输出。
Complete void insertion_sort(int a[], int n) so it sorts the array ascending, in place, using insertion sort (take each item as a key and shift bigger items right). Do not · 不 write a main. · 完成 void insertion_sort(int a[], int n),用插入排序把数组就地升序排好(把每个元素当作关键值,把更大的元素向右移)。不要写 main。
Click Run to see the output here. · 点击“运行”查看此处输出。