【汇编语言实战】对给定的数组实现堆排序

#include <stdio.h>
// 交换数组中两个元素的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
// 调整堆，使以root为根节点的堆满足最大堆性质
void maxHeapify(int arr[], int n, int root) {
    int largest = root;     // 初始化最大值索引为根节点
    int left = 2 * root + 1;    // 左子节点索引
    int right = 2 * root + 2;   // 右子节点索引
   
    // 如果左子节点存在且大于根节点，则更新最大值索引为左子节点
    if (left < n && arr[left] > arr[largest])
        largest = left;
   
    // 如果右子节点存在且大于当前最大值，则更新最大值索引为右子节点
    if (right < n && arr[right] > arr[largest])
        largest = right;
   
    // 如果最大值索引不是根节点，则交换根节点与最大值，并递归调整子树
    if (largest != root) {
        swap(&arr[root], &arr[largest]);
        maxHeapify(arr, n, largest);
    }
}
// 构建最大堆
void buildMaxHeap(int arr[], int n) {
    // 从最后一个非叶子节点开始，依次向前调整堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        maxHeapify(arr, n, i);
    }
}
// 堆排序
void heapSort(int arr[], int n) {
    // 构建最大堆
    buildMaxHeap(arr, n);
   
    // 从最后一个元素开始，依次将最大值交换至数组末尾，并调整堆
    for (int i = n - 1; i >= 0; i--) {
        swap(&arr[0], &arr[i]);   // 将当前最大值交换至数组末尾
        maxHeapify(arr, i, 0);     // 调整剩余元素为最大堆
    }
}
int main() {
    int arr[] = {3, 1, 5, 7, 2, 4, 9, 6, 10, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
   
    heapSort(arr, n);
   
    printf("堆排序后数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
   
    return 0;
}

include irvine32.inc
.data
  arr dd 3,1,5,7,2,4,9,6,10,8
  len dd ($-arr)/4
  two dd 2
  msg1 db ' ',0
  msg2 db ' ',0
  msg3 db ' ',0
.code
print proc
  push ebp
  mov ebp,esp
  pushad
  mov esi,0
  mov ebx,[ebp+8]
again:
  cmp esi,[ebp+12]
  jge final
  mov eax,[ebx+4*esi]
  call writeint
  mov edx,offset msg1
  call writestring
  add esi,1
  jmp again
final:
  popad
  pop ebp
  ret 8
print endp
HeapAdjust proc
  push ebp
  mov ebp,esp
  pushad
  mov esi,[ebp+8]
  mov ebx,[ebp+12]
  mov ecx,[esi+4*ebx]
  mov eax,ebx
  mul two
  add eax,1
again:
  cmp eax,[ebp+16]
  jge final
  mov edx,eax
  add edx,1
  cmp edx,[ebp+16]
  jge next1
  mov edi,[esi+4*eax]
  cmp edi,[esi+4*edx]
  jge next1
  add eax,1
next1: 
  mov edx,[esi+4*eax]
  cmp [esi+4*ebx],edx
  jge final
  mov [esi+4*ebx],edx
  mov ebx,eax
  mov eax,ebx
  shl eax,1
  add eax,1
  mov [esi+4*ebx],ecx
  jmp again
final:
  popad
  pop ebp
  ret 12
HeapAdjust endp
BuildingHeap proc
  push ebp
  mov ebp,esp
  pushad
  mov eax,[ebp+12]
  sub eax,1
  mov edx,0
  div two
again:
  cmp eax,0
  jl final
  push dword ptr[ebp+12]
  push eax
  push dword ptr[ebp+8]
  call HeapAdjust
  sub eax,1
  jmp again
final:
  popad
  pop ebp
  ret 8
BuildingHeap endp
HeapSort proc
  push ebp
  mov ebp,esp
  pushad
  push dword ptr[ebp+12]
  push dword ptr[ebp+8]
  call BuildingHeap
  mov edx,[ebp+8]
  mov esi,[ebp+12]
  sub esi,1
again:
  cmp esi,0
  jle final
  mov edi,0
  mov ebx,[edx+4*esi]
  mov ecx,[edx+4*edi]
  mov [edx+4*esi],ecx
  mov [edx+4*edi],ebx
  push esi
  push edi
  push dword ptr[ebp+8]
  call HeapAdjust
  sub esi,1
  jmp again
final:
  popad
  pop ebp
  ret 8
HeapSort endp
main proc
  mov edx,offset msg2
  call writestring
  push len
  push offset arr
  call print
        call crlf 
  push len
  push offset arr
  call HeapSort
  mov edx,offset msg3
  call writestring
  push len
  push offset arr
  call print
  exit
main endp
end main