C语言描述:
#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
运行结果: