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'); }

// 答辩内容：这是一个使用堆排序算法对输入的20个数进行排序的程序。程序首先通过输入函数将用户输入的20个数存储在数组中，然后调用heapSort函数对数组进行排序。在heapSort函数中，首先调用buildMaxHeap函数建立大根堆，然后通过循环将堆顶元素与最后一个元素交换，并调用heapAdjust函数重新构建大根堆。最后，程序调用printArray函数打印排序后的数组。

// 堆排序算法的核心思想是通过建立大根堆，将数组中的最大元素放在堆顶，然后将堆顶元素与最后一个元素交换位置，再重新构建大根堆。重复这个过程，直到整个数组有序。

// 在程序输出中，每次迭代后都会打印当前的堆，可以观察到堆在迭代过程中的变化。