我的汇编Bubble Sort有什么问题？

Question

我是用汇编实现Bubble Sort的，基本的伪代码大纲。

for i in array
    if array[i] >= array[i+1]
        exchange array[i], array[i+1]

我的ASM代码

BubbleSort PROC
    mov     EBX, LENGTHOF myArr
    .REPEAT
        mov     ESI, 0
        mov     ECX, LENGTHOF myArr
        .REPEAT
            mov     EAX, [myArr + ESI]
            .IF EAX >= [myArr + ESI + TYPE myArr]       ; If (myArr[i] < myArr[i + 1])
                xchg    EAX, [myArr + ESI + TYPE myArr]
                mov     [myArr + ESI], EAX
            .ENDIF

            add     ESI, TYPE myArr
            dec     ECX
        .UNTIL ECX == 0
    dec     EBX
    .UNTIL EBX == 0
    ret
BubbleSort ENDP

当我把我的实现给教授看时 他说这 "有点 "像泡泡排序 或者说是泡泡排序的 "类型" 在告诉我们这个任务时，他说我们应该从数组的后面开始，从后往前移动。可是我却从前面开始，从前到后移动。

我觉得我的方向是对的，代码也能用，但是我想正确的做。

有谁看出我哪里出错了吗？

Answer 1

假设你的代码工作，它是 绝对 冒泡排序。 向数组的任何一端冒泡都是可以的，所以不进行优化，比如使用外循环计数器(EBX)作为内循环的上界。

简单化或天真并不能阻止它成为Bubble Sort。 (如果有的话，简单化和天真就是Bubble Sort的全部意义。)

---

也请看 泡沫排序。古代算法分析 以了解更多关于Bubble Sort的历史，并对相关的JumpDown Sort进行了一些讨论，以及是否使用布尔值作为早期退出。

它所介绍的BubbleSort的版本，运行了来自于 j=n-1 以至于 1 (含)，所以内循环可以把它作为上界。 但内循环和你的一样，从k=0到 j，有条件地交换 A[j] 与 A[j+1]，从而使元素在数组的最后冒泡。

版本 维基百科上 也是往上冒，跑 i 从1到 n-1 (含)。 维基其实有2个版本：那第一个像你这样天真的版本，第二个版本则是减去了 n 内的循环。 (Wiki的两个版本都使用了一个布尔变量来记录是否做了任何交换，使算法复杂化，并且破坏了Bubble Sort的唯一目的优势，那就是死简单，代码极小。 (例如 约20字节的x86机器代码，尽管那是针对大小而不是速度进行了大量优化。 一个更正常的实现将与InsertionSort大小相似。)

---

你的代码使用了MASM宏，最终会浪费指令重做检查（我假设 .UNTIL ECX == 0 不利用以下事实 dec ecx 已经只是根据ECX为非零来设置标志）。) 但它确实有很好的 do{}while() 的循环结构。

---

另外，你的伪代码缺少外循环。 那只是BubbleSort的一个段落。 但是，是的，迭代那个 n 次将排序 n 元素数组。