我的程序集气泡排序有什么问题？

Question

我正在使用基本的伪代码/大纲在汇编中实现气泡排序：

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)作为内部循环的上限。

简单化或幼稚并不能阻止它成为泡沫排序。 (如果有的话，简单和幼稚是泡沫排序的全部意义所在。

---

另请参阅气泡排序：考古算法分析，了解有关气泡排序历史的更多信息，以及相关的跳转排序的一些讨论，以及您是否使用布尔值作为早期输出。

它呈现的 BubbleSort 版本将外部循环从j=n-1运行到1(含)，因此内部循环可以将其用作上限。 但是内部循环和你的一样，从 k=0 到j，有条件地用A[j+1]交换A[j]，从而在数组的末尾冒泡元素。

维基百科上的版本也向上冒泡，从 1 到n-1(含)运行i。 Wiki 实际上有 2 个版本：第一个像你这样的幼稚版本，第二个版本在循环内递减n。 (两个 Wiki 的版本都使用布尔变量来记录它是否进行了任何交换，使算法复杂化并破坏了 Bubble Sort 的唯一目的/优势，即非常简单且代码很小。 (例如，大约 20 字节的 x86 机器代码，尽管它针对大小进行了大量优化。 更正常的实现将是类似于 InsertionSort 的大小。

---

您的代码使用 MASM 宏，最终会浪费指令重做检查(我认为.UNTIL ECX == 0没有利用dec ecx已经根据 ECX 不为零设置标志的事实)。 但它确实具有良好的do{}while()循环结构，这是asm的惯用语。

---

顺便说一句，您的伪代码缺少外部循环。 这只是BubbleSort的一次通过。 但是，是的，迭代n次将对n元素数组进行排序。