1. SORT 卡住的从来不是算法是汇编眼里“数据长什么样”如果你正准备交一个 MIPS MARS 的 sort 作业打开编辑器看到.data array: .word 3,10,8,2,5,2,3这句话大概率不是困惑算法怎么写而是困惑这串数字到底在哪里汇编里的“函数”要怎么调用有些同学能找到 sort 函数排序结构体的 C 代码也能把 C 版选择排序背得很熟可一旦落到 MIPS 里就发现自己手上只有寄存器、内存地址和一堆 label。我断断续续给不少初学汇编的人看过 SORT 这类的项目过程中发现一个普遍规律真正让大家卡住的从来不是排序逻辑本身而是“高级语言里已经封装好的东西到了 MIPS 里全部要自己摊开”。数组不是int[]没有自动的下标访问结构体没有类型系统只是一段固定长度的内存sort函数更不会从哪本标准库里冒出来帮你干活它必须是你自己写的 procedure或者你按规则跳转到一个函数入口。所以在折腾代码之前我建议先把问题倒过来不要以“我要写一个排序算法”为起点而是以“我要让 MARS 里的内存按顺序改变”为起点。只要把数据在内存里的存在形式看明白了SORT 这个项目就解决了一大半。1.1 一句 .word 到底做了什么MARS 是 MIPS Assembler and Runtime Simulator一个非常常用的 MIPS 教学模拟器。它启动后的内存布局很固定.text段从0x00400000开始.data段一般从0x10010000开始。也就是说你在源代码里写的.data array: .word 3, 10, 8, 2, 5, 2, 3并不是在 C 语言里那样“创建了一个数组”。它的实际动作是让汇编器在当前数据段位置依次预留 7 个 word每个 word 占 4 字节然后把这些初始值按顺序写进内存。array只是一个“符号地址”汇编器会把array解析成0x10010000这个地址也就是第一个数 3 存放的位置。所以原始数组在内存里的真实样子是下面这张表理解这张表比背循环重要得多数组下标内存地址存放的值00x10010000310x100100041020x10010008830x1001000C240x10010010550x10010014260x100100183看到规律了吗地址相差 4 的倍数。$t0是“数组下标”用sll $t4, $t0, 2把下标乘以 4再加到数组基地址$a0上就能得到对应元素的地址。这个“乘 4”是初学汇编时最容易漏掉的地方。很多人写 C 写惯了脑子里只有arr[i]到汇编里就直接add $t4, $a0, $t0结果拿下标当成了地址偏移量相当于把arr[1]读成了0x10010001这个地址上的内容自然不是你想要的数。建议你先在 MARS 中 Run 一下程序然后打开 Tools - Memory Contents把地址填成0x10010000你会直观看到这 7 个数确实一个挨一个存在内存里。看到这个画面之后再往下写代码心里就踏实了。1.2 为什么在 MIPS 里不能直接调一个现成 sort 函数MIPS 的教学环境里没有标准库即使有也只提供最基础的系统调用服务比如用syscall打印整数、读取字符串、退出程序。你不要指望能写出sort(array, 7)然后等着所有事情发生。在汇编里“函数”是一个带 label 的代码块它和普通代码唯一的区别是你用一个地址跳到那里执行完再用jr $ra跳回来。更准确地说连“函数”这个概念都是编译器给的底层只有jal、j、jr三条跳转指令。jal selection_sort的意思是把下一条指令的地址放进$ra然后跳到selection_sort这个 label 去执行。所以如果你想写一个可以被重复调用的排序代码就要遵守一套基本约定参数放哪里返回值放哪里哪些寄存器不能随便改递归或者嵌套调用时要不要往栈里保存现场。对于题目里常见的array: .word 3,10,8,2,5,2,3长度是 7我推荐的做法是至少写成两个部分main负责从.data取地址和长度然后调用排序函数排序函数只和$a0、$a1打交道不关心数组的符号名。这样代码路径清晰以后想排第二组数组只要换$a0、$a1就行。2. 用选择排序把一组数从数据段排成升序2.1 为什么选选择排序而不是冒泡SORT 这个项目通常不会对性能提出苛刻要求7 个数怎么排都是瞬间完成。但从汇编实现成本看排序算法之间的差异很明显。冒泡排序每一轮可能要交换很多次每一次交换都意味着至少两条sw插入排序由于要搬移元素也会产生大量内存操作。选择排序的思路最直观每一轮从剩下的元素里找到最小的那个记下它的下标本轮结束时只交换一次。在纯 C 里你可能不在乎多交换几次但在 MIPS 里交换涉及到lw和sw每多一次操作就多一个可能写错的地方。选择排序一轮最多一次交换总共最多 6 次交换逻辑上很简单for (i 0; i n - 1; i) { min_index i; for (j i 1; j n; j) { if (a[j] a[min_index]) { min_index j; } } swap(a[i], a[min_index]); }这个伪代码和 C 几乎没什么区别。真正要操心的是在 MIPS 里这个min_index不是一个变量而是一个寄存器a[j]也不是语法糖而是“基地址 j * 4”后lw出来的值。2.2 寄存器规划先把 C 循环翻成中间伪代码我写汇编前会先做一张寄存器分配表这比直接写指令省心得多。SORT 项目规模小没必要把所有变量都塞进$s寄存器使用临时寄存器$t就够了但必须分清楚每个寄存器在循环里负责什么变量或用途寄存器说明数组起始地址$a0参数从 main 传入数组长度 n$a1参数外层循环 i$t0每次递增 1内层循环 j$t1每次从 i1 开始当前最小元素下标 min_index$t2每一轮初始化成外层 i比较过程中的临时地址/数据$t4-$t7按需使用不跨循环保存依赖在 main 里数组长度应该用la $a0, array lw $a1, lengthlength是在.data里定义的一个 word不能直接把length当成立即数使用。你需要lw $a1, length从内存里取值或者干脆用li $a1, 7。我更推荐定义成变量因为以后改数据时只需要改.data不用改代码逻辑。2.3 selection_sort 完整实现与解释下面是可直接放进 MARS 跑通的完整代码。我刻意把它写成一个可以被调用的函数selection_sort而不只是在main里从头排到尾目的是让你以后扩展到结构体排序或另一个数组时更方便。.data array: .word 3, 10, 8, 2, 5, 2, 3 length: .word 7 space: .asciiz .text main: la $a0, array lw $a1, length jal selection_sort # 打印排序结果 la $s0, array lw $s1, length li $s2, 0 print_loop: bge $s2, $s1, print_done sll $t0, $s2, 2 add $t0, $s0, $t0 lw $a0, 0($t0) li $v0, 1 syscall la $a0, space li $v0, 4 syscall addi $s2, $s2, 1 j print_loop print_done: li $v0, 10 syscall # 函数selection_sort # 参数$a0 数组首地址, $a1 数组长度 # 说明就地升序排序无返回值 selection_sort: addi $t3, $a1, -1 # $t3 n - 1外层循环只需到 n-2 addi $t0, $zero, 0 # i 0 outer_loop: bge $t0, $t3, sort_done add $t2, $t0, $zero # min_index i addi $t1, $t0, 1 # j i 1 inner_loop: bge $t1, $a1, inner_done sll $t4, $t1, 2 # j * 4 add $t4, $a0, $t4 # array[j] lw $t5, 0($t4) # $t5 array[j] sll $t6, $t2, 2 # min_index * 4 add $t6, $a0, $t6 # array[min_index] lw $t7, 0($t6) # $t7 array[min_index] bge $t5, $t7, skip_update add $t2, $t1, $zero # min_index j skip_update: addi $t1, $t1, 1 j inner_loop inner_done: sll $t4, $t0, 2 add $t4, $a0, $t4 # array[i] lw $t5, 0($t4) # 暂存 array[i] sll $t6, $t2, 2 add $t6, $a0, $t6 # array[min_index] lw $t7, 0($t6) # 暂存 array[min_index] sw $t7, 0($t4) # array[i] array[min_index] sw $t5, 0($t6) # array[min_index] 原 array[i] addi $t0, $t0, 1 j outer_loop sort_done: jr $ra这段代码有几个细节值得说一下。bge $t0, $t3, sort_done里的bge是 MARS 支持的伪指令如果第一个操作数大于等于第二个操作数就跳转。刚开始学 MARS 的人总以为只能写beq、bne、blt这些基本指令其实 MARS 默认开启了扩展伪指令支持bge这类写法完全可以用。bge $t5, $t7, skip_update的意思是如果array[j]不小于当前最小值就不更新min_index。很多同学在 C 里写if (a[j] a[min_index])翻成汇编时容易把条件颠倒成“小于才跳”结果找出来的不是最小值而是最大值整段排序变成降序甚至乱序。这里我的建议是先在纸上写出这一句的比较方向和跳转方向再落到代码里。排序完成后main 里的打印循环会输出2 2 3 3 5 8 10这个结果其实就是原始数组3,10,8,2,5,2,3的最终正确形态。3. MARS 上排了一晚上五个真实翻车现象代码看起来不复杂但只要你在 MARS 里动过手一定碰到过“编译不报错、运行也不崩溃、输出却永远不符合预期”的情况。我帮过不少同学定位 SORT 的 bug下面这些现象基本可以覆盖初学阶段八成的问题。3.1 翻车一sw的基址算错排了半天改的是别的内存这是最常见也最隐蔽的错误。很多人知道要取array[j]必须用sll乘 4但写着写着就把内层循环的地址计算写成了同一个寄存器比如add $t4, $a0, $t4 # 这里 $t4 已经是 j*4没问题 sw $t5, 0($t4) # 但你后来又对 $t4 做了修改或者误用了 $t6一旦交换时的基址寄存器不是元素真正所在的地址sw依然能正常写不会报 “address out of range”。结果就是排序没有改变数组数据。排查这种问题最有效的方法是排序结束之后打开 MARS 的 Memory Contents看0x10010000附近的数据是否变化。如果数据完全没动就说明sw从来就没写到你认为的地址如果数据变了但不是排序效果就说明地址计算链路里某个寄存器的值在比较和交换之间被另一次运算覆盖了。3.2 翻车二地址越界程序输出一个巨大且莫名其妙的数MARS 在访问非法地址时通常会弹窗提示“Runtime exception at 0x...: address out of range”但有些同学的内存访问没有越到规则之外只是访问了一个尚未定义的、包含随机值的 data 区域程序就能继续跑最后输出一个巨大正数或负数。这种越界通常来自 length 用错。比如.word数组长度是 7却因为.data里下面的标签或注释干扰导致lw $a1, length取到的不是 7。另一个原因是排序结束后打印循环里的$t0地址计算和排序循环共享之后又被某个临时指令覆盖于是打印循环访问到数组末尾之外。我自己的经验是在打印循环里使用一组固定的$s寄存器核心变量存入后不要随意复用。主程序里调用jal之前最好把需要保留的地址和长度放在$s0、$s1里不要放在$t里指望调用之后原封不动。3.3 翻车三比较方向反了得到降序还觉得是题目要求MIPS 里没有这样的高级操作符只能靠bge、blt、bgt等指令组合。排序核心代码里这一行的方向非常容易写反bge $t5, $t7, skip_update它的意思是“如果array[j] array[min_index]就不更新”。这是升序。如果你把它误写成ble或blt内层循环每次都会把min_index更新成当前较大的那个下标最后交换时就会把大的数挪到前面得到降序。还有一种情况是输出确实是升序但题目要的是降序。那就把所有比较方向整体反过来即可。这里有一个小技巧不要只改bge那一行要同时检查外层循环和交换有没有依赖“最小值”这个语义否则可能会做出一个既不是升序也不是降序的混乱序列。3.4 翻车四循环里某个寄存器被后续指令冲掉我见过一个同学的代码外层循环的i存放在$t0结果在计算array[j]地址时他也用$t0作为临时寄存器。于是内层循环每执行一轮i都会被覆盖成某个临时值外层循环次数完全失控出现死循环或者一组数据反复交换。在 MIPS 里没有“变量名保护”$t0只是一个编号同一个寄存器可以在代码不同位置代表完全不同的含义。因此寄存器分配表越简单越好。我的选择是整个排序函数里外层i用$t0内层j用$t1min_index用$t2其余$t4之后全部当作临时地址和临时数据绝对不去碰$t0到$t2。这样即使后面代码写多了也不太会互相干扰。3.5 翻车五调用者寄存器压栈没有做嵌套调用后现场全丢许多示例代码为了展示“函数”会把 main 里的地址也存在$t寄存器然后调用sort。如果sort内部又调用了别的输出函数或者使用jal调用了自己的子程序$ra就会被覆盖。第一次调用结束后还能正常返回第二次可能就跳到了奇怪的地方。如果你是初学者我建议先不要做成复杂的嵌套结构main里用$s寄存器排序函数作为叶子函数内部不再调用任何其他函数。函数结束时jr $ra。等上述逻辑跑通之后再改成标准的压栈调用addiu $sp, $sp, -4 sw $ra, 0($sp) ... jal selection_sort ... lw $ra, 0($sp) addiu $sp, $sp, 4 jr $ra这串代码能够保护返回地址但前提是你真的需要嵌套调用。如果没有嵌套先不要随便往栈里塞东西减少变量。4. 从整数数组到结构体排序sort 怎么排一整块数据SORT 项目做到后面很多人会碰到结构体排序的需求。热搜里也经常出现“sort 函数排序结构体”这种词。其实这个概念放到 MIPS 里特别清晰因为汇编阶段根本没有“结构体类型”只有“一块连续内存以及由你定义怎么切分它”。4.1 MIPS 没有结构体但结构体数组只是一段有规律的字节高级语言里的struct会给每个字段分配固定偏移。比如typedef struct { int id; int score; } Student;如果按这个结构体定义数组每个 Student 占 8 字节id在内存地址偏移 0 处score在偏移 4 处。在 C 里直接写stu[i].score时编译器背后做的就是先计算stu的首地址加上i * sizeof(Student)再取偏移 4 处的数据。在 MIPS 里没有编译器替你算这些所以你必须自己定义“记录的大小”和“字段的偏移”。比刚才那个学生记录再简单点用两个 word 表示.data .align 2 students: .word 2, 78 # 学号 2成绩 78 .word 5, 93 # 学号 5成绩 93 .word 1, 65 # 学号 1成绩 65 n: .word 3这里每个记录占 8 字节。如果我要按成绩排序那么需要在比较的时候把两个记录的score字段取出来比也就是每个记录地址偏移 4 处。换成 MIPS 代码比较核心大概是# 记录下标存在 $t1记录基地址存在 $a0 sll $t4, $t1, 3 # 记录下标 * 8因为每个记录 8 字节 add $t4, $a0, $t4 # students[$t1] lw $t5, 4($t4) # 取 score因为 score 在偏移 4这行lw $t5, 4($t4)是整个结构体排序和整数数组排序的分界点。排整数数组时偏移是 0排记录时偏移变成你要比较的字段位置。其余循环和交换逻辑基本可以沿用选择排序但交换时不能在只交换两个 word而是需要把整个记录都搬到临时寄存器再写回去。8 字节的记录可以一次处理两个 word如果记录更大循环内存拷贝反而更清晰。4.2 给结构体数组排序时比较器和交换的数据块很多人在 C 里用sort函数排序结构体时只写一个比较函数交换由sort内部自动完成。但在汇编里“比较”和“交换”都摆在明面上。比较要写明字段偏移交换要把记录大小考虑进去。刚才那个 8 字节记录的下标 i 和 min_index 交换可以写成# $t0 是外层 i$t2 是 min_index$a0 是数组首地址 sll $t4, $t0, 3 # i * 8 add $t4, $a0, $t4 sll $t6, $t2, 3 # min_index * 8 add $t6, $a0, $t6 # 暂存 students[i] lw $t8, 0($t4) lw $t9, 4($t4) # 暂存 students[min_index] lw $t5, 0($t6) lw $t7, 4($t6) # 写回 sw $t5, 0($t4) sw $t7, 4($t4) sw $t8, 0($t6) sw $t9, 4($t6)通过这段代码你可以直观看到所谓“排序结构体”本质上就是两件事一是按哪个偏移位比较二是按多大步长整块搬运。只要这两点想清楚无论排的是 2 个 word 的记录还是 20 个字段的记录思路都一致。4.3 回到高级语言C 的 qsort、C 的 std::sort如果你已经理解了汇编里的“比较器”思想再去看高级语言中的sort函数会发现内核一样。C 标准库里没有自带名为sort的函数最接近的是qsort它本身不关心你排的是 int、double 还是结构体它只认四个参数数组首地址、元素个数、每个元素占多少字节、以及一个比较函数指针。#include stdio.h #include stdlib.h typedef struct { int id; int score; } Student; int cmp(const void *a, const void *b) { const Student *sa (const Student *)a; const Student *sb (const Student *)b; if (sa-score ! sb-score) { return sa-score sb-score ? -1 : 1; } return sa-id - sb-id; } int main(void) { Student stu[3] {{2, 78}, {5, 93}, {1, 65}}; qsort(stu, 3, sizeof(Student), cmp); return 0; }qsort底层会根据比较函数返回值的正负来确定顺序本质上就是在做我们上面手写的那一套“比较字段、交换记录”。而 C 里的std::sort也同理只是比较部分通常可以写成函数对象或 lambda#include algorithm #include vector struct Student { int id; int score; }; std::vectorStudent stu {{2, 78}, {5, 93}, {1, 65}}; std::sort(stu.begin(), stu.end(), [](const Student a, const Student b) { if (a.score ! b.score) { return a.score b.score; } return a.id b.id; });看清这层关系后你在 MIPS 里手写结构体排序就不会