这个8086升序代码是如何工作的？

Question

我目前正在学习 8086 编程，这个编程已在我们实验室的 8086 套件上进行了演示。以下代码将数字序列按升序排序：

mov si, 2000
mov cl, [si]
dec cl
loop1: mov si, 2000
       mov ch, [si]
       dec ch
       inc si
       loop2: mov al, [si]
              inc si
              cmp al, [si]
              
              jc loop3

              xchg al, [si]
              dec si
              xchg di, [si]
              inc si

       loop3: dec ch
              jnz loop2
       dec cl
       jnz loop1
int a5

这个功能到底是如何运作的？

假设我们有一个由 N 个数字 d1, d2, ..., dN 组成的数组，如下所示：

Address |2000|2001|2002|2003|...|2000+N|...|
Data    |N   |d1  |d2  |d3  |...|dN    |...|
        |si  |

cl <-- [si]
{cl:N --> N-1}

循环1：

ch <-- [si]
{ch:N --> N-1}
si --> si+1
Address |2000|2001|2002|2003|...|2000+N|...|
Data    |N   |d1  |d2  |d3  |...|dN    |...|
             |si  |

循环2：

al <-- [si] = d1
si --> si+1
Address |2000|2001|2002|2003|...|2000+N|...|
Data    |N   |d1  |d2  |d3  |...|dN    |...|
                  |si  |
Compare [si] = d2 with al = d1.
If d1 > d2, jump to LOOP 3,
else d1 <= d2 and exchange d1 in al with d2 at si = 2002.
al = d2
Address |2000|2001|2002|2003|...|2000+N|...|
Data    |N   |d1  |d1  |d3  |...|dN    |...|
                  |si  |
si --> si - 1
[di] = d1 (at 2001) 

循环3：

{ch:N-1 --> N-2}
If ch is not zero then jump to LOOP 2.
al <-- [si] = d2 and so on.

此时我感觉我已经不知道代码是如何工作的了。那么，这是如何运作的呢？我错过了什么吗？演示的例子是：

Address |2000|2001|2002|2003|2004|2005|...|
Input   |5   |04  |03  |01  |00  |02  |...|
Output  |5   |00  |01  |02  |03  |04  |...|

Answer 1

升序冒泡排序的麻烦

• xchg di, [si]

  肯定有错别字。应该清楚的是，代码在其他任何地方都没有使用

  di

  寄存器，因此这个特定的交换指令是无用的。有意义的是

  xchg al, [si]

  ，但更好的是简单的

  mov [si], al

  。
• 除了冒泡排序是最糟糕的排序方法之外，这里他们还因为不承认冒泡排序最突出的特征“使最大元素冒泡到数组的顶部”而使其变得更加糟糕。一旦最大元素到达顶部位置，代码不应再考虑该顶部位置，并且下一次迭代应该已经提前停止一个位置。

此时我感觉我已经不知道代码是如何工作的了。那么，这是如何运作的呢？我是不是错过了什么？

您误解了条件跳转：

cmp al, [si]      <<<< AL = d1, [si], d2
jc loop3

当你说：

If d1 > d2, jump to LOOP 3,
else d1 <= d2 and exchange d1 in al with d2 at si = 2002.

jc

指令应该写成

jb

，它具有完全相同的编码，但更好地传达了它的作用：“如果 AL 低于 [si] 处的字节，则跳转到 LOOP3”。所以如果

d1 < d2

这与你所说的正好相反（“如果 d1 > d2”）。
顺便说一句，LOOP3对于这个厂牌来说是一个非常糟糕的名字！更合适的名称可能是SKIP。

如果您能发布此代码的易于理解的更好版本，我将非常感激。

       mov  si, 2000  ; Where the count resides
       mov  cl, [si]  ; CL is number of elements
       dec  cl        ; CL is number of iterations outer loop
Outer: mov  si, 2001  ; Where the first element resides
       mov  ch, cl    ; Ever smaller number of iterations inner loop (*)
Inner: mov  al, [si]
       inc  si
       cmp  al, [si]  ; Compare two adjacent elements
       jb   Skip      ; Skip the Swap if ordered fine already
Swap:  xchg al, [si]
       mov  [si-1], al
Skip:  dec  ch
       jnz  Inner     ; Iterate on the Inner loop
       dec  cl
       jnz  Outer     ; Iterate on the Outer loop

(*) 这就是使冒泡排序作为小数组的排序方法在某种程度上可以被接受的魔力！

有关编写冒泡排序代码的更多信息，请参阅对从键盘读取的 10 个整数进行排序并按升序显示。