翻到26.3.14那天练手的一小段代码题目朴素得不能再朴素输入三个整数按从小到大排序输出。这道题在翁恺老师的C语言练习题、浙大OJ的基础题集、以及各个入门教材里出现频率都极高也是不少人真正意义上写出的第一段“排序算法”代码。题目看着简单但我这些年帮人改过不少版本能一次写对、还能讲清楚每一步原因的人其实不多——有人漏一个比较有人把交换写成连续赋值有人跑通一次就再也不回看等到后面学冒泡排序和选择排序时又卡住。所以今天用一篇博文的篇幅把这题掰开揉碎讲一遍。内容分五块为什么这道题这么经典、三种对应不同算法思想的写法、最容易踩的三个细节、怎么从三数排序平滑升级到N个数的通用排序最后是一段我实际排查错误代码的完整过程。正在学C语言基础、准备刷数据结构排序算法题的朋友都可以从里面找到对自己有用的东西。1. 三数排序这道题为什么几乎所有C语言入门教程都拿它当排序第一课1.1 题目解析它到底在考什么先说语法层面。这道题用到的知识非常少三个int变量、一次scanf、若干个if、一个printf再加一个用于交换的临时变量。也就是说只要学完最基本的顺序结构和分支结构就有能力做这道题。它不会把你挡在“前置知识”之外这也是它能当入门题的第一个原因。但考题从来都不是语法。三个整数之间一共有六种排列顺序abc、acb、bac、bca、cab、cba。程序里没有一个叫“排序”的指令能用的只有比较和交换。你必须在六种情况下都给出正确输出同时尽量少写比较这就逼着你思考“哪两个变量需要先比哪两个需要后比”。更深一层这道题练的是把“有序”这个概念翻译成操作序列。比如“a最小”这句话在代码里的意思往往是“a不大于b且a不大于c”。很多初学者写不明白不是不会if而是不知道“满足什么条件才等于排好序”。这种从结果倒推条件的思维方式恰恰是后面学所有排序算法的地基。顺带说一句翁恺老师在课程里拿这类题当例题也是看重它的这个特性代码量小但五脏俱全。它包含交换变量、嵌套分支、边界条件还有一点点“怎么设计比较顺序”的思想已经是一次微型的算法设计练习了。1.2 最常见的错误姿势我见过的错误样式中大概可以分为四类基本可以覆盖大多数初学者的翻车现场。第一类是交换写成连续赋值比如a b; b a;执行完第一条语句之后原a的值已经丢了b再赋给“新的a”时得到的是原b自己两个变量都变成了原b。这个错误在课堂作业里出现的频率高得离谱。第二类是scanf漏了地址符写成scanf(%d %d %d, a, b, c);。有些编译器会有警告但初学者经常忽略程序运行时就会从乱七八糟的内存位置读数据输出一个天知道哪来的数。第三类是只写了两次比较。比如只有if (a b)和if (b c)看起来比了两次但第二次交换完之后a和b的大小关系又可能变化最后一输出就乱了。这个问题会在第5章用一个真实案例详细演示。第四类是把大于号写成小于号排序结果从升序变成降序。这种错往往不是不会而是手滑但恰好说明“最终验证”这步不能省——跑一组3 2 1立刻就能看出来。这四类问题的共同根源是脑子里缺少一条“程序执行过程”的完整链条。所以我的建议一直是不要急着上机先在纸上把三个变量画成三个格子用手模拟一遍交换过程。这一步想明白了后面所有和排序有关的代码都会顺畅很多。2. 三种实现思路比较交换、相邻上浮、全枚举选哪条路决定你能走多远2.1 先把最小的送到第一格有序比较交换法这是教材和网上最容易见到的一种写法。核心思路很直接第一步保证a是a和b里较小的第二步保证a也比c小那么a最小第三步再把b和c排好。代码如下#include stdio.h int main() { int a, b, c, tmp; printf(请输入三个整数用空格分隔); scanf(%d %d %d, a, b, c); if (a b) { tmp a; a b; b tmp; } if (a c) { tmp a; a c; c tmp; } if (b c) { tmp b; b c; c tmp; } printf(%d %d %d\n, a, b, c); return 0; }这个写法有两个值得琢磨的地方。第一为什么前两个if之后a就是最小值因为第一个if处理完a是前两个数里的较小者第二个if再把当前a和c比较如果c更小就把a和c交换。这一来a一定不大于另外任何一个所以它全局最小。第二注意这里每一步的交换都会改变变量内容所以“a”这个符号始终代表“当前第一个位置上的值”而不是“原来的第一个数”。这个概念想清楚看代码就不会晕。从算法思维上看这个写法其实已经内置了“选择排序”的影子先把最小值选出来放到最前面再处理剩下的两个数。只不过三数规模太小不需要循环和数组就能写完。它的优点是容易验证、几乎不犯错是所有入门者最稳的起点。2.2 相邻比较大数一路往后挪三数版冒泡第二种写法和第一种长得非常像但思考路径完全不同。它的思路是先比较a和b把较小者放到a再比较b和c把较大者放到c第二次比较完之后c已经是最大的数最后再比较一次a和b把剩下两个排好。#include stdio.h int main() { int a, b, c, tmp; scanf(%d %d %d, a, b, c); if (a b) { tmp a; a b; b tmp; } if (b c) { tmp b; b c; c tmp; } if (a b) { tmp a; a b; b tmp; } printf(%d %d %d\n, a, b, c); return 0; }仔细对比就能发现这段代码和上面那段的差别只在第三个if这里是if (a b)不是if (b c)。第一轮保证a小于b第二轮把b和c比较让大的数“浮”到c的位置此时c已经拿到全组最大但第二轮交换后a和b的关系可能被破坏所以第三轮要再把a和b整理一次。这就是冒泡排序中“相邻比较交换、每趟确定一个最大值”的三数版本。这种写法理解之后对后面的冒泡排序会特别友好因为它的执行模式就是“从左往右一趟趟比较相邻元素大的往后挪”。但从教学角度我见过不少初学者在这里被绕晕他们不理解为什么第三个if比较的对象又变回a和b了。如果你也绕晕了请记住一句话变量里的值是会变的你只能根据“当前值”去决定下一步比较谁不能盯着最开始输入的几个数看。2.3 把六种排列全部列出来暴力枚举法还有一种思路和前面两种完全不同不管用什么临时变量反正三个整数一共就六种顺序直接把这六种情况全部写出来挨个判断然后输出。代码如下#include stdio.h int main() { int a, b, c; scanf(%d %d %d, a, b, c); if (a b b c) printf(%d %d %d\n, a, b, c); else if (a c c b) printf(%d %d %d\n, a, c, b); else if (b a a c) printf(%d %d %d\n, b, a, c); else if (b c c a) printf(%d %d %d\n, b, c, a); else if (c a a b) printf(%d %d %d\n, c, a, b); else printf(%d %d %d\n, c, b, a); return 0; }这个方案的优点是逻辑上绝对正确它把每种可能都明明白白列出来了不容易漏也没有交换的副作用。缺点是代码非常冗长而且这种写法基本不具备可扩展性——三数时写6个分支还能忍四数就是24种排列五数就是120种根本没法写。我把它列出来的目的是想说明一个道理同样一道题可以有完全不同的实现策略。枚举法“笨”但正确交换法“巧”但需要想清楚副作用。实际工作中我们追求的是两者平衡写出正确、可读、能扩展的代码而不是单纯追求代码最短或者跑得最快。这道小题里看清这个取舍以后写更大规模的程序会很受益。2.4 三种写法对比三种方案简单对比如下方案核心思想固定比较次数交换次数上限特点迁移价值有序比较交换最小者坐第一位33简洁稳健入门首选选择排序相邻比较上浮大数往后冒33直观但第三轮易晕冒泡排序暴力枚举穷举所有排列最坏120正确性最直观不可扩展几乎为零从表里可以看出前两种方案用三次比较解决问题思路不同但效率相同第三种方案虽然不交换但分支更宽代码也难维护。所以如果目标是为了打牢基础我建议把前两种都亲手写一遍写的时候想清楚“每一步为什么比比完之后哪个变量已经确定位置”这比单纯跑通一次有价值得多。3. 写这段代码最容易被忽略的三个细节交换、输入、边界值3.1 交换没有临时变量的一行代码就是灾难先看一段典型错误代码if (a b) { a b; b a; }从数学上看“把a和b互换”这个概念人人都会但代码里没有这种语法。你必须先把a的值存到第三方变量里才能腾出a去接收b。正确写法是这样if (a b) { tmp a; a b; b tmp; }执行顺序可以拆成三步tmp保存原aa拿走b的值b再拿走tmp里的原a。没有第一步第二步就把原a覆盖了。我见过一些教材会在后面提到用异或交换两个变量a a ^ b; b a ^ b; a a ^ b;这种写法能跑但可读性差而且对初学者来说很容易产生“我是不是漏了一个数据”的困惑。实际工程里也没有理由用它替代temp方式。我给学生的建议始终是交换就老老实实用临时变量三个字母的事不丢人。3.2 输入scanf 格式串和地址符一个都不能少这道题的输入环节是初学者翻车的重灾区。第一是漏。scanf要求传入变量的地址也就是你告诉它“把读到的数写到哪个内存位置”。如果不写等于给了它变量本身的值程序会试图往一个根本不允许写的地方写数据轻则读到垃圾值重则运行时崩溃。这个错误在所有C语言初学者代码里出现的频率常年排名前三。第二个问题出在格式串。如果题目要求“输入三个整数用空格分隔”那你用scanf(%d %d %d, a, b, c)是匹配的。但如果你输入了1,2,3这种带逗号的格式第二个和第三个%d都会匹配失败变量里保留的是编译前栈上的垃圾值输出自然全乱。所以做题前先看清题目的输入格式然后严格按格式输。第三个问题是scanf的返回值。scanf会返回成功读入的变量个数所以可以写成if (scanf(%d %d %d, a, b, c) ! 3) { printf(输入格式不正确\n); return 1; }这样用户敲错格式时程序能及时退出而不是带着错误数据继续往下算。这种“对输入保持警惕”的习惯从这道小题开始养成后面写文件读写、写网络报文解析时都受用。3.3 边界值负数、相等数、极大极小都要测很多同学跑一组正常数据就宣布“写完了”这是不严谨的。三数排序看着简单但边界情况一样能翻车。我的建议是至少测下面这一组用例输入期望输出主要验证点3 2 11 2 3完全逆序最考验交换逻辑1 2 31 2 3已经有序的情况不能乱动2 2 11 2 2两个数相等1 1 11 1 1三个数全部相等-5 0 3-5 0 3负数参与排序-3 -9 0-9 -3 0负数逆序INT_MIN 0 INT_MAXINT_MIN 0 INT_MAX极端取值用limits.h后两条需要用到一个头文件limits.h里面定义了INT_MIN和INT_MAX。测试极端值主要是为了确认交换与比较在边界取值上不会出问题。对于这里的三条if交换逻辑正常情况都能通过但如果不测这么一组你就永远不敢名正言顺地说“这段代码在任何整数输入下都正确”。顺手还能看一眼limits.h里还有LONG_MAX、CHAR_MIN这些常量以后处理更大范围整数时也用得上。相等数据的验证也很重要。有人会担心“我只写了没写相等的时候会不会漏交换”实际上两个数相等时交换不交换结果完全一样所以和在这里等价。但反过来如果把误写成相等数据不会暴露问题一定要用3 2 1这种逆序用例才能抓到。4. 从三个数到N个数数组化改造是这道题真正的延伸价值4.1 把变量换成数组把三次比较换成两层循环三数排序写完后不要急着过。下一步值得做的事情是把它改成能处理N个数的版本。最简单的路径是冒泡排序把a、b、c三个变量换成一个数组把固定三次比较换成一个双层循环。代码如下#include stdio.h #define N 5 void swap(int *x, int *y) { int tmp *x; *x *y; *y tmp; } int main() { int arr[N]; int i, j; for (i 0; i N; i) scanf(%d, arr[i]); for (i 0; i N - 1; i) { for (j 0; j N - 1 - i; j) { if (arr[j] arr[j 1]) swap(arr[j], arr[j 1]); } } for (i 0; i N; i) printf(%d , arr[i]); printf(\n); return 0; }这段代码里我特意把交换写成了swap函数并且用指针传参。原因是三数版本里临时变量就写在原地问题不大但数组排序时交换会反复出现封装成函数能让主体逻辑更清楚。这里的int *x就是“指向数组元素的指针”*x *y相当于交换格子里的内容。看到C语言里*号在声明和赋值里含义不同很多初学者会懵但代码多看几遍就理解了声明里的*表示“这是一个指针”赋值里的*表示“取指针指向的值”。4.2 两层循环和三数排序的对应关系如果把N改成3把数组换回三个变量上面的冒泡循环本质上就是在反复执行三数版本里的那几个if。三数版的顺序是if (a b) swap; if (b c) swap; if (a b) swap;数组版的外层循环控制“总共要确定几个最大值”内层循环控制“这一趟一路比到哪个位置”。第一趟遍历后最大的数肯定被推到数组末尾第二趟就不用再比较最后一个元素了所以内层j的上界是N - 1 - i。当N3时第一趟比较arr[0]和arr[1]、arr[1]和arr[2]等价于三数版本的前两个if第二趟只比较arr[0]和arr[1]正好对应三数版本的第三个if。一一对应得严丝合缝。这个对应关系值得自己想一遍。初学者最常见的困惑是“为什么三数排序不用循环N个数就要用循环”答案其实很简单N个数时手工写比较和交换会淹没在你根本数不完的if里必须抽象成“对所有相邻对执行同一规则”的循环。循环不是新知识它只是替你把“重复劳动”打包了。4.3 从常数复杂度到O(n²)的一课三数排序无论输入什么比较次数固定为3可以认为时间开销是常数。但数组冒泡排序不是这样比较次数等于每一趟内层比较的次数之和大致是(N-1) (N-2) ... 1 N*(N-1)/2。用大O记号来表示就是O(n²)。说人话就是数据量翻倍时间会变成四倍左右。N100时比较将近5000次N1000时变成将近50万次N10000时就到5000万次了。这个量级在排序算法里属于“能跑但很慢”的类型。数据结构课程里后续会讲快排、归并这些O(n log n)的算法它们的出现正是为了解决冒泡排序在数据量变大时撑不住的问题。不过话说回来冒泡排序作为入门算法价值恰恰在于慢得直白。它用最直观的方式让你理解“比较、交换、有序”这三大核心要素。等你哪天真拿冒泡去排几十万条数据时自然会体会到为什么需要更聪明的算法那时候再学快排动力和理解深度都是完全不一样的。5. 实测踩坑实录从错误输出到正确结果的一次完整排查5.1 症状复现输入3 2 1输出2 1 3有个学员发来一段代码说“输入3 2 1输出却是2 1 3”代码长这样#include stdio.h int main() { int a, b, c, tmp; scanf(%d %d %d, a, b, c); if (a b) { tmp a; a b; b tmp; } if (b c) { tmp b; b c; c tmp; } printf(%d %d %d\n, a, b, c); return 0; }我拿到代码的第一反应不是看if写得对不对而是把三个变量画成格子手动推一遍。初始状态是a3b2c1。第一个if里32成立交换后a2b3c1。第二个if里b31成立交换后a2b1c3。程序结束输出2 1 3果然和学员说的一样。问题在哪就在第二个if交换完成之后a和b的大小关系已经变成了a2、b1又变成逆序了但代码里没有第三个if去重新整理a和b。也就是说程序只保证“第一对比较大数往右推了”没有保证推完之后左边那一对仍然有序。修复方式很简单在最后补一个if (a b)的交换或者干脆把第三个比较改成针对当前的a、b再处理一次。5.2 调试手段printf 大法 GDB 关键操作这种问题靠肉眼看代码也能发现但如果在更复杂的程序里就需要靠工具辅助了。我最常用的两个办法一个是printf大法一个是GDB。printf大法就是在可疑位置加打印语句把每一步的变量状态输出出来。比如在上面这个例子里可以在每个if后面加一行printf(after first if: a%d b%d c%d\n, a, b, c);跑一遍输入3 2 1程序会告诉你每一步之后a、b、c分别是什么。看到“第二个if之后a2 b1 c3”这一行问题立刻暴露。这个方法的优点是零学习成本、任何IDE都能用缺点是打印语句写完要记得删。如果想更系统地调试可以用GDB。在VS Code里配置好C语言环境后终端里gcc -g sort3.c -o sort3编译再用gdb ./sort3启动。常用操作就几个break main在main函数入口设断点print a查看变量next单步执行continue继续跑。在断点处观察每次交换前后三个变量的值能非常直观地看到“为什么第二个if之后a和b又乱了”。GDB上手成本不算高但一旦会用排查这类问题会快很多我认为值得在大一阶段就学会。5.3 一套值得长期保存的测试输入最后放一组我自己的测试用例。这组用例在之后的数组排序、字符排序、结构体排序里都可以复用只是把输入格式改一改就行用例名称输入覆盖点已有序1 2 3不能打乱原有顺序完全逆序3 2 1最考验交换次数带相等值2 2 1相等数据的稳定性全相等5 5 5边界分支含负数-8 4 -2负数参与比较极端值-2147483648 0 2147483647INT_MIN/INT_MAX输入不合法1 2scanf返回值应捕获以后写任何排序程序先把这张表跑一遍。跑过了心里就有底跑不过看哪一列挂了通常很快就能定位到是交换逻辑、比较方向还是输入处理的问题。我自己刷题这么多年依然保留着这种“测试用例随手带”的习惯因为在OJ上被一个极端数据判WA一次远比在本地补测一条用例浪费时间。最后讲点个人体会。三数排序我写了不知道多少遍每次给学员讲这道题我都会问一句你只求跑通还是要说清楚每一步为什么这样比较。能说出“我在把最小的往第一位放”或者“我在把最大的往后面冒”的人后面学数组排序几乎没有卡过壳只记代码、说不出依据的人十有八九会在冒泡和选择排序那节重新迷路。所以我真心建议看完这篇之后先拿纸笔手动跑一遍两种交换写法再上机敲代码最后把测试表格里的每一行都测一次。这套流程走完你对C语言里“变量、交换、分支、循环”这四个基础概念的掌握程度会明显上一个台阶。一个小技巧是如果你手头没有编译器就把代码里的三个变量想象成三个杯子交换的过程就是倒水必须多准备一个空杯子才能把两个杯子的水换过来——这个比喻能帮你避免绝大多数交换错误。