MIPS汇编语言实现：插入排序的递归与非递归版本

"这篇实验报告主要探讨了如何使用MIPS汇编语言实现插入排序，包括递归和非递归两种版本。插入排序是一种简单的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。在MIPS汇编代码中，递归版本的排序函数和非递归版本的排序函数被详细地展示出来，并且有输入和输出函数的支持，以便在SPIM模拟器上运行和验证排序结果。" 插入排序是一种基础的排序算法，其核心思想是通过不断将未排序元素插入到已排序部分来完成排序。在递归版本的MIPS汇编代码中，`sort`函数被设计为一个递归过程。首先，它检查要排序的元素个数是否小于或等于1，如果是，则认为数组已经有序，直接返回。否则，将最后一个元素与已排序的子数组进行比较并适当移动，直到找到正确的位置插入，然后对剩余的子数组进行递归调用。 非递归版本的插入排序通常使用一个循环来实现，它遍历数组，将每个元素插入到已排序的子数组的正确位置。在这个过程中，需要维护两个指针，一个指向当前未排序元素，另一个指向已排序部分的末尾。在MIPS汇编代码中，这个过程可能涉及多次`sw`（存储）和`lw`（加载）指令，用于在内存中读取和写入元素，以及`add`、`sub`指令来更新指针。 实验中还包括了`input`和`output`函数，分别负责从用户那里获取输入数据并将排序后的结果输出。`input`函数使用`syscall`指令读取用户输入，将数据存储到数组中，并使用循环结构处理所有输入。`output`函数则可能遍历整个数组，打印出排序后的元素。 在MIPS汇编语言中，函数调用通过`jal`指令实现，而返回则使用`jr $ra`指令。栈空间的管理（包括保存和恢复寄存器状态）通过`sub`和`add`指令调整栈指针`sp`，以及`sw`和`lw`指令将寄存器数据压栈和出栈，以确保函数调用期间的现场得以保存和恢复。 这个实验提供了插入排序的MIPS汇编实现，有助于理解排序算法在底层硬件上的工作方式，同时展示了递归和非递归两种方法的实现细节。这对于学习计算机体系结构、汇编语言编程以及算法实现具有很高的实践价值。