C Day 22

从一次相邻比较,
到完整升序排序

今天把昨天的临时变量交换用于排序:先走完一轮相邻比较,再用外层循环重复这个过程,让数组从小到大排列。

左边较大时才交换

升序是从小到大。比较相邻的 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 次。

day22.c · 最终代码
#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,外层循环不执行。这两项是推理结果,今天没有单独运行这两组输入。

下一课学习一轮没有交换时提前结束,并统计比较次数与交换次数,观察排序过程做了多少工作。