C语言实现堆排序算法 - 详细代码解析及排序过程可视化

#include <stdio.h>

// 堆排序函数声明 void heapSort(int arr[], int len);

// 建立大根堆函数声明 void buildMaxHeap(int arr[], int len);

// 维护大根堆函数声明 void heapAdjust(int arr[], int i, int len);

// 打印数组函数声明 void printArray(int arr[], int len);

int main() { int arr[20]; int len = 20;

printf("Enter 20 numbers: ");
for (int i = 0; i < len; i++) {
    scanf("%d", &arr[i]);
}

printf("Original array: \n");
printArray(arr, len);

heapSort(arr, len);

printf("Sorted array: \n");
printArray(arr, len);

return 0;

}

// 堆排序函数实现 void heapSort(int arr[], int len) { buildMaxHeap(arr, len); // 建立大根堆 printf("Heap after initialization: \n"); printArray(arr, len);

for (int i = len - 1; i >= 1; i--)
{
    int temp = arr[i];  // 交换堆顶元素和最后一个元素
    arr[i] = arr[0];
    arr[0] = temp;

    heapAdjust(arr, 0, i);  // 重新构建大根堆
    printf("Heap after iteration %d: \n", len - i);
    printArray(arr, len);
}

}

// 建立大根堆函数实现 void buildMaxHeap(int arr[], int len) { // 从最后一个非叶结点开始，向前依次调用HeapAdjust函数，构建大根堆。 for (int i = (len - 2) / 2; i >= 0; i--) { heapAdjust(arr, i, len); } }

// 维护大根堆函数实现 void heapAdjust(int arr[], int i, int len) { int temp = arr[i]; int child = 2 * i + 1;

while (child < len)
{
    if (child + 1 < len && arr[child] < arr[child + 1]) // 如果右子节点存在，且比左子节点大
    {
        child++;
    }

    if (arr[child] > temp)
    {
        arr[i] = arr[child];
        i = child;
        child = 2 * i + 1;
    }
    else
    {
        break;
    }
}

arr[i] = temp;

}

// 打印数组函数实现 void printArray(int arr[], int len) { for (int i = 0; i < len; i++) { printf("%d ", arr[i]); } printf("\n"); }