Masm64：排序算法

1. 冒泡排序（Bubble Sort）

原理

冒泡排序是一种简单的排序算法。它重复地走访要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

代码实现

.686p
.MODEL flat, stdcall
.STACK 4096
.DATA
array DWORD 5, 4, 3, 2, 1
array_size EQU ($ - array) / TYPE array
.CODE
main PROC
mov ecx, array_size
dec ecx
outer_loop:
mov esi, 0
inner_loop:
mov eax, array[esi]
cmp eax, array[esi + 4]
jle no_swap
xchg eax, array[esi + 4]
mov array[esi], eax
no_swap:
add esi, 4
cmp esi, ecx * 4
jl inner_loop
loop outer_loop
mov eax, 0
ret
main ENDP
END main

2. 插入排序（Insertion Sort）

原理

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为新元素提供插入空间。

代码实现

.686p
.MODEL flat, stdcall
.STACK 4096
.DATA
array DWORD 5, 4, 3, 2, 1
array_size EQU ($ - array) / TYPE array
.CODE
main PROC
mov ecx, 1
outer_loop:
mov eax, array[ecx * 4]
mov esi, ecx
dec esi
inner_loop:
cmp eax, array[esi * 4]
jge no_move
mov array[(esi + 1) * 4], array[esi * 4]
dec esi
cmp esi, 0
jge inner_loop
no_move:
mov array[(esi + 1) * 4], eax
inc ecx
cmp ecx, array_size
jl outer_loop
mov eax, 0
ret
main ENDP
END main

3. 选择排序（Selection Sort）

原理

选择排序首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

代码实现

.686p
.MODEL flat, stdcall
.STACK 4096
.DATA
array DWORD 5, 4, 3, 2, 1
array_size EQU ($ - array) / TYPE array
.CODE
main PROC
mov ecx, array_size
dec ecx
outer_loop:
mov esi, 0
mov ebx, esi
mov eax, array[esi]
inner_loop:
add esi, 4
cmp eax, array[esi]
jle no_min
mov eax, array[esi]
mov ebx, esi
no_min:
cmp esi, ecx * 4
jl inner_loop
mov esi, ebx
mov eax, array[esi]
mov array[esi], array[0]
mov array[0], eax
add ecx, - 1
cmp ecx, 0
jg outer_loop
mov eax, 0
ret
main ENDP
END main

4. 快速排序（Quick Sort）

原理

快速排序采用分治法（Divide - and - Conquer）的一个非常典型的应用。它的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

代码实现（简单示例）

.686p
.MODEL flat, stdcall
.STACK 4096
.DATA
array DWORD 5, 4, 3, 2, 1
array_size EQU ($ - array) / TYPE array
.CODE
partition PROC
; 函数参数通过寄存器传递，假设数组首地址在esi中，数组大小在ecx中
mov eax, array[esi]
mov edi, esi
inc edi
mov ebx, ecx
dec ebx
partition_loop:
cmp edi, ebx
jg partition_end
mov edx, array[edi]
cmp edx, eax
jle partition_left
mov edx, array[ebx]
cmp edx, eax
jge partition_right
xchg array[edi], array[ebx]
inc edi
dec ebx
jmp partition_loop
partition_left:
inc edi
jmp partition_loop
partition_right:
dec ebx
jmp partition_loop
partition_end:
mov edx, array[ebx]
cmp edx, eax
jle partition_final
xchg array[esi], array[ebx]
ret
partition_final:
xchg array[esi], array[edi - 4]
ret
partition ENDP
quick_sort PROC
; 函数参数通过寄存器传递，假设数组首地址在esi中，数组大小在ecx中
cmp ecx, 1
jle quick_sort_end
call partition
mov esi, 0
mov ecx, eax
call quick_sort
mov esi, eax
add esi, 4
mov ecx, array_size - eax
call quick_sort
quick_sort_end:
ret
quick_sort ENDP
main PROC
mov esi, 0
mov ecx, array_size
call quick_sort
mov eax, 0
ret
main ENDP
END main