此页面需较新浏览器(支持 SharedArrayBuffer)。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
把数组排好顺序
- 排序重新排列数组,让元素从小到大。
- 我们就地排序:在同一个数组里把元素挪来挪去,没有返回值。
- 三种经典方法都能做到:冒泡、插入、选择排序。
交换两个元素
- 每种排序都需要交换两个元素。先用一个临时变量存住一个,再覆盖。
int t = a[i]; a[i] = a[j]; a[j] = t;交换位置i和j。- 忘了临时变量就会丢掉其中一个值 —— 一定要保留它。
冒泡排序
- 遍历数组,比较每一对相邻的元素:
a[j]和a[j + 1]。 - 如果顺序不对,就交换它们。最大的值会“冒”到末尾。
- 一遍一遍地重复,直到整个数组都排好序。
插入排序
- 把数组左边的部分当作已经排好序的,然后一次扩大一个元素。
- 把下一个元素当作关键值,把更大的已排序元素向右移,再把关键值放进空出来的位置。
- 很多人整理手里的扑克牌就是这样做的。
English
#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;
}
常见错误
- 冒泡、选择、插入排序都是 O(n²)。
- 手动追踪一个小数组,检查排序。
现在轮到你
- 按升序(从小到大)就地排序,没有返回值。
- 检查器会尝试好几个数组,包括负数和一个已经排好序的。
- 不要自己写
main—— 检查器会提供。
探索
Watch a sort run
Bubble / selection / insertion all compare and swap into order.
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
Complete void swap(int a[], int i, int j) so it exchanges the items at index i and j, in place (no return). Do 不 write a main.
点击“运行”查看此处输出。
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
Complete void bubble_sort(int a[], int n) so it sorts the array ascending, in place, using bubble sort. Do 不 write a main.
点击“运行”查看此处输出。
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
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 不 write a main.
点击“运行”查看此处输出。