最近帮人调试 MIPS MARS 的汇编实验消息发过去半天没动静最后回了一句“SORT 到底要不要用 sort 函数”我一听就明白他卡住的不是 Python 里那个list.sort()也不是 C 里std::sort而是mips mars环境下手写排序指令。题目给得很干就一段.dataarray: .word 3, 10, 8, 2, 5, 2, 3剩下的全靠自己发挥。后来我又在答疑群里看到有人问“sort函数排序结构体”的报错问题才知道这个看似普通的排序题其实横跨了高级语言和汇编两层。今天就把这一整套思路完整复盘一遍从 MARS 里.word数组怎么在内存中摆放到手写冒泡排序时寄存器如何分配再到 C/C 里 sort 函数排序结构体为什么舒服最后说说我实际调试中踩过的坑。我先说结论SORT 在高级语言里是一个被你调用的函数在 MIPS 实验里是一段你必须自己写出来的循环。前者让人写得舒心后者逼你看清一件事——数组下标在硬件眼里只是“基地址 偏移量”。想两头都通最好的办法就是拿 MARS 亲手翻译一遍冒泡排序。1. 从一道“用 MARS 给数组排序”的题说起1.1 这道题并不只是“给数据排个序”题目原文往往只有类似这样的片段.data array: .word 3,10,8,2,5,2,3没有给你n也没有告诉你数组长度是多少。很多人第一反应是“这还不简单冒泡排序呗”但真到了 MIPS 指令层面你会发现自己连“取出第 j 个元素”这句话都要想一会儿。在高级语言里写a[j]编译器会帮你把它翻译成取数组首地址把 j 乘以元素大小首地址加上这个偏移量从算出来的地址读取或写入。到了 MIPS 汇编这四步每一步都是显式指令。更麻烦的是题目到底要你写成什么样通常还藏着两个潜台词你要写出数据段声明不能从键盘输入排序结果要么在内存里可观察要么用 syscall 打印到控制台。所以这个题目真正想考的不是“你会不会排序算法”而是“你懂不懂内存寻址、寄存器分配、分支循环控制”这三件套。1.2 在写汇编前先把 C 语言的模板固定下来我习惯先写一个最朴素的 C 版本作为翻译底稿。不搞花活就用冒泡排序因为它的双层循环和交换操作最简单翻译成汇编时不容易绕晕int array[7] {3, 10, 8, 2, 5, 2, 3}; int n 7; for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (array[j] array[j 1]) { int temp array[j]; array[j] array[j 1]; array[j 1] temp; } } }这段代码本身没什么可讲的但它把两个关键信息写死了外层循环的边界是n - 1不是n内层循环的边界是n - 1 - i每一轮都比上一轮少比较一次。这两个条件如果翻译错了程序大概率要么漏排要么在 MARS 里出现数组越界访问。关键是MARS 不会像高级语言那样温柔地告诉你“数组越界”它只会给你一个莫名其妙的运行结果或者直接报地址异常。1.3 汇编和 C 的分岔路下标不是下标是地址这是从高级语言切到汇编时最重要的一次思维转换。在 C 语言里array[j]是个“值”你不需要关心它住在哪个地址。到了 MIPS 中数组就是一排连续内存单元每个.word占 4 字节。取array[j]需要这样思考数组的启动地址存到某个寄存器比如$s0j存在另一个寄存器里array[j]的地址是$s0 j * 4乘法尽量用移位指令j * 4等价于j 2。举个生活化的例子一排连续的快递柜编号从 0 开始每个柜子占 4 个门牌宽度。你说“取第 3 个柜子”如果只看门牌号你得从第 0 个柜子的位置出发向后走 12 个门牌宽度才是第 3 个柜子。高级语言的array[3]帮你把这个 12 算好了汇编里你必须自己做这个乘法。2..data段与运行时内存数组的“住址”到底长什么样2.1 数据声明并不等于数组初始化.word 3, 10, 8, 2, 5, 2, 3这一段看起来像 C 语言的初始化列表其实它是一个“内存布局声明”。MARS 会把这 7 个 32 位整数依次放进数据段默认起始地址通常在0x10010000附近。每个.word占 4 字节所以这段数组一共占 28 字节数组下标值相对字节偏移03011042883212451652206324如果你在 MARS 里打开 Tools → Data Segment Viewer运行前就可以看到内存里这 7 个.word的内容。但注意MARS 默认显示的是十六进制所以3会显示成0x0000000310会显示成0x0000000a不要以为是数据错了。2.2 用地址偏移理解array[i]MIPS 里没有“数组变量”这种概念只有“标签”。array这个标签的本质是一个地址它是数据段中那块连续内存的起点。当代码写la $s0, array时$s0就保存了这个起始地址。之后想取第j个元素普通做法是用累加器构造地址sll $t4, $t2, 2 # $t4 j * 4 add $t4, $s0, $t4 # $t4 array基址 j * 4 lw $t5, 0($t4) # $t5 array[j]这里sll是逻辑左移左移 2 位就等于乘 4因为.word是 4 字节。如果要访问array[j1]不需要重新算一遍地址直接在当前地址上加 4 就行lw $t6, 4($t4) # $t6 array[j1]lw指令的第二个操作数4($t4)意思是从$t4 4这个地址读取一个字。这种“基址 偏移量”的寻址方式是 MIPS 中最常见的访存姿势也是理解结构体字段访问的基础。2.3 我建议你先在 MARS 里观察一遍内存不要急着写完整排序代码。我第一次做这个实验时直接写完跑了一遍发现输出不对但又不知道数据到底变成什么样了。后来学会一个更高效的方法先只写数据声明再在代码里用la $s0, array加载地址随便加几条lw然后在 Data Segment Viewer 里看地址变化。具体操作可以这样在 MARS 中打开.asm文件先不要运行打开 Tools → Data Segment Viewer单步执行到la $s0, array之后看$s0的值再单步执行lw $t5, 0($t4)看$t5是否等于你脑海中预期的元素值。这一步能帮你建立“标签 → 地址 → 数据”的映射关系。如果直接把循环写完才发现问题你会很难排查是算法出错、寻址出错还是寄存器被覆盖了。3. 冒泡排序翻译成 MIPS寄存器分配的博弈3.1 动手翻译前先定寄存器分工写汇编最忌讳边写边想寄存器用哪个写完才发现同一个寄存器被两个循环变量用脏了。我一般先列一张寄存器分配表寄存器用途说明$s0array 基地址排序过程中不变$s1n数组长度$t0i外层循环变量$t1n - 1外层循环比较用$t2j内层循环变量$t3n - i - 1内层循环边界$t4当前元素地址array[j] 的地址$t5array[j]第一个值$t6array[j1]第二个值这里把数组基址放$s0、长度放$s1是因为它们在循环中需要存活很久。$t系列寄存器作为临时寄存器在内层循环里反复使用没有问题。虽然 main 里没有调用别的函数但提前养成“长寿变量放$s临时变量放$t”的习惯后面写含jal的子程序时会少踩很多坑。3.2 完整可运行的 MARS 代码下面这份代码是用冒泡排序对数组升序排列并把结果输出到控制台。直接复制到 MARS 里可以运行.data array: .word 3, 10, 8, 2, 5, 2, 3 space: .asciiz .text .globl main main: la $s0, array # 数组基地址 li $s1, 7 # 数组长度 li $t0, 0 # i 0 outer_loop: addi $t1, $s1, -1 # n - 1 bge $t0, $t1, print_array # i n - 1 时排序结束 li $t2, 0 # j 0 sub $t3, $s1, $t0 addi $t3, $t3, -1 # n - i - 1 inner_loop: bge $t2, $t3, outer_next # j n - i - 1 时外层循环加 1 sll $t4, $t2, 2 add $t4, $s0, $t4 # $t4 array[j] lw $t5, 0($t4) # $t5 array[j] lw $t6, 4($t4) # $t6 array[j 1] ble $t5, $t6, no_swap # 如果前者 后者不用交换 sw $t6, 0($t4) # array[j] array[j 1] sw $t5, 4($t4) # array[j 1] temp no_swap: addi $t2, $t2, 1 # j j inner_loop outer_next: addi $t0, $t0, 1 # i j outer_loop print_array: li $t0, 0 # 重新用 i 做输出循环变量 print_loop: bge $t0, $s1, exit # i n 时结束输出 sll $t4, $t0, 2 add $t4, $s0, $t4 lw $a0, 0($t4) # 要打印的数字 li $v0, 1 syscall # print_int la $a0, space li $v0, 4 syscall # print_string addi $t0, $t0, 1 j print_loop exit: li $v0, 10 syscall # 退出程序运行后控制台会输出2 2 3 3 5 8 10原数组里有两个2、两个3这个结果说明排序成功。你可以在 MARS 里点单步执行每一步对比寄存器和内存的变化尤其是$t5与$t6在交换前后的值。3.3 为什么内层循环边界要写成n - i - 1很多人翻译冒泡时会把内层循环写成j n - 1这样不是不行但每一轮都会多做无用功。冒泡排序的核心思想是每一轮把当前未排序区间的最大值“冒”到最后面。数组长度为n第一轮需要比较相邻元素n - 1次第二轮时最后一个元素已经是全局最大不需要再碰它所以只需要比较n - 2次。外层变量i每加 1内层可比较次数就减 1因此边界是n - 1 - i。在 C 语言里for 循环的条件通常写j n - 1 - i所以循环变量j的最大取值为n - 2 - i。而汇编代码中我用bge判断“当 j 大于等于边界时跳出”所以这里的$t3要设成n - i - 1而不是n - i - 2。这是最容易出 off-by-one 错误的地方。提示写汇编循环之前先在草稿纸上把 C 语言循环的“退出条件”翻译成“跳转条件”。j limit等效于“当 j limit 时跳出”所以判断用bge而不是blt。3.4 关于伪指令MARS 很方便但你要知道它帮你做了什么上面代码里出现了la、bge、ble这些其实都不是 MIPS 的“真指令”而是 MARS 汇编器提供的伪指令。la $s0, array会被展开成luiori因为 32 位地址不能直接塞进一条指令里bge和ble最终会被翻译成sltbeq/bne的组合。如果只是交 MARS 实验用伪指令完全没问题。但如果你以后接触真实 MIPS 机器或模拟器里的“延迟分支”就要注意这些伪指令的展开方式可能影响你对指令数的判断。我个人建议初学阶段先在 MARS 里看“Execute”窗口把伪指令展开后的真实指令浏览一遍哪怕记不住也要知道它们并不是一条指令。这能解释为什么有些代码在 MARS 里能跑在课上讲的概念模型里看指令流程却对不上。4. 当排序对象从数组变成结构体sort 函数的“舒服”不是白来的4.1 结构体排序到底在排什么数组排序只是热身真正让很多人翻车的是结构体排序。比如学生信息struct Student { char name[16]; int score; int age; };现在给你一个struct Student数组想按score从低到高排序。高级语言写起来很清爽C 里可以是#include algorithm #include vector using namespace std; struct Student { char name[16]; int score; int age; }; vectorStudent students; sort(students.begin(), students.end(), [](const Student a, const Student b) { return a.score b.score; });这里真正改变的是什么比较规则变了。数组中的元素从一个 4 字节整数变成了一个 24 字节左右的结构体排序时需要“整体搬运”每个结构体。如果回到 MIPS 汇编你要做的事就复杂得多用基址加偏移访问score字段比较两个score交换两个完整的结构体不只是交换一个字。4.2 qsort 的比较函数为什么要用地址同学们常说的“sort函数排序结构体”在 C 语言里更准确的说法其实是qsort#include stdlib.h int cmp_by_score(const void *a, const void *b) { const struct Student *sa (const struct Student *)a; const struct Student *sb (const struct Student *)b; return (sa-score sb-score) - (sa-score sb-score); } qsort(students, count, sizeof(struct Student), cmp_by_score);为什么qsort第四参数要传一个函数指针因为在 C 语言里排序函数不知道你的结构体长什么样也不知道你想按分数还是年龄排序。它只负责一件事根据比较结果把内存块搬来搬去。具体“怎么比较”由你写的比较函数告诉它。这其实就是把第 3 节 MIPS 代码里的ble $t5, $t6, no_swap这一句抽象成了回调函数。排序框架只负责循环和交换比较规则通过函数指针注入。在底层qsort拿到两个元素的地址调用你的比较函数根据返回值决定是否交换。如果你把比较函数写错比如强转类型不对或者返回逻辑写反排序结果就会南辕北辙。4.3 汇编视角下的结构体字段访问很多学过 C 结构体但没写过汇编的人不知道结构体在内存里就是一块连续存储区。下面的结构体struct Student { char name[16]; int score; int age; };它在内存里的布局大致是字段偏移量大小name016 字节score164 字节age204 字节合计24 字节如果score字段的偏移量是 16那么访问某个结构体数组第j个元素的score等于结构体首地址 j * 24 16这里的元素大小是 24不再是 4。交换两个结构体时如果只像整数排序那样交换一个lw那就只把前 4 个字节换了后面 20 个字节原封不动数据直接错乱。正确做法要么按 4 字节一块循环搬 6 次要么用专门的内存块拷贝过程。这就是为什么“sort函数排序结构体”在高级语言里看起来简单——标准库帮你处理了元素大小和字节搬移。但代价是你得搞清楚比较函数怎么写。4.4 顺便补一个稳定性知识点如果你用 C 的std::sort它不保证相等元素在排序后维持原有顺序。对于只有数值的数组稳定性无所谓但对于结构体如果先按name排好序再按score排序你可能会期望同样的score之间保留原来的相对顺序。这时候应该用std::stable_sort它和std::sort的参数几乎一样但能保证稳定性。回到 MIPS 冒泡排序里稳定性取决于你交换的条件到底用还是。只用“大于”交换相等元素就不会被打乱用“大于等于”交换相等元素的先后顺序会被反转。很多初学者在汇编里写排序时没注意这个细节结果在普通整数数组上完全看不出来等后面数据结构做链式结构排序时才发现问题。5. 我自己在 MARS 里踩过的三个坑5.1 忘记给偏移量乘 4导致排序结果像“隔一个换一个”这个坑我见过太多次了。有些同学把 C 语言里array[j]想成“从数组开头数 j 个位置”然后直接写add $t4, $s0, $t2 # 错误没有把 j 乘以 4 lw $t5, 0($t4)这样$t4只是array起始地址加上 j而不是加上j * 4。数组里每个.word占 4 字节你等于每次只跳过一个字节读取了一个完整字的 4 个字节中的某一部分。结果是排序过程看起来在跑但数据像被“打乱”了一样。正确做法是乘法用移位sll $t4, $t2, 2 add $t4, $s0, $t4提示不要写mul指令吗MARS 支持mul但整数乘 4 这种常量乘法编译器都会优化成sll。初学阶段最好直接养成“看变量类型决定移位量”的习惯。5.2 交换时寄存器互相覆盖另一个经典错误是交换逻辑写成了# 错误示例 lw $t5, 0($t4) # $t5 array[j] lw $t6, 4($t4) # $t6 array[j1] sw $t5, 0($t4) # array[j] $t5 sw $t6, 4($t4) # array[j1] $t6这段看起来是对的但如果有人在第一条sw之前把其中一个值存到了被覆盖的内存位置然后才把另一个值存过去就会出现覆盖问题。比如# 也是错误示例 sw $t5, 4($t4) # 先把靠前的值写到后面 lw $t5, 0($t4) # 再读前面这里读到的已经不是 array[j] 了标准交换必须先把两个值都装入寄存器再执行两次sw。寄存器$t5和$t6必须是两个不同的寄存器千万不能都用$t5。5.3 循环边界写成n导致越界读取如果内层循环没有限制在“当前未排序区间”而是傻傻地每次都从 0 跑到n - 1那么当 j 等于n - 1时array[j 1]会访问到数组末尾再追加 4 字节的地方。这段内存不属于你的数组可能是其他数据也可能是未定义的。运气好时程序不崩但排序结果中会出现一个莫名其妙的“大数”运气不好时 MARS 直接报地址异常。我建议你在写内层循环前先把这三样东西写清楚内容值数组长度 n7外层 i 的取值范围0 ~ 5内层 j 的取值范围0 ~ 5 - i然后每次检查bge跳转条件时拿n7、i0的情况心算一遍。循环边界正确程序不一定对但循环边界错了程序基本必挂。5.4 用 syscall 输出前记得设置$v0MARS 里系统调用依赖寄存器传入功能号。打印整数要li $v0, 1打印字符串要li $v0, 4退出程序要li $v0, 10。有的同学在调试时会打断点看$a0的值但发现输出的数字总是不对往往是因为之前的syscall改掉了$v0或者往$v0里写了一个中间结果。如果输出循环里需要在整数和空格字符串之间切换最稳妥的方式是每次 syscall 前重新设置$v0。虽然看起来啰嗦但能避免不少“明明数据排对了显示出来却是乱码”的尴尬。6. 从手写 SORT 到理解标准库我最终收获了什么整轮折腾下来我对“排序”这两个字有了完全不同的理解。以前用 C 写std::sort排结构体我只把它当工具从来没想过为什么可以传一个 lambda 进去。后来写了 MIPS 版排序才意识到标准库的 sort 本质是一个“排序框架”它需要的只是元素地址、元素大小和比较规则。比较规则可以通过函数指针、仿函数、lambda 注入所以一套排序代码可以处理整数、字符串、结构体甚至任意自定义类型。反过来汇编排序让我理解了内存连续性对算法效率的影响。数组元素按顺序排布时支持通过基址加偏移随机访问这让冒泡排序的实现成为可能。如果换成链表冒泡排序在 MIPS 里就要一遍一遍地通过lw加载 next 指针代码结构和数组版本完全不同。这也是为什么很多数据结构课程会强调“物理结构决定操作效率”。如果你现在也在做 MIPS MARS 的 SORT 题目我不建议直接背代码。更好的做法是先跑通上面的完整程序然后尝试做三个小改动把数组改成降序排列观察代码里哪些地方要改把长度从固定 7 改成.word一个变量再用li $s1, 7加载体会数据段和指令段的分离把排序部分封装成一个sort过程主程序用jal sort调用练习参数传递和返回地址保存。第三个改动会逼你想清楚一个问题如果sort过程内部又会调用其他过程$ra寄存器还能不能安全使用这就涉及栈帧了也是 MIPS 实验里比 SORT 本身更有价值的下一课。我自己在带这个题目的过程中最深的体会是能让你真正把高级语言里的排序函数和汇编里的排列指令打通的办法不是看标准库源码而是亲手写一遍那个最笨的冒泡排序。写完再回头看sort函数你会觉得它没那么神奇反而更清楚它替我们省了多少事。 
长河君 · 2026/9/8 18:09:06 · 阅读 1.2k MIPS MARS手写排序：从冒泡汇编到理解sort函数
最近帮人调试 MIPS MARS 的汇编实验消息发过去半天没动静最后回了一句“SORT 到底要不要用 sort 函数”我一听就明白他卡住的不是 Python 里那个list.sort()也不是 C 里std::sort而是mips mars环境下手写排序指令。题目给得很干就一段.dataarray: .word 3, 10, 8, 2, 5, 2, 3剩下的全靠自己发挥。后来我又在答疑群里看到有人问“sort函数排序结构体”的报错问题才知道这个看似普通的排序题其实横跨了高级语言和汇编两层。今天就把这一整套思路完整复盘一遍从 MARS 里.word数组怎么在内存中摆放到手写冒泡排序时寄存器如何分配再到 C/C 里 sort 函数排序结构体为什么舒服最后说说我实际调试中踩过的坑。我先说结论SORT 在高级语言里是一个被你调用的函数在 MIPS 实验里是一段你必须自己写出来的循环。前者让人写得舒心后者逼你看清一件事——数组下标在硬件眼里只是“基地址 偏移量”。想两头都通最好的办法就是拿 MARS 亲手翻译一遍冒泡排序。1. 从一道“用 MARS 给数组排序”的题说起1.1 这道题并不只是“给数据排个序”题目原文往往只有类似这样的片段.data array: .word 3,10,8,2,5,2,3没有给你n也没有告诉你数组长度是多少。很多人第一反应是“这还不简单冒泡排序呗”但真到了 MIPS 指令层面你会发现自己连“取出第 j 个元素”这句话都要想一会儿。在高级语言里写a[j]编译器会帮你把它翻译成取数组首地址把 j 乘以元素大小首地址加上这个偏移量从算出来的地址读取或写入。到了 MIPS 汇编这四步每一步都是显式指令。更麻烦的是题目到底要你写成什么样通常还藏着两个潜台词你要写出数据段声明不能从键盘输入排序结果要么在内存里可观察要么用 syscall 打印到控制台。所以这个题目真正想考的不是“你会不会排序算法”而是“你懂不懂内存寻址、寄存器分配、分支循环控制”这三件套。1.2 在写汇编前先把 C 语言的模板固定下来我习惯先写一个最朴素的 C 版本作为翻译底稿。不搞花活就用冒泡排序因为它的双层循环和交换操作最简单翻译成汇编时不容易绕晕int array[7] {3, 10, 8, 2, 5, 2, 3}; int n 7; for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (array[j] array[j 1]) { int temp array[j]; array[j] array[j 1]; array[j 1] temp; } } }这段代码本身没什么可讲的但它把两个关键信息写死了外层循环的边界是n - 1不是n内层循环的边界是n - 1 - i每一轮都比上一轮少比较一次。这两个条件如果翻译错了程序大概率要么漏排要么在 MARS 里出现数组越界访问。关键是MARS 不会像高级语言那样温柔地告诉你“数组越界”它只会给你一个莫名其妙的运行结果或者直接报地址异常。1.3 汇编和 C 的分岔路下标不是下标是地址这是从高级语言切到汇编时最重要的一次思维转换。在 C 语言里array[j]是个“值”你不需要关心它住在哪个地址。到了 MIPS 中数组就是一排连续内存单元每个.word占 4 字节。取array[j]需要这样思考数组的启动地址存到某个寄存器比如$s0j存在另一个寄存器里array[j]的地址是$s0 j * 4乘法尽量用移位指令j * 4等价于j 2。举个生活化的例子一排连续的快递柜编号从 0 开始每个柜子占 4 个门牌宽度。你说“取第 3 个柜子”如果只看门牌号你得从第 0 个柜子的位置出发向后走 12 个门牌宽度才是第 3 个柜子。高级语言的array[3]帮你把这个 12 算好了汇编里你必须自己做这个乘法。2..data段与运行时内存数组的“住址”到底长什么样2.1 数据声明并不等于数组初始化.word 3, 10, 8, 2, 5, 2, 3这一段看起来像 C 语言的初始化列表其实它是一个“内存布局声明”。MARS 会把这 7 个 32 位整数依次放进数据段默认起始地址通常在0x10010000附近。每个.word占 4 字节所以这段数组一共占 28 字节数组下标值相对字节偏移03011042883212451652206324如果你在 MARS 里打开 Tools → Data Segment Viewer运行前就可以看到内存里这 7 个.word的内容。但注意MARS 默认显示的是十六进制所以3会显示成0x0000000310会显示成0x0000000a不要以为是数据错了。2.2 用地址偏移理解array[i]MIPS 里没有“数组变量”这种概念只有“标签”。array这个标签的本质是一个地址它是数据段中那块连续内存的起点。当代码写la $s0, array时$s0就保存了这个起始地址。之后想取第j个元素普通做法是用累加器构造地址sll $t4, $t2, 2 # $t4 j * 4 add $t4, $s0, $t4 # $t4 array基址 j * 4 lw $t5, 0($t4) # $t5 array[j]这里sll是逻辑左移左移 2 位就等于乘 4因为.word是 4 字节。如果要访问array[j1]不需要重新算一遍地址直接在当前地址上加 4 就行lw $t6, 4($t4) # $t6 array[j1]lw指令的第二个操作数4($t4)意思是从$t4 4这个地址读取一个字。这种“基址 偏移量”的寻址方式是 MIPS 中最常见的访存姿势也是理解结构体字段访问的基础。2.3 我建议你先在 MARS 里观察一遍内存不要急着写完整排序代码。我第一次做这个实验时直接写完跑了一遍发现输出不对但又不知道数据到底变成什么样了。后来学会一个更高效的方法先只写数据声明再在代码里用la $s0, array加载地址随便加几条lw然后在 Data Segment Viewer 里看地址变化。具体操作可以这样在 MARS 中打开.asm文件先不要运行打开 Tools → Data Segment Viewer单步执行到la $s0, array之后看$s0的值再单步执行lw $t5, 0($t4)看$t5是否等于你脑海中预期的元素值。这一步能帮你建立“标签 → 地址 → 数据”的映射关系。如果直接把循环写完才发现问题你会很难排查是算法出错、寻址出错还是寄存器被覆盖了。3. 冒泡排序翻译成 MIPS寄存器分配的博弈3.1 动手翻译前先定寄存器分工写汇编最忌讳边写边想寄存器用哪个写完才发现同一个寄存器被两个循环变量用脏了。我一般先列一张寄存器分配表寄存器用途说明$s0array 基地址排序过程中不变$s1n数组长度$t0i外层循环变量$t1n - 1外层循环比较用$t2j内层循环变量$t3n - i - 1内层循环边界$t4当前元素地址array[j] 的地址$t5array[j]第一个值$t6array[j1]第二个值这里把数组基址放$s0、长度放$s1是因为它们在循环中需要存活很久。$t系列寄存器作为临时寄存器在内层循环里反复使用没有问题。虽然 main 里没有调用别的函数但提前养成“长寿变量放$s临时变量放$t”的习惯后面写含jal的子程序时会少踩很多坑。3.2 完整可运行的 MARS 代码下面这份代码是用冒泡排序对数组升序排列并把结果输出到控制台。直接复制到 MARS 里可以运行.data array: .word 3, 10, 8, 2, 5, 2, 3 space: .asciiz .text .globl main main: la $s0, array # 数组基地址 li $s1, 7 # 数组长度 li $t0, 0 # i 0 outer_loop: addi $t1, $s1, -1 # n - 1 bge $t0, $t1, print_array # i n - 1 时排序结束 li $t2, 0 # j 0 sub $t3, $s1, $t0 addi $t3, $t3, -1 # n - i - 1 inner_loop: bge $t2, $t3, outer_next # j n - i - 1 时外层循环加 1 sll $t4, $t2, 2 add $t4, $s0, $t4 # $t4 array[j] lw $t5, 0($t4) # $t5 array[j] lw $t6, 4($t4) # $t6 array[j 1] ble $t5, $t6, no_swap # 如果前者 后者不用交换 sw $t6, 0($t4) # array[j] array[j 1] sw $t5, 4($t4) # array[j 1] temp no_swap: addi $t2, $t2, 1 # j j inner_loop outer_next: addi $t0, $t0, 1 # i j outer_loop print_array: li $t0, 0 # 重新用 i 做输出循环变量 print_loop: bge $t0, $s1, exit # i n 时结束输出 sll $t4, $t0, 2 add $t4, $s0, $t4 lw $a0, 0($t4) # 要打印的数字 li $v0, 1 syscall # print_int la $a0, space li $v0, 4 syscall # print_string addi $t0, $t0, 1 j print_loop exit: li $v0, 10 syscall # 退出程序运行后控制台会输出2 2 3 3 5 8 10原数组里有两个2、两个3这个结果说明排序成功。你可以在 MARS 里点单步执行每一步对比寄存器和内存的变化尤其是$t5与$t6在交换前后的值。3.3 为什么内层循环边界要写成n - i - 1很多人翻译冒泡时会把内层循环写成j n - 1这样不是不行但每一轮都会多做无用功。冒泡排序的核心思想是每一轮把当前未排序区间的最大值“冒”到最后面。数组长度为n第一轮需要比较相邻元素n - 1次第二轮时最后一个元素已经是全局最大不需要再碰它所以只需要比较n - 2次。外层变量i每加 1内层可比较次数就减 1因此边界是n - 1 - i。在 C 语言里for 循环的条件通常写j n - 1 - i所以循环变量j的最大取值为n - 2 - i。而汇编代码中我用bge判断“当 j 大于等于边界时跳出”所以这里的$t3要设成n - i - 1而不是n - i - 2。这是最容易出 off-by-one 错误的地方。提示写汇编循环之前先在草稿纸上把 C 语言循环的“退出条件”翻译成“跳转条件”。j limit等效于“当 j limit 时跳出”所以判断用bge而不是blt。3.4 关于伪指令MARS 很方便但你要知道它帮你做了什么上面代码里出现了la、bge、ble这些其实都不是 MIPS 的“真指令”而是 MARS 汇编器提供的伪指令。la $s0, array会被展开成luiori因为 32 位地址不能直接塞进一条指令里bge和ble最终会被翻译成sltbeq/bne的组合。如果只是交 MARS 实验用伪指令完全没问题。但如果你以后接触真实 MIPS 机器或模拟器里的“延迟分支”就要注意这些伪指令的展开方式可能影响你对指令数的判断。我个人建议初学阶段先在 MARS 里看“Execute”窗口把伪指令展开后的真实指令浏览一遍哪怕记不住也要知道它们并不是一条指令。这能解释为什么有些代码在 MARS 里能跑在课上讲的概念模型里看指令流程却对不上。4. 当排序对象从数组变成结构体sort 函数的“舒服”不是白来的4.1 结构体排序到底在排什么数组排序只是热身真正让很多人翻车的是结构体排序。比如学生信息struct Student { char name[16]; int score; int age; };现在给你一个struct Student数组想按score从低到高排序。高级语言写起来很清爽C 里可以是#include algorithm #include vector using namespace std; struct Student { char name[16]; int score; int age; }; vectorStudent students; sort(students.begin(), students.end(), [](const Student a, const Student b) { return a.score b.score; });这里真正改变的是什么比较规则变了。数组中的元素从一个 4 字节整数变成了一个 24 字节左右的结构体排序时需要“整体搬运”每个结构体。如果回到 MIPS 汇编你要做的事就复杂得多用基址加偏移访问score字段比较两个score交换两个完整的结构体不只是交换一个字。4.2 qsort 的比较函数为什么要用地址同学们常说的“sort函数排序结构体”在 C 语言里更准确的说法其实是qsort#include stdlib.h int cmp_by_score(const void *a, const void *b) { const struct Student *sa (const struct Student *)a; const struct Student *sb (const struct Student *)b; return (sa-score sb-score) - (sa-score sb-score); } qsort(students, count, sizeof(struct Student), cmp_by_score);为什么qsort第四参数要传一个函数指针因为在 C 语言里排序函数不知道你的结构体长什么样也不知道你想按分数还是年龄排序。它只负责一件事根据比较结果把内存块搬来搬去。具体“怎么比较”由你写的比较函数告诉它。这其实就是把第 3 节 MIPS 代码里的ble $t5, $t6, no_swap这一句抽象成了回调函数。排序框架只负责循环和交换比较规则通过函数指针注入。在底层qsort拿到两个元素的地址调用你的比较函数根据返回值决定是否交换。如果你把比较函数写错比如强转类型不对或者返回逻辑写反排序结果就会南辕北辙。4.3 汇编视角下的结构体字段访问很多学过 C 结构体但没写过汇编的人不知道结构体在内存里就是一块连续存储区。下面的结构体struct Student { char name[16]; int score; int age; };它在内存里的布局大致是字段偏移量大小name016 字节score164 字节age204 字节合计24 字节如果score字段的偏移量是 16那么访问某个结构体数组第j个元素的score等于结构体首地址 j * 24 16这里的元素大小是 24不再是 4。交换两个结构体时如果只像整数排序那样交换一个lw那就只把前 4 个字节换了后面 20 个字节原封不动数据直接错乱。正确做法要么按 4 字节一块循环搬 6 次要么用专门的内存块拷贝过程。这就是为什么“sort函数排序结构体”在高级语言里看起来简单——标准库帮你处理了元素大小和字节搬移。但代价是你得搞清楚比较函数怎么写。4.4 顺便补一个稳定性知识点如果你用 C 的std::sort它不保证相等元素在排序后维持原有顺序。对于只有数值的数组稳定性无所谓但对于结构体如果先按name排好序再按score排序你可能会期望同样的score之间保留原来的相对顺序。这时候应该用std::stable_sort它和std::sort的参数几乎一样但能保证稳定性。回到 MIPS 冒泡排序里稳定性取决于你交换的条件到底用还是。只用“大于”交换相等元素就不会被打乱用“大于等于”交换相等元素的先后顺序会被反转。很多初学者在汇编里写排序时没注意这个细节结果在普通整数数组上完全看不出来等后面数据结构做链式结构排序时才发现问题。5. 我自己在 MARS 里踩过的三个坑5.1 忘记给偏移量乘 4导致排序结果像“隔一个换一个”这个坑我见过太多次了。有些同学把 C 语言里array[j]想成“从数组开头数 j 个位置”然后直接写add $t4, $s0, $t2 # 错误没有把 j 乘以 4 lw $t5, 0($t4)这样$t4只是array起始地址加上 j而不是加上j * 4。数组里每个.word占 4 字节你等于每次只跳过一个字节读取了一个完整字的 4 个字节中的某一部分。结果是排序过程看起来在跑但数据像被“打乱”了一样。正确做法是乘法用移位sll $t4, $t2, 2 add $t4, $s0, $t4提示不要写mul指令吗MARS 支持mul但整数乘 4 这种常量乘法编译器都会优化成sll。初学阶段最好直接养成“看变量类型决定移位量”的习惯。5.2 交换时寄存器互相覆盖另一个经典错误是交换逻辑写成了# 错误示例 lw $t5, 0($t4) # $t5 array[j] lw $t6, 4($t4) # $t6 array[j1] sw $t5, 0($t4) # array[j] $t5 sw $t6, 4($t4) # array[j1] $t6这段看起来是对的但如果有人在第一条sw之前把其中一个值存到了被覆盖的内存位置然后才把另一个值存过去就会出现覆盖问题。比如# 也是错误示例 sw $t5, 4($t4) # 先把靠前的值写到后面 lw $t5, 0($t4) # 再读前面这里读到的已经不是 array[j] 了标准交换必须先把两个值都装入寄存器再执行两次sw。寄存器$t5和$t6必须是两个不同的寄存器千万不能都用$t5。5.3 循环边界写成n导致越界读取如果内层循环没有限制在“当前未排序区间”而是傻傻地每次都从 0 跑到n - 1那么当 j 等于n - 1时array[j 1]会访问到数组末尾再追加 4 字节的地方。这段内存不属于你的数组可能是其他数据也可能是未定义的。运气好时程序不崩但排序结果中会出现一个莫名其妙的“大数”运气不好时 MARS 直接报地址异常。我建议你在写内层循环前先把这三样东西写清楚内容值数组长度 n7外层 i 的取值范围0 ~ 5内层 j 的取值范围0 ~ 5 - i然后每次检查bge跳转条件时拿n7、i0的情况心算一遍。循环边界正确程序不一定对但循环边界错了程序基本必挂。5.4 用 syscall 输出前记得设置$v0MARS 里系统调用依赖寄存器传入功能号。打印整数要li $v0, 1打印字符串要li $v0, 4退出程序要li $v0, 10。有的同学在调试时会打断点看$a0的值但发现输出的数字总是不对往往是因为之前的syscall改掉了$v0或者往$v0里写了一个中间结果。如果输出循环里需要在整数和空格字符串之间切换最稳妥的方式是每次 syscall 前重新设置$v0。虽然看起来啰嗦但能避免不少“明明数据排对了显示出来却是乱码”的尴尬。6. 从手写 SORT 到理解标准库我最终收获了什么整轮折腾下来我对“排序”这两个字有了完全不同的理解。以前用 C 写std::sort排结构体我只把它当工具从来没想过为什么可以传一个 lambda 进去。后来写了 MIPS 版排序才意识到标准库的 sort 本质是一个“排序框架”它需要的只是元素地址、元素大小和比较规则。比较规则可以通过函数指针、仿函数、lambda 注入所以一套排序代码可以处理整数、字符串、结构体甚至任意自定义类型。反过来汇编排序让我理解了内存连续性对算法效率的影响。数组元素按顺序排布时支持通过基址加偏移随机访问这让冒泡排序的实现成为可能。如果换成链表冒泡排序在 MIPS 里就要一遍一遍地通过lw加载 next 指针代码结构和数组版本完全不同。这也是为什么很多数据结构课程会强调“物理结构决定操作效率”。如果你现在也在做 MIPS MARS 的 SORT 题目我不建议直接背代码。更好的做法是先跑通上面的完整程序然后尝试做三个小改动把数组改成降序排列观察代码里哪些地方要改把长度从固定 7 改成.word一个变量再用li $s1, 7加载体会数据段和指令段的分离把排序部分封装成一个sort过程主程序用jal sort调用练习参数传递和返回地址保存。第三个改动会逼你想清楚一个问题如果sort过程内部又会调用其他过程$ra寄存器还能不能安全使用这就涉及栈帧了也是 MIPS 实验里比 SORT 本身更有价值的下一课。我自己在带这个题目的过程中最深的体会是能让你真正把高级语言里的排序函数和汇编里的排列指令打通的办法不是看标准库源码而是亲手写一遍那个最笨的冒泡排序。写完再回头看sort函数你会觉得它没那么神奇反而更清楚它替我们省了多少事。