冒泡排序
此页面需较新浏览器(支持 SharedArrayBuffer)。请升级 Chrome、Edge、Firefox 或 Safari 至最新版本。
把最短的时间放在前面
- 三个比赛用时放在数组里:
14、9、11。最小的应该排在最前。 - 比较每一对相邻的值。左边更大时,交换它们。
- 一次比较排不完整个列表。比完这一对,再比下一对。
English
DECLARE Score : ARRAY[1:3] OF INTEGER
DECLARE J, Temp : INTEGER
Score[1] ← 14
Score[2] ← 9
Score[3] ← 11
FOR J ← 1 TO 2
IF Score[J] > Score[J + 1]
THEN
Temp ← Score[J]
Score[J] ← Score[J + 1]
Score[J + 1] ← Temp
ENDIF
NEXT J
OUTPUT Score[1]
OUTPUT Score[2]
OUTPUT Score[3]
再走一趟
- 内层循环走一趟,会把这一趟里最大的值冒到后面。
- 外层循环把这一趟再做几次。四个值,三趟就够了。
- 这就是考纲里的冒泡排序。你之前写的线性查找只是在找。排序会把数据重新排好。
English
DECLARE Score : ARRAY[1:4] OF INTEGER
DECLARE I, J, Temp : INTEGER
Score[1] ← 4
Score[2] ← 1
Score[3] ← 3
Score[4] ← 2
FOR I ← 1 TO 3
FOR J ← 1 TO 3
IF Score[J] > Score[J + 1]
THEN
Temp ← Score[J]
Score[J] ← Score[J + 1]
Score[J + 1] ← Temp
ENDIF
NEXT J
NEXT I
OUTPUT Score[1]
OUTPUT Score[2]
OUTPUT Score[3]
OUTPUT Score[4]
注意
- 交换要用一个
Temp变量。只写Score[J] ← Score[J + 1]会丢掉左边的值。 - 内层
NEXT写J。外层NEXT写I。
当没有交换发生时停止
- 修复后的版本每次都会执行所有轮次,即使列表已经有序。
- 一个
BOOLEAN标志Swap记录本轮是否发生了交换。若某轮无交换,则说明列表已排序,循环随即停止。 - 每轮结束后,剩余未排部分中的最大值即归位,因此
Last的范围缩减一位。
DECLARE Score : ARRAY[1:5] OF INTEGER
DECLARE J, Last, Temp : INTEGER
DECLARE Swap : BOOLEAN
Score[1] ← 2
Score[2] ← 1
Score[3] ← 3
Score[4] ← 4
Score[5] ← 5
Last ← 4
REPEAT
Swap ← FALSE
FOR J ← 1 TO Last
IF Score[J] > Score[J + 1]
THEN
Temp ← Score[J]
Score[J] ← Score[J + 1]
Score[J + 1] ← Temp
Swap ← TRUE
ENDIF
NEXT J
Last ← Last - 1
UNTIL NOT Swap OR Last = 0
FOR J ← 1 TO 5
OUTPUT Score[J]
NEXT J
此处第一轮交换了2和1,第二轮未发生任何交换,因此排序在完成两轮后便停止,而非四轮。
常见错误
- 判断是“左边更大”,这样较小的值才会移到左边。方向反了,就排成了倒序。
- 这门课的数组从 1 开始数。最后一对是末尾前一格和最后一格。
- 在4单元格数组中访问
FOR J ← 1 TO 4会读取Score[5],而该位置并不存在。内层循环会在到达末尾前一步停止。 - 在
REPEAT之前设置一次Swap ← FALSE。必须在每一轮的起始处将其重置。
现在轮到你
- 第一项任务是执行一轮遍历。第二项是完成完整排序。第三项读取五个数值,并使用
Swap标志将它们按降序排列。每个数值独占一行输出。 - 按检查答案来测试它。
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
数组 Score 里是 14、9、11。只走一趟:左边更大时交换相邻项。把三个值各输出一行(9,然后 11,然后 14)。
点击“运行”查看此处输出。
难度 4/5 · 今日首次完成可获 280 金币及少量额外奖励
数组 Score 里是 4、1、3、2。用冒泡排序排成升序,并把四个值各输出一行。
点击“运行”查看此处输出。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
将五个整数读入 Score : ARRAY[1:5] OF INTEGER。使用 BOOLEAN 标志 Swap 进行冒泡排序,按降序排列,当一趟遍历没有发生交换时停止。逐行输出这五个值。
点击“运行”查看此处输出。