# 汕头大学 12计算机 张雪浩 2014/4/7
# 用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_si
gn:
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循环，再来一次读数、排序、输出
exit: la $a0,tip5  # 提示程序退出
li $v0,4
syscall
jr $ra 
QuickSort:  # void quick_sort(int *low,int *high)
addi $sp,$sp,-32 # 开辟堆栈空间，至少32字节
sw $ra,28($sp)  # 保存上一个函数的指针
sw $fp,24($sp)  # 保存当前框架指针，听说是当前框架内存储器内容的基指针
sw $a0,20($sp)  # 保存参数0
sw $a1,16($sp)  # 保存参数1
addi $fp,$sp,32  # 框架指针上移到进入当前函数时的堆栈指针位置，我也不知道干嘛用的
slt $t0,$a0,$a1 
bne $t0,$zero,less # if(low<high) then  do less
j end
less: move $t0,$a0 # left = low
move $t1,$a1 # right = high
lw $t4,0($a0) # key = *left, 获取key的值
while1: slt $t2,$t0,$t1 
bne $t2,$zero,W1 # while(left<high) do W1
j endW1
W1:
# while(left<high && *right>=key) right--;
while2: slt $t2,$t0,$t1 
beq $t2,$zero,endW2 # if（left>=high) then endW2
lw $t3,0($t1)  # *right操作
slt $t2,$t3,$t4
bne $t2,$zero,endW2  # if（*right<key) then endW2
addi $t1,$t1,-4  # right--
j while2
endW2: lw $t2,0($t1)  # *right操作
sw $t2,0($t0)  # *left=*right;
# while(left<high && *left<key) left++;
while3: slt $t2,$t0,$t1
beq $t2,$zero,endW3 # if（left>=high) then endW3
lw $t3,0($t0)  # *left操作
slt $t2,$t3,$t4
beq $t2,$zero,endW3  # if（*left>=key) then endW2
addi $t0,$t0,4  # left++
j while3
endW3: lw $t2,0($t0)  # *left操作
sw $t2,0($t1)  # *right=*left
j while1
endW1:
sw $t4,0($t0)  # *left=key
sw $t0,12($sp)  # 保存当前函数的left指针
lw $a0,20($sp)  # 读取参数0，即low
addi $t0,$t0,-4  # left-1
move $a1,$t0  #
参数1赋值为left-1
jal QuickSort  # quick_sort(low,left-1)
lw $t0,12($sp)  # 恢复当前函数的left指针
addi $t0,$t0,4  # left+1
move $a0,$t0  # 参数0赋值为left+1
lw $a1,16($sp)  # 读取参数1，即high
jal QuickSort  # quick_sort(left+1,high)
end: lw $ra,28($sp)  # 获取上一个函数的指针
lw $fp,24($sp)  # 获取当前框架指针
lw $a0,20($sp)  # 获取参数0
lw $a1,16($sp)  # 获取参数1
addi $sp,$sp,32  # 回收堆栈空间
jr $ra  # 返回到上一个函数指针所指的函数，即返回到上一个函数调用本函数时的下一条指令处
# 测试例子
# 12
# 46 30 -98 112 0 76 9 11 19 15 102 -44
#  main函数：
# a) 提示输入数字个数n，，当n<=0时退出程序，经测试，当n超过3000时可能栈溢出；
#  b) 计算存储n个整数所需空间，以及用字符串保存n个整数所需空间；
# c) 堆栈指针下移n*4 bytes，保存该指针到$s0，为数组a的起始地址；
#  d) 堆栈指针继续下移 n*12 bytes, 保存该指针到$a0, 调用系统功能读入字符串，
#    用户输入整数时需用1个空格间隔开相邻的2个整数，字符串输入结束后将堆栈
#    指针恢复到$s0, 即数组a的起始位置；
# e) 循环n次 将字符串中里的n个字符型整数转换成数值型整数，并保存在数组a里，需保存a[n]的地址到$s1；
# f) 将数组a[0]地址 与 a[n-1]地址 赋值到寄存器$a0和$a1,
#    先用堆栈保存$ra, 再调用QuickSort函数，最后恢复$ra及回收堆栈空间，$ra存储着当前下一条指令的指针;
# g) 打印数组a的n个元素, 跳回步骤a。
# QuickSort函数：
# 快速排序的基本思想是先选取一个元素作为比较量key，以该比较量为基准，
# 通过一趟排序将待排序元素分割成独立的两部分，其中一部分的元素均小于
# 等于key，另一部分的元素均大于等于key。然后分别对这两部分元素继续进
# 行上述排序，以达到整个序列有序。
# 实现步骤：
# a) 先用堆栈保存相关寄存器内容，如果 参数$a0 < 参数$a1，则进入步骤b，否则进入步骤e；
# b) 获取待排序元素的起始位置left、终止位置right 和 比较量key，这里取key=*left，
#    此时left所指的内容可以被覆盖掉，因为key已经保存了其内容；
# c) 当left<right时，
#    先把right向left移动，寻比key小的第一个元素的地址，将到的元素赋值给left所指的内存单元，
#    此时right所指的内容可以被覆盖掉，因为*left已经保存了其内容；
#    再把left向right移动，寻大于等于key的第一个元素的地址，将到的元素赋值给right所指的内存单元，
#    此时left所指的内容可以被覆盖掉，因为*right已经保存了其内容；
#    当left<right时继续步骤c，否则进入步骤d；
# d) 先将key赋值给left所指的内存单元；
#   
再保存left指针，把 left-1赋值给寄存器$a1，
#    回到步骤a)继续排序，排序完后恢复left指针；
#    最后把left+1赋值给寄存器$a0,
#    回到步骤a)继续排序，排序完后进入步骤e；
# e) 恢复相关寄存器内容，返回到上一个函数调用本函数时的下一条指令处，并执行该指令及后面的指令。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。