M​I​P​S​实​现​快​速​排​序

# 用PCSpim打开运行

.data
tip1: .asciiz "输入数字个数N: "
tip2: .asciiz "依次输入"
tip3: .asciiz "个数字,以1个空格符为间隔:\n"
tip4: .asciiz "快速排序结果: \n"
tip5: .asciiz "程序结束!\n"
space: .asciiz " "
LF: .asciiz "\n"
.text
.globl __start

__start:
while0: la $a0,tip1 # 将字符串提示1的首地址传入参数$a0
li $v0,4 # 选择要调用的系统功能
syscall # 打印提示1

li $v0,5 # 读入N
syscall
move $t0,$v0

beq $t0,$zero,exit # N==0时退出程序
slt $t1,$t0,$zero
bne $t1,$zero,exit # N<0时退出程序

la $a0,tip2 # 提示2
li $v0,4
syscall

move $a0,$t0 # 输出N
li $v0,1
syscall

la $a0,tip3 # 提示3
li $v0,4
syscall

sll $t0,$t0,2 # 计算存储n个数字所需空间,即 n*4 bytes
li $t1,3
mul $a1,$t0,$t1 # a1为读入字符串的最大长度,即 n*12 bytes, 注意不是字符串的实际长度
# 1个32位整数最大长度为10,申请 n*12 bytes
# n< 剩余堆栈容量/16,如堆栈剩余有2^15字节,则最多读入 2^15 / 16 =2048 个整数

sub $sp,$sp,$t0 # 堆栈指针sp下移 n*4 字节
move $s0,$sp # 保存数组a[0]位置

sub $sp,$sp,$a1 # 堆栈指针sp继续下移 a1 字节
move $a0,$sp # $a0为读入字符串的首地址
li $v0,8
syscall # 读入字符串

move $sp,$s0 # 恢复堆栈指针至数组a[0]位置

addi $t3,$zero,' ' # 空格符ASCII值
addi $t4,$zero,10 # 换行符ASCII值
addi $t5,$zero,'0' # 数字0的ASCII值
addi $t6,$zero,'-' # 负号ASCII值
move $t7,$zero # $t7为0时表示$t1的数值为正,否则为负

move $t0,$s0 # 开始对数组元素赋值

Loop: andi $t1,$t1,0x0000 # 清零,用于累加读入的每一个字符的数值

tran: andi $t2,$t2,0x0000 # 清零,用于存储字符串的1个字符
lb $t2,0($a0) # 从字符串读入1个字符到$t2,注意1个字符占1字节
beq $t2,$t3,store # 读到空格符,表示一个数已经读完,跳至store在数组里保存$t2
beq $t2,$t4,store # 读到换行符,表示整个字符串已经读完,跳至store在数组里保存$t2
beq $t2,$t6,signed # 读到负号,跳至signed保存符号位

mul $t1,$t1,$t4 # $t1 = $t1 * 10
sub $t2,$t2,$t5 # $t2 = $t2 - '0'
add $t1,$t1,$t2 # $t1 = $t1 + $t2
addi $a0,$a0,1 # 字符串首地址上移1字节
j tran # 循环读取字符串,直至遇到换行符

signed: addi $t7,$zero,-1
addi $a0,$a0,1
j tran

store: bne $t7,$zero,add_sign # 判断$t1的数值是否为负

lab0: sw $t1,0($t0) # 把$t1的数值保存在数组的$t0位置上

addi $a0,$a0,1 # 字符串首地址上移1字节
addi $t0,$t0,4 # 数组指针上移4字节,一个32位整数占4字节
bne $t2,$t4,Loop # 判断是否读到字符串的换行符,若没有则继续读数
j lab1 # 读数结束,跳过符号位处理
add_sign:
mul $t1,$t1,$t7 # 符号位处理

move $t7,$zero # 置零
j lab0 # 跳回lab0,继续保存$t1

lab1: move $s1,$t0 # 保存数组a[n]位置,a[0 : n-1]为数组元素

move $a0,$s0 # 将数组a的首地址传递给参数$a0, 即quick_sort(int *low,int *high)函数的low
move $a1,$s1
addi $a1,$a1,-4 # 将数组a最后元素的地址传递给参数$a1,即quick_sort(int *low,int *high)函数的high

addi $sp,$sp,-32 # 开辟堆栈空间
sw $ra,28($sp) # 保存当前函数指针
jal QuickSort # 调用QuickSort函数
lw $ra,28($sp) # 恢复当前函数指针
addi $sp,$sp,32 # 回收堆栈空间

la $a0,tip4 # 提示开始输出排序结果
li $v0,4
syscall

move $sp,$s0 # 把堆栈指针$sp移到数组a的首地址$s0
Output: lw $a0,0($sp) # 读入数组元素
li $v0,1
syscall # 打印数组元素

la $a0,space
li $v0,4
syscall # 打印空格符

addi $sp,$sp,4 # 堆栈指针上移4个字节,用于读取下一个数组元素
bne $sp,$s1,Output # 判断堆栈指针是否等于a[n]的地址,若不等则继续打印数组元素

la $a0,LF
li $v0,4
syscall # 换行

j while0 # while循环,再来一次读数、排序、输出

--电子创新网--
粤ICP备12070055号