如何在汇编中使用堆栈对数组进行排序

Question

我想在使用堆栈时对数组进行排序：

所以首先我把它全部推入堆栈。

然后我找到堆栈中的最小元素，将其与顶部元素交换，将其弹出并将其移回数组。

但有些事情不对劲，大约在一半的时候就搞砸了（DI 比实际值低了一个指数）

data segment
   a db 5h,12h,6h,4h,9h
   len equ $-a
   loop_counter db len
   min_index dw 0
   min db ?
ends

stack segment
    dw   128  dup(0)   
ends

code segment ;TODO: Locate min in stack xchg it with top element copy to array and pop it :|    
start:
    mov ax, data
    mov ds, ax
    mov bx,0
    mov cx,0
    mov cl,loop_counter
push_arr_to_stack:

    mov al,a[bx]
    push ax
    inc bx      
    loop push_arr_to_stack
  
    mov bx,len-1
    mov ax,0
    mov cl,loop_counter
    mov bp,sp
    mov ax,[bp]
    mov bx,[bp]
    mov di,0 
    mov dx,0
    mov si,2
    mov di_check,len-loop_counter 
    
find_min_to_arr:

    cmp bx,ax
    jb  new_min
    mov bx,[bp+si]
    add si,2  
    
    loop find_min_to_arr
    mov min,al
    
    xchg a[di],al
    jmp pop_min
    
new_min:
       mov ax,bx
       mov bx,[bp+si]
       mov min_index,si
       sub min_index,2
       add si,2
       dec cx
       jmp find_min_to_arr
        
pop_min:
        mov dx,[bp]
        xchg di,min_index
        mov [bp+di],dx
        xchg di,min_index
        pop dx
        mov dx,0
        inc di
        mov si,0
        cmp di,len
        je b
        dec loop_counter
        mov cl,loop_counter
        jmp find_min_to_arr
        
b:              
    mov ax, 4c00h ; exit to operating system.
    int 21h
  
ends
end start 

Answer 1

首先我将其全部推入堆栈。

这部分很好，但出于速度原因，您应该忘记

loop

指令并将其替换为

dec cx

，然后是

jnz ..

。请参阅为什么循环指令很慢？英特尔就不能高效地实现它吗？.

然后我找到堆栈中的最小元素，将其与顶部元素交换，将其弹出并将其移回数组。

这里你的代码变得非常复杂并且包含很多错误。此外，代码不会在找到的最小值和堆栈顶部的元素之间执行真正的交换。

我尝试修改你的代码，但通常情况下，它无法修复。下面是我的重写，你应该学习，而不是仅仅复制！
我定义了 loop_counter 一个 word 变量，因为这样更容易。另外，我把它保存在

DX

寄存器中，它坐在那里什么都不做......

将其全部压入堆栈

    mov  bx, dx
push_arr_to_stack:
    mov  al, a[bx-1]
    push ax
    dec  bx      
    jnz  push_arr_to_stack

我将数组反向推入，以便堆栈中的元素与原始数组的顺序相同。这对于完成任务来说不是必需的，但它更简单，并且它将

BX

寄存器保留为零以供以后使用。

找到堆栈中的最小值

Again:
    mov  bp, sp
    xor  si, si
    mov  al, [bp+si] ; Chosen minimum
    mov  di, si      ; Remember its position
    mov  cx, dx
    dec  cx          ; N elements = N-1 compares
    jz   .c
.a: add  si, 2
    cmp  al, [bp+si]
    jbe  .b
    mov  al, [bp+si] ; New minimum
    mov  di, si      ; Remember its position
.b: dec  cx
    jnz  .a

与顶部元素交换

.c: xchg al, [bp]    ; Read the final note about this XCHG
    mov  [bp+di], al

将其弹出并将其移回阵列

    pop  ax
    mov  a[bx], al
    inc  bx
    dec  dx
    jnz  Again

---

这里重要的是上面的内容完全按照任务描述所述进行。

最后注意事项

出于性能原因，应避免与内存进行交换。因此最好更换：

.c: xchg al, [bp]
    mov  [bp+di], al

作者：

.c: mov  cl, [bp]
    mov  [bp], al
    mov  [bp+di], cl