从一次相邻比较,
到完整升序排序
今天把昨天的临时变量交换用于排序:先走完一轮相邻比较,再用外层循环重复这个过程,让数组从小到大排列。
左边较大时才交换
升序是从小到大。比较相邻的 values[index] 与 values[index + 1],只有左边大于右边时才用临时变量交换。两个值相等时不交换,但循环仍继续向右比较。
一轮冒泡不等于全部排好
从数组 {8,3,5,2} 开始,第一轮的三次比较得到下面的变化:
初始:8 3 5 2
第一次比较后:3 8 5 2
第二次比较后:3 5 8 2
第三次比较后:3 5 2 8最大值 8 已经到达末尾,但前面的 3、5、2 还没有排好。第二轮只比较前面三个元素,得到 {3,2,5,8};第三轮再比较前两个,得到 {2,3,5,8}。
外层控制轮数,内层完成本轮比较
round 从 0 开始,0 对应第一轮。内层循环完整结束后才执行 round++;进入下一轮时,index 重新从 0 开始。
内层条件是 index < count - 1 - round。减 1 是因为还要访问右边的 index + 1;再减去 round,则跳过末尾已经到达最终位置的元素。五个元素依次比较 4、3、2、1 次。
#include<stdio.h>
int main(void)
{
int values[5] = { 4, -2, 4, 1, 0 };
size_t count = sizeof(values) / sizeof(values[0]);
for (size_t round = 0; round < count - 1; round++)
{
for (size_t index = 0; index < count - 1 - round; index++)
{
if (values[index] > values[index + 1])
{
int temp = values[index];
values[index] = values[index + 1];
values[index + 1] = temp;
}
}
}
printf("排序后的数组:\n");
for (size_t index = 0; index < count; index++)
{
printf("%d ", values[index]);
}
printf("\n");
return 0;
}两次需要订正的地方
第一次输入代码时,我把升序判断的 > 写成了 <,运行输出 8 5 3 2。检查后发现这会在左边较小时交换;自行改回 > 后,一轮正确输出 3 5 2 8。
预测 {4,-2,4,1,0} 的第一轮时,我最初只写出首次交换后的 {-2,4,4,1,0}。逐对追踪后,确认整轮结果是 {-2,4,1,0,4};随后独立预测第二轮为 {-2,1,0,4,4}。一次比较、一轮冒泡与全部排序,是三个不同的进度。
实际运行与边界理解
- {8,3,5,2} 完整排序输出 2 3 5 8。
- 包含负数与重复值的 {4,-2,4,1,0} 输出 -2 0 1 4 4。
- 以上正确运行均正常退出,代码为 0。
最后的理解题中,我能说明:当前代码对已经升序的数组仍执行比较,但不交换;单元素数组的 count - 1 为 0,外层循环不执行。这两项是推理结果,今天没有单独运行这两组输入。
下一课学习一轮没有交换时提前结束,并统计比较次数与交换次数,观察排序过程做了多少工作。