选择排序循环中的问题

Question

我在实现汇编中的选择排序方法时遇到了问题。

我还是不明白自己哪里出了问题。欢迎大家的帮助。

可能我在向量中分配数字，然后比较的时候出错了。

按照C#中的代码，再来看看我在汇编中的做法。

public static void selecao(int[] vet)
{
   int i, j, min, temp;
   for (i = 0; i < vet.Length - 1; i++)
   {
      min = i;
   for (j = i + 1; j < vet.Length; j++)
   {
      if (vet[j] < vet[min])
      {
         min = j;
      }
   }
   temp = vet[i];
   vet[i] = vet[min];
   vet[min] = temp;
   }
}

汇编

addi $t0, $zero, 0 
addi $t1, $zero, 0  
sub $s1, $s0, 1     
addi $s2, $zero, 0  
addi $t1, $zero, 0 
forS1:
slt $t2, $t0, $s1 (i < size v - 1)
beq $t2, $zero, fimForS1

addi $s2, $t0, 0

addi $t3, $t0, 1 
forS2:
slt $t4, $t3, $s0
beq $t4, $zero, fimForS2

add $s6, $s6, 1 
mul $t3, $t3, 4 
lw $s3, vetor($t3)      # vet[j]
mul $s2, $s2, 4
lw $s4, vetor($s2)      # vet[min]
slt $t5, $s3, $s4       # vet[j] < vet[min]
beq $t5, $zero, forS2
add $s7, $s7, 1 
add $s2, $t3, 0         # min = j
addi $t3, $t3, 1 
j forS2

fimForS2:
lw $t6, vetor($t1)      # vet[i]
mul $s5, $s2, 2         # posicao do vet[min]
lw $t7, vetor($s2)      # vet[min]  
addi $t8, $t6, 0        # temp = vet[i]
sw $t6, vetor($s2)          # vet[i] = vet[min];
sw $t7, vetor($t1)          # vet[min] = temp;
addi $t1, $t1, 4 
addi $t0, $t0, 1 

j forS1

Answer 1

我们来看看for语句的控制流程，先用伪代码。

for ( int i = 0; i < n; i++ ) {
    ...body...
}

1. 首先我们做 i=0，一次，在循环外。
2. 接下来，我们用一个检查开始循环 i<n 看看我们是否完成了循环。
3. 接下来的代码 ...body...，然后
4. 增量 i++，最后。
5. 来重复循环：回到步骤2。

当（使用结构化编程）我们在循环的主体中嵌套另一个控制语句时，我们仍然遵循同样的模式，没有变化。

for ( int i = 0; i < n; i++ ) {
    if ( a < b ) {
         b = a;
    }
}

所以，这里的主体只是一个if语句。  因此，我们

1. 首先我们做 i=0，一次，在循环外。
2. 接下来，我们用一个检查开始循环 i<n 看看我们是否完成了循环。
3. 接下来 ...body...，这里是if语句。
   • 测试a < b，如果不是这样，就跳到4.
   • 捕获b=a
4. 增量 i++，最后。
5. 来重复循环：回到步骤2。

你是否看到无论嵌套的if语句是否执行，接下来正确的做法是for语句增量。i++?

你不小心移动了你的 j++ 增量到嵌套的if语句内部的then-part。  你的代码没有遵循嵌套控制结构的正确模式--if语句不应该干扰它所嵌套的for语句。  所以，与其这样做，不如用 j++ 无论if语句做什么，你都在做 j++ 只有当if-statement触发时才会出现。  所以，这是对伪代码的错误翻译，根本无法正常工作。

再下面当你交换时，你使用的是 vet[min] 但你的数组索引是错误的。

---

请看行内说明。

addi $t0, $zero, 0 
addi $t1, $zero, 0  
sub $s1, $s0, 1     
addi $s2, $zero, 0  
addi $t1, $zero, 0    <--- unnecessary, already done above
forS1:
slt $t2, $t0, $s1 (i < size v - 1)
beq $t2, $zero, fimForS1

addi $s2, $t0, 0

addi $t3, $t0, 1 
forS2:
slt $t4, $t3, $s0
beq $t4, $zero, fimForS2

add $s6, $s6, 1 
mul $t3, $t3, 4 
lw $s3, vetor($t3)      # vet[j]
mul $s2, $s2, 4
lw $s4, vetor($s2)      # vet[min]
slt $t5, $s3, $s4       # vet[j] < vet[min]

beq $t5, $zero, forS2   <--- this if statement skips the then part (good)
                             ***** but also skip the j++ (bad) *****

+------------------------------- this it the then part
add $s7, $s7, 1 
add $s2, $t3, 0         # min = j
addi $t3, $t3, 1        <--- this is j++
+-------------------------------
j forS2

fimForS2:
lw $t6, vetor($t1)      # vet[i]
mul $s5, $s2, 2         # posicao do vet[min]  <--- multiply by 2 (why 2??)
                                                    ***** $s5 is never used *****
lw $t7, vetor($s2)      # vet[min]         <--- here using $s2, min (bad)
                                           ***** you want min*4 instead *****
addi $t8, $t6, 0        # temp = vet[i]
sw $t6, vetor($s2)          # vet[i] = vet[min];
sw $t7, vetor($t1)          # vet[min] = temp;
addi $t1, $t1, 4 
addi $t0, $t0, 1 

j forS1