如何在MIPS汇编中通过递归调用实现快速排序的分区操作

先明确快速排序的核心流程：

1. 若当前子数组的左边界 >= 右边界，直接返回（递归终止条件）
2. 调用partition函数将数组分区，得到基准元素的最终索引pivot
3. 递归排序基准左侧的子数组（左边界到pivot-1）
4. 递归排序基准右侧的子数组（pivot+1到右边界）

现有代码问题 #

• quickSort函数调用partition后未处理返回的基准索引，也未执行递归调用
• partition函数未实现核心分区逻辑，且未处理寄存器的保存/恢复
• 递归调用时未保存返回地址$ra和s寄存器（MIPS中s寄存器属于调用者保存，递归会覆盖）

完整实现代码 #

.data
array: .word 6 8 1 7 5 2 3 4 9 3 5
length: .word 11
newline: .asciiz "\n"
space: .asciiz " "

.text
.globl main

main:
    la $a0, array
    li $a1, 0
    lw $a2, length
    addi $a2, $a2, -1  # 右边界是length-1
    
    jal quickSort
    
    # 排序完成后打印数组（可选，用于验证）
    la $a0, array
    lw $a1, length
    jal printArray
    
    li $v0, 10
    syscall

# 快速排序函数
# 参数: $a0=数组地址, $a1=左边界low, $a2=右边界high
quickSort:
    # 递归终止条件：low >= high
    bge $a1, $a2, quickSort_end
    
    # 保存调用者保存寄存器和返回地址到栈
    addi $sp, $sp, -20  # 保存$s0-$s3, $ra（每个4字节，共5个）
    sw $s0, 0($sp)
    sw $s1, 4($sp)
    sw $s2, 8($sp)
    sw $s3, 12($sp)
    sw $ra, 16($sp)
    
    move $s0, $a0  # 保存数组地址
    move $s1, $a1  # 保存low
    move $s2, $a2  # 保存high
    
    # 调用分区函数，返回基准索引到$v0
    jal partition
    move $s3, $v0  # 保存pivot索引
    
    # 递归排序左半部分：low 到 pivot-1
    move $a0, $s0
    move $a1, $s1
    addi $a2, $s3, -1
    jal quickSort
    
    # 递归排序右半部分：pivot+1 到 high
    move $a0, $s0
    addi $a1, $s3, 1
    move $a2, $s2
    jal quickSort
    
    # 恢复寄存器
    lw $s0, 0($sp)
    lw $s1, 4($sp)
    lw $s2, 8($sp)
    lw $s3, 12($sp)
    lw $ra, 16($sp)
    addi $sp, $sp, 20

quickSort_end:
    jr $ra

# 分区函数（Lomuto分区，易实现）
# 参数: $a0=数组地址, $a1=low, $a2=high
# 返回: $v0=pivot的最终索引
partition:
    # 选最后一个元素作为基准
    sll $t0, $a2, 2       # high * 4
    add $t0, $a0, $t0     # 基准元素的地址
    lw $t1, 0($t0)        # $t1 = pivot值
    
    addi $t2, $a1, -1     # i = low - 1，跟踪小于等于基准的区域边界
    move $t3, $a1         # j = low，遍历数组

partition_loop:
    bge $t3, $a2, partition_end  # j遍历到high-1时退出
    
    # 获取当前j位置的元素
    sll $t4, $t3, 2
    add $t4, $a0, $t4
    lw $t5, 0($t4)        # $t5 = array[j]
    
    # 如果当前元素<=基准，交换到i的下一个位置
    ble $t5, $t1, partition_swap
    j partition_next

partition_swap:
    addi $t2, $t2, 1      # i++
    # 交换array[i]和array[j]
    sll $t6, $t2, 2
    add $t6, $a0, $t6     # array[i]地址
    lw $t7, 0($t6)        # temp = array[i]
    
    sw $t5, 0($t6)        # array[i] = array[j]
    sw $t7, 0($t4)        # array[j] = temp

partition_next:
    addi $t3, $t3, 1      # j++
    j partition_loop

partition_end:
    # 把基准元素交换到最终位置（i+1）
    addi $t2, $t2, 1      # i++
    sll $t6, $t2, 2
    add $t6, $a0, $t6     # array[i]地址
    lw $t7, 0($t6)        # temp = array[i]
    
    sw $t1, 0($t6)        # array[i] = pivot
    sw $t7, 0($t0)        # array[high] = temp
    
    move $v0, $t2         # 返回i作为pivot索引
    jr $ra

# 打印数组函数（可选，用于验证结果）
# 参数: $a0=数组地址, $a1=数组长度
printArray:
    li $t0, 0
print_loop:
    bge $t0, $a1, print_end
    sll $t1, $t0, 2
    add $t1, $a0, $t1
    lw $a0, 0($t1)
    li $v0, 1
    syscall
    
    la $a0, space
    li $v0, 4
    syscall
    
    addi $t0, $t0, 1
    j print_loop
print_end:
    la $a0, newline
    li $v0, 4
    syscall
    jr $ra

关键逻辑解释 #

1. 递归调用机制

   • 每次调用quickSort前，必须把$ra（返回地址）和s寄存器压栈，因为递归调用会覆盖这些寄存器的值
   • 分区完成后，分别对基准左侧和右侧的子数组递归调用quickSort，直到子数组长度为0或1（low >= high）时终止递归
   • 递归返回后，恢复之前保存的寄存器，确保上层调用的环境不受影响

2. 分区函数（Lomuto算法）

   • 选择数组最后一个元素作为基准
   • 用i指针跟踪小于等于基准的区域边界，初始值为low-1
   • j指针遍历从low到high-1的所有元素，若当前元素<=基准，就将其交换到i的下一个位置，i右移
   • 遍历结束后，将基准元素交换到i+1的位置，此时基准左侧都是<=它的元素，右侧都是>它的元素，返回i+1作为基准索引

3. 寄存器使用规范

   • MIPS中t寄存器（$t0-$t9）属于被调用者保存，函数内部使用不需要保存到栈
   • s寄存器（$s0-$s7）属于调用者保存，函数调用前必须保存到栈，返回后恢复
   • $ra（返回地址）在调用jal时会被覆盖，递归调用前必须压栈保存

内容的提问来源于stack exchange，提问作者Tanner Raine